Why does a prepare message wants a promise that an acceptor is never to accept a proposal numbered less than its propose sequence value? (Paxos)

Question

I was studying Paxos from:

http://research.microsoft.com/en-us/um/people/lamport/pubs/paxos-simple.pdf

Recall that Paxos is a distributed system algorithm with the goal that the processes participating in its protocol will reach consensus on one of the valid values.

On page 4 of the paper, at the bottom where they outline what a prepare request looks like it says:

"A proposer chooses a new proposal number n and sends a request to each member of some set of acceptors, asking it to respond with:

(a) A promise never again to accept a proposal numbered less than n,

(b) ... "

Why does prepare message extract such promise from the set of acceptors that receive such a prepare message? What is the goal and what safety guarantee does it provide? How does it aid Paxos into reaching a consensus to a certain value? How is it crucial so that a majority can reach agreement?

I did some further research to try to answer this question and went to the following yale university notes:

http://pine.cs.yale.edu/pinewiki/Paxos

These notes try to justify this point by saying:

"... proposer tests the waters by sending a prepare(n) message to all accepters where n is the proposal number. An accepter responds to this with a promise never to accept any proposal with a number less than n (so that old proposals don't suddenly get ratified)... "

Basically, the way they justify that step is by saying so that old proposals don't get ratified/accepted. Which I kind of see why they said that, since if a decision has happened, that rule definitively avoids the consensus from being reversed, which is nice. But, however, the reason I did not feel very convinced about it yet is because it seems to damage termination a lot. What if if a majority was about to be formed in the past and the proposer was ready to send the propose(n) and now because a different prepare(n') was sent its not able to reach agreement? I can't seem to convince myself that that this step is 100% a good idea.

Unless the only reason for that step is because they just want to guarantee that once a value has been chosen/decided, by adopting this rule, its impossible that any old proposal reverses the decision?

Again, I did some further research by reading the yale article and now it says:

"The rule that an acceptor doesn't accept any proposal earlier than a round it has acknowledged means that the value v in an ack(n, v, n_v) message never goes out of date—there is no possibility that an acceptor might retroactively accept some later value in round n' with nv < n' < n. So the ack message values tell a consistent story about the history of the protocol, even if the rounds execute out of order."

However, its not obvious to me why retroactivity might be bad (unless in the case that I already mentioned). Retroactivity could be good if it somehow manages our protocol to reach consensus. Still the only reason I see for such a rule is so that one doesn't reverse a decision by accident once a value has been agreed on.

---

Author: Leslie Lamport

Title: Paxos made simple

Institution: Microsoft Research

Answer 1

Without N being monotonically incremented this may happen:

1. Proposer P1 get promises from every Acceptor for N=1
2. Proposer P1 goes to slip (e.g. java garbage collection kicks in)
3. Another proposer P2 with N=2 gets promises and gets its value V2 accepted by all acceptors - consensus happened.
4. Proposer P1 wakes up and sends accepts to all, without smaller N being rejected, the consensus will change its decision - broken logic.

You could find other examples, when increasing N is important. Think about case when acceptors already accepted some values and proposers has to respect that.

The important part to understand about epaxos - it does not really have to stop; after a consensus happened, proposers may keep proposing new values and N will keep increasing. The algorithm makes sure that while N keep increasing, the same value is kept being sent to learners.

Since in reality proposers, learners and acceptors are same boxes (each box/server/node runs all three nodes), proposers should stop proposing after their learned about a consensus.