Cornell University
Library
Cornell UniversityLibrary

eCommons

Help
Log In(current)
  1. Home
  2. Cornell Computing and Information Science
  3. Computer Science
  4. Computer Science Technical Reports
  5. Election Vs. Consensus in Asynchronous Systems

Election Vs. Consensus in Asynchronous Systems

File(s)
95-1488.pdf (166.38 KB)
95-1488.ps (181.24 KB)
Permanent Link(s)
https://hdl.handle.net/1813/7146
Collections
Computer Science Technical Reports
Author
Sabel, Laura S.
Marzullo, Keith
Abstract

It 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.

Date Issued
1995-02
Publisher
Cornell University
Keywords
computer science
•
technical report
Previously Published as
http://techreports.library.cornell.edu:8081/Dienst/UI/1.0/Display/cul.cs/TR95-1488
Type
technical report

Site Statistics | Help

About eCommons | Policies | Terms of use | Contact Us

copyright © 2002-2026 Cornell University Library | Privacy | Web Accessibility Assistance