Implementing the weakest failure detector for solving the consensus problem
- 23 January 2013
- journal article
- research article
- Published by Taylor & Francis in International Journal of Parallel, Emergent and Distributed Systems
- Vol. 28 (6) , 537-555
Abstract
The concept of unreliable failure detector was introduced by Chandra and Toueg as a mechanism that provides information about process failures. This mechanism has been used to solve several agreement problems, such as the consensus problem. In this paper, algorithms that implement failure detectors in partially synchronous systems are presented. First two simple algorithms of the weakest class to solve the consensus problem, namely the Eventually Strong class (⋄S), are presented. While the first algorithm is wait-free, the second algorithm is f-resilient, where f is a known upper bound on the number of faulty processes. Both algorithms guarantee that, eventually, all the correct processes agree permanently on a common correct process, i.e. they also implement a failure detector of the class Omega (Ω). They are also shown to be optimal in terms of the number of communication links used forever. Additionally, a wait-free algorithm that implements a failure detector of the Eventually Perfect class (⋄P) is presented. This algorithm is shown to be optimal in terms of the number of bidirectional links used forever.Keywords
This publication has 27 references indexed in Scilit:
- On implementing omega in systems with weak reliability and synchrony assumptionsDistributed Computing, 2008
- On the implementation of unreliable failure detectors in partially synchronous systemsIEEE Transactions on Computers, 2004
- On the quality of service of failure detectorsIEEE Transactions on Computers, 2002
- A simple and fast asynchronous consensus protocol based on a weak failure detectorDistributed Computing, 1999
- Reducing Ω to ◊Information Processing Letters, 1998
- Early consensus in an asynchronous system with a weak failure detectorDistributed Computing, 1997
- The weakest failure detector for solving consensusJournal of the ACM, 1996
- Unreliable failure detectors for reliable distributed systemsJournal of the ACM, 1996
- Consensus in the presence of partial synchronyJournal of the ACM, 1988
- Impossibility of distributed consensus with one faulty processJournal of the ACM, 1985