algorithmdistributeddistributed-systemconsensuspaxos

Why does Paxos ensure that consensus is reached and does not change?

I have been reading about single-decree Paxos (primarily looking at Paxos Made Simple) yet am confused about if a consensus among Acceptors is guaranteed to not change after being reached.

According to James Aspnes's notes,

So now we suppose that some value v is eventually accepted by a majority T with number n. Then we can show by induction on proposal number that all proposals issued with higher numbers have the same value (even if they were issued earlier).

However, I am confused since I believe I have a counterexample, shown below. Feel free to jump to step 12 since that is where simple steps can illustrate the problem. I have included steps 1-12 in case it is not possible to reach the state in step 12.

Consider the following behavior. Borrowing notation from Contradiction in Lamport's Paxos made simple paper. That is, X(n:v, m), means Acceptor X has largest accepted proposal n:v, where n is proposal number and v is value, and m is the largest numbered prepare response to which Acceptor X has responded.

Say we have 3 Acceptors A, B, C. Let Px be a proposer, or even multiple proposers, who keeps sending proposals since they don't find out about any consensus being reached.

  1. Px broadcasts prepare(1)
  2. A and B respond with promise, state is A(:, 1), B(:, 1)
  3. Px receives promises from A and B, confirms majority and broadcasts accept(1:'foo')
  4. Only A receives this accept, state is now A(1:'foo', 1), B(:, 1), C(:,)
  5. Py broadcasts prepare(2)
  6. B, C respond with promises, state is now A(1:'foo', 1), B(:, 2), C(:,2)
  7. Py receives promises from B and C, confirms majority and broadcasts accept(2:'bar')
  8. Only B receives this accept, state is A(1:'foo', 1), B(2:'bar', 2), C(:,2)
  9. Pz broadcasts prepare(3)
  10. A and C response with promise, state is A(1:'foo', 3), B(2:'bar', 2), C(:,3)
  11. Pz receives promises from A and C, confirms majority, notes that 1:'foo' is the largest numbered accepted value, and broadcasts accept 3:'foo'
  12. Only C receives this accept, state is A(1:'foo', 3), B(2:'bar', 2), C(3:'foo', 3) -- A consensus has been reached! 'foo' is the value decided upon --
  13. Pn doesn't know about this, broadcasts prepare(4)
  14. A and B response with promise, state is A(1:'foo', 4), B(2:'bar', 4), C(3:'foo', 3)
  15. Pn receives promises from A and B, confirms majority, notes that 2:'bar' is the largest numbered accepted value, and broadcasts accept 4:'bar'
  16. A receives this broadcast, state is A(4:'bar', 4), B(4:'bar', 4), C(3:'foo', 3). -- A consensus has been reached! 'bar' is the value decided upon --

To be clear, steps 4, 8, 12, don't necessarily mean that the other nodes "failed", but I think it can just the proposer in question is taking a really long time to deliver the messages. Thus this shouldn't be a case where more than N acceptors crash in out of 2N + 1.

The top-voted answer in Contradiction in Lamport's Paxos made simple paper suggests that Proposers only sent accept messages to Acceptors who promised them and an acceptor accepting a value means updating the maxBal. Both of these are satisfied in the above example, yet it shows how consensus can flip-flop between two different values. Am I missing something here?

Solution

  • I am going to copy&paste a statement straight from Paxos article in wikipedia: "consensus is achieved when a majority of Acceptors accept the same identifier number (rather than the same value)".

    So in your step 12 "state is A(1:'foo', 3), B(2:'bar', 2), C(3:'foo', 3) -- A consensus has been reached! 'foo' is the value decided upon" - there is no consensus yet; even if there is a majority in the value.

    p.s. thanks for the questions, this is a nice highlight on the consensus definition in Paxos!