Many important distributed computing problems cannot be solved in purely asynchronous fault-prone systems. These impossibilities can be circumvented with failure detectors, distributed oracles that provide computing units with hints about failures. The weakest failure detector for a given problem defines necessary and sufficient assumptions about failures that enable the problem’s solutions. In this meeting, we are going to discuss how to determine two important weakest failure detectors: (1) Omega, the leader election failure detector for solving consensus and (2) Sigma, the quorum failure detector for implementing read-write storage.
Literature:
[1] Tushar Deepak Chandra, Sam Toueg: Unreliable Failure Detectors for Reliable Distributed Systems. J. ACM 43(2): 225-267 (1996).
[2] Tushar Deepak Chandra, Vassos Hadzilacos, Sam Toueg: The Weakest Failure Detector for Solving Consensus. J. ACM 43(4): 685-722 (1996).
[3] Carole Delporte-Gallet, Hugues Fauconnier, Rachid Guerraoui: Tight failure detection bounds on atomic object implementations. J. ACM 57(4): 22:1-22:32 (2010).