Implementing the Omega failure detector in the crash-recovery failure model
📜 Abstract
Unreliable failure detectors are mechanisms providing information about process failures, that allow to solve several problems in asynchronous systems, e.g., Consensus. A particular failure detector, Omega, provides an eventual leader election functionality. This paper addresses the implementation of Omega in the crash-recovery failure model. We first propose an algorithm assuming that processes are reachable from the correct process that crashes and recovers a minimum number of times. Then, we propose two algorithms which assume only that processes are reachable from some correct process. Besides this, one of the algorithms requires the membership to be known a priori, while the other two do not.
✨ Summary
The paper studies how to implement the Omega failure detector when processes may crash and later recover, including processes that recover infinitely often. The system model permits directed, partially connected communication networks containing both eventually timely links and lossy asynchronous links. Processes use stable storage to preserve incarnation numbers and, when needed, their current leader across recoveries.
The authors adapt the specification of Omega to crash-recovery systems. Instead of requiring eventual agreement only among permanently correct processes, the proposed specification requires that, after some point, every active process—whether correct or unstable—trust the same correct process. This accounts for the fact that an unstable process cannot determine whether it will eventually remain up or continue to recover repeatedly.
Three algorithms are presented. The first does not require prior knowledge of membership and elects the correct process with the smallest identifier among those having the minimum incarnation number. It requires eventual timely reachability from that particular process to all correct and unstable processes. The second assumes that membership is known and requires eventual timely reachability from some correct process. It propagates vectors of suspicion counters and eventually selects the correct process with the smallest stabilized suspicion value, using identifiers to break ties. The third removes the prior-membership requirement by dynamically propagating membership information and suspicion values; a self-punishment mechanism handles processes that may not be observed by other processes.
The correctness arguments establish that, under the stated reachability and eventual-timeliness assumptions, all active processes eventually trust one common correct process permanently. The algorithms also use increasing timeouts and incarnation numbers to prevent unstable processes and transient communication delays from permanently disrupting leader selection. For the second and third algorithms, periodic traffic is bounded by the product of the number of processes and the number of directed links; the first algorithm can require rebroadcasting over up to quadratic many links in the worst case.
The paper’s documented influence is primarily academic. Later work explicitly treats these algorithms as prior crash-recovery implementations of Omega and develops a communication-efficient algorithm that removes the need for stable storage. (sciencedirect.com) A subsequent study formalizes communication efficiency and near-efficiency for crash-recovery leader election and presents algorithms using stable storage and, under stronger assumptions, no stable storage. (sciencedirect.com) Later research also extends the setting to systems combining crash-recovery and omission failures, citing this paper as an earlier Omega implementation and using its crash-recovery leader-election framework as related work. (sciencedirect.com) The sources located document research extensions, but no specific industry deployment of this paper’s algorithms.