Cheap and Secure Web Hosting Provider : See Now

[Solved]: Why does an acceptor send the highest numbered proposal with number less than n as a response to prepare(n) in paxos?

, , No Comments
Problem Detail: 

I was reading the Paxos notes from yale from the following link:

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

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.

I was trying to better understand the revoting mechanism to avoid deadlocks in Paxos. The revoting mechanism is explained as follows in the article:

The revoting mechanism now works like this: before taking a vote, a 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) together with the highest-numbered proposal that the accepter has accepted (so that the proposer can substitute this value for its own, in case the previous value was in fact ratified).

The bold section is the one that I was trying to understand better. The author tries to justify it with:

"...so that the proposer can substitute this value for its own, in case the previous value was in fact ratified..."

But I didn't really understand why the proposer would want to ratify the previous value. By doing this, what crucial safety property is he guaranteeing? Why is he responding with that and not something else? Responding with the highest could be problem, right, since the current proposal would get lost?

Asked By : Pinocchio

Answered By : Pinocchio

As I was writing my question I realized what I believe to be the correct answer and wanted to share it just in case someone else was wondering this step in Paxos, or maybe correct it if its not 100% correct (or clear).

Recall that, in Paxos, the actual goal is to achieve some consensus (agreement) on some value. The actual value is not very important as long as its from the valid set of values. However, we only care that our protocol somehow achieves some agreement. Thus, if we are a proposer and want to propose a value, what we really care is that some value is agreed amongst the processes participating in the protocol (since that the goal of a consensus algorithm, that some valid value is accepted). If for some reason, we were desperate for our value to be accepted at some point, we could eventually re-run a different instance of Paxos later (or more instances of Paxos until that value is chosen), so its ok to try to suggest the value later (to a different paxos instance) if we really need to (but that will be a different set of rounds of Paxos, starting with round zero and doing Paxos all over again). Its crucial to understand that suggesting the value to the same paxos instance is pointless since the point is that once paxos reaches consensus, that it sticks to it. We have to run paxos for a different set of values if we want our value to still be decided at some point.

But, the point of the step that "acceptors respond with the highest-numbered proposal that the current acceptor has seen", is to guarantee that if a value in the past (with lower sequence number) had been ratified, then why complicate agreement by considering a different value? It's easier to eventually agree at some value if we just keep that ratified value instead. Furthermore, and the more important reason is, imagine if we decided to discard the value we had ratified previously and instead ratify the new incoming one. Well, if we did that and update our state it could be very bad, because, one important property we wish our algorithm to have is, "once an agreement by majority has been reached, we wish it to be impossible for our system to change its mind" (because consensus has occurred already, so a change in mind is completely unnecessary). If we take this new (wrong) approach I have suggested, then that property could not hold. However, if instead, we always just respond with the highest ratified value, then the proposer on the other side is bound to learn the chosen value, if one has been chosen (if he queries some majority). Thus, the safe thing to do is, just send the proposer the current ratified value with the highest sequence number, that way, if a value was chosen, then the system is not able to change its mind if a consensus occurred (since its not necessary for it to change its mind since some value has already been accepted by some majority!). The whole point of consensus means that we agree on something, so changing the value can be viewed as breaking consensus.

Best Answer from StackOverflow

Question Source : http://cs.stackexchange.com/questions/24209

3.2K people like this

 Download Related Notes/Documents

0 comments:

Post a Comment

Let us know your responses and feedback