Share on Facebook Tweet on Twitter Share on LinkedIn Share by email
Omega Meets Paxos: Leader Election and Stability without Eventual Timely Links

Dahlia Malkhi, Florin Oprea, and Lidong Zhou


This paper provides a realization of distributed leader election without having any eventual timely links. Progress is guaranteed in the following weak setting: Eventually one process can send messages such that every message obtains f timely responses, where f is a resilience bound. A crucial facet of this property is that the f responders need not be fixed, and may change from one message to another. In particular, this means that no specific link needs to remain timely. In the (common) case where f=1, this implies that the FLP impossibility result on consensus is circumvented if one process can at any time communicate in a timely manner with one other process in the system. The protocol also bears significant practical importance to well-known coordination schemes such as Paxos, because our setting more precisely captures the conditions on the elected leader for reaching timely consensus. Additionally, an extension of our protocol provides leader stability, which guarantees against arbitrary demotion of a qualified leader and avoids performance penalties associated with leader changes in schemes such as Paxos.


Publication typeInproceedings
Published in19th Intl. Symposium on Distributed Computing (DISC 05)
InstitutionMicrosoft Research
AddressCracow, Poland
PublisherEuropean Association for Theoretical Computer Science
> Publications > Omega Meets Paxos: Leader Election and Stability without Eventual Timely Links