Hacker News Reader

Comment by rubiquity | Hacker News Reader

Using incrementing ballot numbers is fine. If you have multiple Proposers all sending the same ballot number in Phase 1 (Prepare & Promise) the Acceptors will reject any ballot number less than the highest ballot number they have received. In order to move to Phase 2, the Proposer needs to receive the thumbs up from a majority of the Acceptors, which means only one Proposer can ever win.

If you were to divide the ballot number space, in the event that the owner of the highest values in that space won, every other proposer would immediately need to increase their ballot numbers for all future rounds and so on and so forth or else they would always get rejected.

View on HN

The problem is on the recovery path.

Recovery path needs to identify if there was a chosen value only from F+1 nodes (out of 2*F+1 nodes total).

When two proposers with same proposal-number, but different values have partially executed the protocol before the crash, then you would end up with all F+1 nodes with same proposal number indicating successful consensus previously, but with divergent values.

I'm not sure what you mean by "recovery path" or "partially executed the protocol before the crash." Paxos has specific terminology for each of the phases. Can you be more precise?

Sure, imagine all nodes are crashed (due to poweroff) in the middle of two proposers A and B doing Phase2 with the same proposal-number, but different values. Remember, they can go to Phase2 cause their proposal-number is the largest ever seen when they are the first.

Proposer-A received Phase2 votes from nodes n_1,...n_f and Proposer-B received one vote from n_f+1 when power is off and other nodes n_f+2, n_f+3...n_2f+1 don't know anything about the Phase2.

Now, consider the case when power is back and only the first F+1 nodes came back online. System is expected to continue with F+1 live nodes.

Proposer-C now does Phase-1 with the same proposal-number. He is expected to pick the already voted value associated with the max proposal-number from the Phase-1 responses, but there are two different values and he can't determine what to pick.

I think you're mistaken about the ability of 2 proposers to move to phase 2 - once an acceptor has agreed to a proposal with a certain seq number, it cannot just agree to another one with the same seq number. And that means only one of the two proposers can obtain the required majority of votes to start sending Accept messages, and thus only one of the two values can be accepted by any acceptor.

Maybe read the papers on Paxos, like the "Paxos Made Simple" one, it's not too big (though it's not all that simple either, at least to me...).

I do not want spend more time on this, so I will let you explore.

Algorithm is not tied to the proposer identity (uuid or fqdn or ip, etc.) The promise in Phase-1 response is not to the proposer, but to the proposal-number.

In your model, proposer cannot change his identity, between Phase-1 and Phase-2 which is not a constraint imposed by the algorithm.

Here is what the paper says:

Phase 1.

(a) A proposer selects a proposal number n and sends a prepare request with number n to a majority of acceptors.

(b) If an acceptor receives a prepare request with number n greater than that of any prepare request to which it has already responded, then it responds to the request with a promise not to accept any more proposals numbered less than n and with the highest-numbered proposal (if any) that it has accepted.

Important part of the statement is

  ...with a promise not to accept any more proposals numbered less than n...

So, Phase-1 promise is not on the proposer-identity, but on the proposal-number.

You're right, my mistake!

But it still should not be an issue, since according to what you quoted an acceptor will not reply to a second proposal that bears the same number ("If an acceptor receives... number n greater than...), which means only one of the two proposers can gather the required majority of promises to move to the next phase, and thus only one of the values can end up being accepted. After the crash you describe, there will be only one accepted value the Proposer-C will receive.

Such assumptions break network request retries and/or relies on proposer-identity, etc.

Reply on news.ycombinator.com