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. The Weakest Failure Detector for Solving Consensus

The Weakest Failure Detector for Solving Consensus

File(s)
94-1426.pdf (4.38 MB)
94-1426.ps (788.99 KB)
Permanent Link(s)
https://hdl.handle.net/1813/6208
Collections
Computer Science Technical Reports
Author
Chandra, Tushar Deepak
Hadzilacos, Vassos
Toueg, Sam
Abstract

We determine what information about failures is necessary and sufficient to solve Consensus in asynchronous distributed systems subject to crash failures. In [CT91], we proved that $\Diamond\cal 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 $\Diamond\cal W$. Thus, $\Diamond\cal W$ is indeed the weakest failure detector for solving Consensus in asynchronous systems with a majority of correct processes.

Date Issued
1994-05
Publisher
Cornell University
Keywords
computer science
•
technical report
Previously Published as
http://techreports.library.cornell.edu:8081/Dienst/UI/1.0/Display/cul.cs/TR94-1426
Type
technical report

Site Statistics | Help

About eCommons | Policies | Terms of use | Contact Us

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