Journal of the Association for Computing Machinery, Vol. 43, No. 4, July 1996, pp. 685–722.

The Weakest Failure Detector for Solving Consensus

TUSHAR DEEPAK CHANDRA

VASSOS HADZILACOS

AND

SAM TOUEG

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 ⋄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 ⋄W. Thus, ⋄W is indeed the weakest failure detector for solving Consensus in asynchronous systems with a majority of correct processes.

Categories and Subject Descriptors. C.2.4 [Computer-Communication Networks]: Distributed Systems—distributed applications; distributed databases; network operating systems; C.4 [Performance of Systems]—reliability, availability, and serviceability; 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, Byzantine Generals’ problem, commit problem, consensus problem, crash failures, failure detection, fault-tolerance, message passing, partial synchrony, processor failures

Copyright 1996 by ACM, Inc. Permission to make digital or hard copies of part or all of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or direct commercial advantage and that copies bear this notice and the full citation on the first page. Copyrights for components of this work owned by others than ACM must be honored. Abstracting with credit is permitted. To copy otherwise, to republish, to post on servers, or to redistribute to lists, requires prior specific permission and/or a fee. Request permissions from Publications Dept, ACM Inc., fax +1 (212) 869-0481, or permissions@acm.org.