Show simple item record

dc.contributor.authorChandra, Tushar Deepaken_US
dc.description.abstractIt is well-known that several fundamental problems of fault-tolerant distributed computing, such as Consensus and Atomic Broadcast, cannot be solved in asynchronous systems with crash failures. These impossibility results stem from the lack of reliable failure detection in such systems. To circumvent such impossibility results, we introduce the concept of unreliable failure detectors that can make mistakes, and study the problem of using them to solve Consensus (and Atomic Broadcast). It is easy to solve Consensus using a "perfect" failure detector (one that does not make mistakes). But is perfect failure detection necessary to solve Consensus? We show that Consensus is solvable with unreliable failure detectors, even if they make an infinite number of mistakes. This leads to the following question: What is the "weakest" failure detector for solving Consensus? We introduce a notion of algorithmic reducibility that allows us to compare seemingly incomparable failure detectors. Using this concept, we show that one of the failure detectors that we introduce here is indeed the weakest failure detector for solving Consensus in asynchronous systems with a majority of correct processes. We also show that Consensus and Atomic Broadcast are equivalent in asynchronous systems. Thus all our results regarding the solvability of Consensus using failure detectors, apply to Atomic Broadcast as well. The work in this thesis was funded by an IBM graduate fellowship and grants from NSF, DARPA/NASA, the IBM Endicott Programming Laboratory, Siemens Corp. and the Natural Sciences and Engineering Research Council of Canada.en_US
dc.format.extent9503219 bytes
dc.format.extent1705377 bytes
dc.publisherCornell Universityen_US
dc.subjectcomputer scienceen_US
dc.subjecttechnical reporten_US
dc.titleUnreliable Failure Detectors for Asynchronous Distributed Systemsen_US
dc.typetechnical reporten_US

Files in this item


This item appears in the following Collection(s)

Show simple item record