Eventually-quiescent election scheduling

Although it is provably[^1] impossible to ensure any particular master election attempt succeeds, Elasticsearch's election protocol is eventually quiescent which means that we can almost-surely guarantee that the cluster eventually elects a master by extending the time between election attempts until the gap is long enough for a single attempt to run to completion without interference from other nodes.

Today we do not back off the election scheduler in all the situations needed to truly guarantee the eventual completion of an election:

the followers reset their schedulers once they have locally applied the state, but there are still other messages in flight at this point so we have not yet reached the quiescent state.
if we are missing a join vote from a node (i.e. it voted for a different master in the current term) then we bump the term and run another election.
the backoff is bounded (to 10s by default, which can be extended if needed, but only up to 600s). Also by default we only back off linearly (by 100ms) on each failed attempt, and while this doesn't affect the claim that we will eventually succeed, it does mean it might take a very long time to back off far enough to complete a very slow election.

Today's implementation works very well in practice for almost all clusters, but may not be effective in clusters with particularly poor IO performance, especially if the cluster is very large or otherwise unusually configured. I'm opening this issue to track that there's still some gaps in this area.

[^1]: Michael J. Fischer, Nancy A. Lynch, and Michael S. Paterson. 1985. Impossibility of distributed consensus with one faulty process. J. ACM 32, 2 (April 1985), 374–382.

elastic / elasticsearch

Eventually-quiescent election scheduling #98467