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