Thumbnail
Access Restriction
Subscribed

Author Chandra, Tushar Deepak ♦ Hadzilacos, Vassos ♦ Toueg, Sam
Source ACM Digital Library
Content type Text
Publisher Association for Computing Machinery (ACM)
File Format PDF
Copyright Year ©1996
Language English
Subject Domain (in DDC) Computer science, information & general works ♦ Data processing & computer science
Subject Keyword Byzantine Generals' problem ♦ Agreement problem ♦ Asynchronous systems ♦ Atomic broadcast ♦ Commit problem ♦ Consensus problem ♦ Crash failures ♦ Failure detection ♦ Fault-tolerance ♦ Message passing ♦ Partial synchrony ♦ Processor failures
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 $\textit{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.
ISSN 00045411
Age Range 18 to 22 years ♦ above 22 year
Educational Use Research
Education Level UG and PG
Learning Resource Type Article
Publisher Date 1996-07-01
Publisher Place New York
e-ISSN 1557735X
Journal Journal of the ACM (JACM)
Volume Number 43
Issue Number 4
Page Count 38
Starting Page 685
Ending Page 722


Open content in new tab

   Open content in new tab
Source: ACM Digital Library