The weakest failure detector for solving consensus
- 1 July 1996
- journal article
- Published by Association for Computing Machinery (ACM) in Journal of the ACM
- Vol. 43 (4) , 685-722
- https://doi.org/10.1145/234533.234549
Abstract
We determine what information about failures is necessary and sufficient to solve Consensus in asynchronous distributed systems subject to crash failures. In Chandra and Toueg (1996), it is shown that {0, a failure detector that provides surprisingly little information about which processes have crashed, is sufficient to solve Consensus in asynchronous systems with a majority of correct processes. In this paper, we prove that to solve Consensus, any failure detector has to provide at least as much information as {0. Thus, {0is indeed the weakest failure detector for solving Consensus in asynchronous systems with a majority of correct processes.Keywords
This publication has 8 references indexed in Scilit:
- Unreliable failure detectors for reliable distributed systemsJournal of the ACM, 1996
- Using process groups to implement failure detection in asynchronous environmentsPublished by Association for Computing Machinery (ACM) ,1991
- Consensus in the presence of partial synchronyJournal of the ACM, 1988
- A combinatorial characterization of the distributed tasks which are solvable in the presence of one faulty processorPublished by Association for Computing Machinery (ACM) ,1988
- On the minimal synchronism needed for distributed consensusJournal of the ACM, 1987
- Fault-tolerant decision making in totally asynchronous distributed systemsPublished by Association for Computing Machinery (ACM) ,1987
- Reaching approximate agreement in the presence of faultsJournal of the ACM, 1986
- Impossibility of distributed consensus with one faulty processJournal of the ACM, 1985