View article

Unreliable failure detectors [3] are useful devices to solve several fundamental problems in fault-tolerant distributed computing, like consensus or atomic broadcast. In their original work [3], Chandra and Toueg proposed 8 different classes of unreliable failure detectors, and showed that all of them can be used to solve consensus in a crash-prone asynchronous system with reliable links. All these detectors have at least a property called Weak Completeness: eventually, every process that fails is permanently suspected by some correct process. In a follow up work with Hadzilacos [2], they proposed another type of failure detector, Ω, which guarantees that eventually all correct processes permanently choose the same correct process as leader. They show in [2] that Ω is the weakest detector that can be used for solving consensus in this type of systems. When the membership is known, an Ω failure detector trivially also implements a 3S failure detector (3S is one of the 8 original classes).