3
$\begingroup$

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

$\endgroup$
  • $\begingroup$ There doesn't seem to be a concise question to be answered here. The consistency is required for a strong version of the invariant $P2^c$ in the cited paper (which satisfies a chain of implications $P2^c\implies P2^b\implies P2^a\implies P2$). Perhaps retroactive acceptance could somehow form a valid consensus protocol, (since only $P2$ needs to be satisfied), but it would be very complicated. $\endgroup$ – VF1 May 28 '14 at 23:20

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.