AbstractWe 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 \diamond W, 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 \diamond W. Thus, \diamond W is indeed the weakest failure detector for solving Consensus in asynchronous systems with a majority of correct processes.
The abstract is also available as a LaTeX file, a DVI file, or a PostScript file.
Categories and Subject Descriptors: C.2.4 [Computer-Communication Networks]: Distributed Systems -- distributed applications, distributed databases, network operating systems; C.4 [Performance of Systems]; D.1.3 [Programming Techniques]: Concurrent Programming -- distributed programming; D.4.5 [Operating Systems]: Reliability -- fault-tolerance; F.1.1 [Computation by Abstract Devices]: Models of Computation -- automata, relations among models; F.1.2 [Computation by Abstract Devices]: Modes of Computation -- parallelism and concurrency; H.2.4 [Database Management]: Systems -- concurrency, distributed systems, transaction processing
General Terms: Algorithms, Reliability, Theory
Additional Key Words and Phrases: agreement problem, asynchronous systems, atomic broadcast, \emph{Byzantine Generals'} problem, commit problem, consensus problem, crash failures, failure detection, fault-tolerance, message passing, partial synchrony, processor failures
Selected papers that cite this one
- Francis Chu. Reducing Omega to \Diamond W. Information Processing Letters, 67(6):289-293, 30 September 1998.
- Louise E. Moser and P. M. Melliar-Smith. Byzantine-resistant total ordering algorithms. Accepted for publication in Information and Computation. Final manuscript received for publication October 29, 1998.
Selected references
- Hagit Attiya, Amotz Bar-Noy, Danny Dolev, Daphne Koller, David Peleg, and Rüdiger Reischuk. Achievable cases in an asynchronous environment (extended abstract). In 28th Annual Symposium on Foundations of Computer Science, pages 337-346, Los Angeles, California, 12-14 October 1987. IEEE.
- Danny Dolev, Cynthia Dwork, and Larry Stockmeyer. On the minimal synchronism needed for distributed consensus. Journal of the ACM, 34(1):77-97, January 1987.
- Danny Dolev, Nancy A. Lynch, Shlomit S. Pinter, Eugene W. Stark, and William E. Weihl. Reaching approximate agreement in the presence of faults. Journal of the ACM, 33(3):499-516, July 1986.
- Cynthia Dwork, Nancy Lynch, and Larry Stockmeyer. Consensus in the presence of partial synchrony. Journal of the ACM, 35(2):288-323, April 1988.
- Michael J. Fischer, Nancy A. Lynch, and Michael S. Paterson. Impossibility of distributed consensus with one faulty process. Journal of the ACM, 32(2):374-382, April 1985.