If you are unfamiliar with multi-Paxos or paxos, the following link might be a good refresher on it:


or the paper by Leslie Lamport:


I was thinking about multi-Paxos and what one should do to elect a new leader if one is to fail (or in general, just if we want to re-elect a leader). I know that Multi-Paxos normally operates under the assumption that there is a stable leader. However, it does not mean that the Leader never fails or that we might never want to change the leader. It might be uncommon, but we must do something so that the system can function properly in the case that we might want to change leader.

I was wondering, what was the standard way to handle leader failures in multi-Paxos?

I have thought of different ways to handle failures of leaders and also google them, but it's still not clear to me how it should be done.

Let me also clarify what I mean by multi-Paxos and clarify that its not the mechanism described in the following source:


What I mean by multi-Paxos is the abstract idea of deciding a list of Paxos instances by a single leader. This leader sends a range of Paxos Instances it wants to prepare and thus, it can hear a single a single prepare acknowledgement for the whole range instead of one per Paxos instances. Therefore, we can avoid a round-trip and have a more efficient prepare phase. Furthermore, we can now send accept messages immediately for that range since we have already prepared the values.

However, I was a little unsure of how multi-Paxos normally handled choosing a new leader, if the current leader happened to die. Does it doing by running a Paxos instance? Also, how often does it change leader? Can we do a leasing mechanism that after some time t a leader is re-elected? If we do, can this only be achieved if one assumes clock synchronization? The article I initially posted talks about multi-Paxos but kind of skips the detail I am trying to address.

If anyone has better sources or an idea of how one should implement leader election, I would love to hear about it, because I am sure that implementing multi-Paxos is not a "new" problem and that is has been addressed before at some point (and I would rather avoid very very weird "ad-hoc" ideas...)


1 Answer 1


Using the terminology of the Leslie Lamport Paxos Made Simple a leader is implicitly chosen when phase 1 is executed and a node hears it has the highest proposal. The problem is not leader election as phase 1 is leader election; the trick is that any server can start and win a new election before the previous leader can make any progress. So rather than the challenge of getting a leader the challenge is not getting too many competing leaders duelling; yet not waiting too long before attempting to get a new leader. See this answer that quotes where the original Paxos papers talk about having a stable leader after a proposal has been accepted.

The raft paper has a lot of detail about leader timeouts. Basically you should have the leader send heartbeats. These can be no-op values as described in the Paxos Made Simple paper. If a follower does not get a message for a while it can timeout and propose. You add a bit of randomness to the timeout to try to prevent simultaneous proposers. You should respond with nacks as mentioned in the Papxs paper stating the higher promise value. That way if you do get simultaneously proposers the nacks will suppress candidates as only one candidate will get the highest number to a majority leading to nacks to the other candidates inside of one full round of phase 1+2 messages to the winner.

If servers stay up after the failure and the network stays stable a new leader should emerge promptly without too much delay or wasted messages on failed rounds due to duelling. The exact timeouts to set can be tuned to a given environment exactly as described in the raft paper.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.