Show simple item record

dc.contributor.authorSabel, Laura S.en_US
dc.contributor.authorMarzullo, Keithen_US
dc.description.abstractIt was shown in 1985 that the {\em Consensus problem} cannot be solved in an asynchronous system if even a single crash failure can occur. In this paper, we show that there are other problems that cannot be solved in an asynchronous system, and for the same intuitive reason: it is impossible to distinguish a very slow processor from a crashed processor. However, these problems are harder than Consensus, in that there are contexts in which Consensus can be solved but these other problems cannot. More precisely, the weakest failure detector that is needed to solve these problems is a Perfect Failure Detector, which is strictly stronger than the weakest failure detector that is needed to solve Consensus. We use a formulation of the Election problem as the prototype for these problems that are harder than Consensus.en_US
dc.format.extent170378 bytes
dc.format.extent185592 bytes
dc.publisherCornell Universityen_US
dc.subjectcomputer scienceen_US
dc.subjecttechnical reporten_US
dc.titleElection Vs. Consensus in Asynchronous Systemsen_US
dc.typetechnical reporten_US

Files in this item


This item appears in the following Collection(s)

Show simple item record