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 thatW, 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 W. Thus, W is 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