Journal of the Association for Computing Machinery, Vol. 43, No. 2, March 1996, pp. 225–267.

Unreliable Failure Detectors for Reliable Distributed Systems

TUSHAR DEEPAK CHANDRA

AND

SAM TOUEG

Abstract. We introduce the concept of unreliable failure detectors and study how they can be used to solve Consensus in asynchronous systems with crash failures. We characterise unreliable failure detectors in terms of two properties—completeness and accuracy. We show that Consensus can be solved even with unreliable failure detectors that make an infinite number of mistakes, and determine which ones can be used to solve Consensus despite any number of crashes, and which ones require a majority of correct processes. We prove that Consensus and Atomic Broadcast are reducible to each other in asynchronous systems with crash failures; thus, the above results also apply to Atomic Broadcast. A companion paper shows that one of the failure detectors introduced here is the weakest failure detector for solving Consensus [Chandra et al. 1992].

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.