3 ms·

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. R

by iambvk 6y ago

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.

bakhy 6y ago
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...).
- iambvk 6y ago
  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.
- iambvk 6y ago
  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.
  - bakhy 6y ago
    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.
    - iambvk 6y ago
      Such assumptions break network request retries and/or relies on proposer-identity, etc.

by iambvk 6y ago

bakhy 6y ago

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...).

iambvk 6y ago
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.
iambvk 6y ago
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.
- bakhy 6y ago
  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.
  - iambvk 6y ago
    Such assumptions break network request retries and/or relies on proposer-identity, etc.