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...)