12 ms·

On Paxos: The following already seems wrong. AFAIK the proposal number space must be divided across proposers. If all proposers use minNumber+1 replicas will di

by iambvk 6y ago

On Paxos: The following already seems wrong. AFAIK the proposal number space must be divided across proposers. If all proposers use minNumber+1 replicas will diverge on the chosen value. protected override void Propose(Instance r) { proposalNumber = minNumber + 1; Broadcast(r, MessageType.Propose, proposalNumber); }

rubiquity 6y ago
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.
- iambvk 6y ago
  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.
  - rubiquity 6y ago
    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?
    - 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.

by iambvk 6y ago

rubiquity 6y ago

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.

iambvk 6y ago
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.
- rubiquity 6y ago
  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?
  - 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.