A realistic look at failure detectors
- 25 June 2003
- proceedings article
- Published by Institute of Electrical and Electronics Engineers (IEEE)
- p. 345-353
- https://doi.org/10.1109/dsn.2002.1028919
Abstract
This paper shows that, in an environment where we do not bound the number of faulty processes, the class P of Perfect failure detectors is the weakest (among realistic failure detectors) to solve fundamental agreement problems like uniform consensus, atomic broadcast, and terminating reliable broadcast (also called Byzantine Generals). Roughly speaking, in this environment, we collapse the Chandra-Toueg failure detector hierarchy, by showing that P ends up being the only class to solve those agreement problems.This contributes in explaining why most reliable distributed systems we know of do rely on some group membership service that precisely aims at emulating P. As an interesting side effect of our work, we show that, in our general environment, uniform consensus is strictly harder than consensus, and we revisit the view that uniform consensus and atomic broadcast are strictly weaker than terminating reliable broadcast.Keywords
This publication has 11 references indexed in Scilit:
- On the relationship between the atomic commitment and consensus problemsPublished by Springer Nature ,2006
- Fail-aware failure detectorsPublished by Institute of Electrical and Electronics Engineers (IEEE) ,2002
- Primary component asynchronous group membership as an instance of a generic agreement frameworkPublished by Institute of Electrical and Electronics Engineers (IEEE) ,2002
- The timely computing base: Timely actions in the presence of uncertain timelinessPublished by Institute of Electrical and Electronics Engineers (IEEE) ,2002
- A knowledge-theoretic analysis of uniform distributed coordination and failure detectorsPublished by Association for Computing Machinery (ACM) ,1999
- 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
- The Byzantine Generals ProblemACM Transactions on Programming Languages and Systems, 1982