Paxos ballot number reuse

Question

On receiving the prepare message from proposer, the Acceptor responds with either promise or refuse.

If proposer did not received enough promises and times-out, the proposer should discard the promises/refusals received and start a new prepare round with a greater ballot number.

If the restart is only because of timeout instead of receiving a refusal, can we reuse the same ballot number?

Answer 1

Short answer: don't do it.

When discovering Paxos Lamport made the assumption that messages could be dropped or duplicated. So at any point you could send the same message again, and the algorithm would deal with it. So technically you can send re-use the same ballot number as long as the payload is exactly the same. Here are some off-the-cuff reasons why you shouldn't.

First, the algorithm says to use a higher ballot number. You have to really know what you are doing if you are going to change a distributed algorithm like this. Reasoning about distributed systems can be very, very hard. And even if you did know what you are doing, you have know way of knowing if the maintainers who come after you know what they are doing.

Second, the base algorithm doesn't actually have anything about refusals/nacks; they are merely optimizations. (Remember they could be dropped at any time.) So not receiving a prepare should be considered a refusal.

Third, there could be another proposer out there. If you decide to re-use the same ballot number, you are essentially giving up and letting the other win. But if the other proposer is using the same algorithmic embellishment, it is also giving up. You are effectively choosing the leader before-hand.

Fourth, not receiving a quorum of responses means your system is in trouble: a network partition; half the majority of hosts not responding quickly enough. These are important things to think about. How will sending the exact same message help the problem?

In the end, re-using the ballot number doesn't buy you anything, but it does complicate things.

Answer 2

You previous proposal was not accepted most likely because it is a smaller ballot number compared to those proposed by the other replicas. So if you insist the old ballot number in your next proposal, you will be rejected again with a very high chance.