MIME-Version: 1.0 Server: CERN/3.0 Date: Sunday, 24-Nov-96 22:05:04 GMT Content-Type: text/html Content-Length: 1788 Last-Modified: Friday, 27-Oct-95 20:23:32 GMT The Weakest Failure Detector for Solving Consensus

The Weakest Failure Detector for Solving Consensus

by Tushar Deepak Chandra, Vassos Hadzilacos and Sam Toueg. This paper has 42 pages. To get a postscript copy, click here (or here to get it from the mirror site). A preliminary version of this paper appeared in PODC92.

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 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.
Research supported by an IBM graduate fellowship, NSF grants CCR-8901780 and CCR-9102231, DARPA/NASA Ames grant NAG-2-593, grants from the IBM Endicott Programming Laboratory and Siemens Corp, and a grant from the Natural Sciences and Engineering Research Council of Canada.
Maintained by tushar@watson.ibm.com