CODEWITHSUNDEEP
distributed-systempaxos
nz_21
nz_21

Reputation: 7383

paxos: why do ids have to increase monotonically?

This is pseudocode for prepare stage:

 Is this ID bigger than any round I have previously received?
    If yes
        store the ID number, max_id = ID
        respond with a PROMISE message
    If no
        do not respond (or respond with a "fail" message)

Why do only higher ids get accepted?

Upvotes: 1

Views: 161

Answers (1)

simbo1905
simbo1905

Reputation: 6862

In the strictest sense the answer to your question is the if any lower value is accepted then it does not match the mathematical proof of correctness provide by Lamport.

That strict answer is of course a not very helpful. My intuitive answer is to consider the following:

  • A leader suddenly stalls (becomes blocked/frozen on io or garbage collection) else becomes disconnect from the rest of the cluster. The rest of the cluster thinks it is dead and elect a new leader. The new leader runs happily. Then then the old leader suddenly comes back sending messages with old numbers. We want the late messages of the old leader to be ignored.

  • A cluster experiences network issues such that in a three-node cluster two nodes are attempting to lead. They both issues prepare messages at the same instance to themselves and the other nodes. All nodes see all messages but they arrive in different orders at different nodes. If each node can accept messages that are higher or lower then how can we determine ”who won”? By only accepting higher numbers and ensuring that each node only sends unique numbers is there a clear “winning leader”. Whichever node issued the highest number will see a majority response and can issue an accept message. If it is not interrupted by any other node sending a higher prepare it will succeed as long as enough messages are successfully delivered.

One thing to note is that there is no requirement of strict monoatomic numbering. The original paper only requires that the numbers can be ordered. Practically ballot numbers tend to be made up of higher and lower bits. In the lower bits the node always writes its own node number which must be unique in the cluster. The higher bits are a local counter used by that node to try to “go higher” without rapidly exhausting the available bit range. Then numbers are unique to nodes and can always be ordered. If a leader dies the new leader should not attempt to start its numbers lower than the previous leader. It will reset its counter to be one higher than the higher counter bits in the last prepare it accepted. Another node in the cluster won't necessarily experience seeing monotonically increasing numbers between subsequent leaders but rather small gaps.

Upvotes: 1

Related Questions