http:^^www.cs.cornell.edu^info^people^chandra^weakestfd.html

来自「This data set contains WWW-pages collect」· HTML 代码 · 共 44 行

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

<title>The Weakest Failure Detector for Solving Consensus</title>
<!-- Changed by: Tushar Deepak Chandra, 27-Oct-1995 -->
<h1>The Weakest Failure Detector for Solving Consensus</h1>
by
<!WA0><!WA0><!WA0><!WA0><!WA0><!WA0><!WA0><!WA0><a href="http://www.cs.cornell.edu/Info/People/chandra/home.html">Tushar Deepak Chandra</a>,
<!WA1><!WA1><!WA1><!WA1><!WA1><!WA1><!WA1><!WA1><a href="http://www.cdf.toronto.edu:/DCS/CSRI/Hadzilacos.html">Vassos
Hadzilacos</a> and
<!WA2><!WA2><!WA2><!WA2><!WA2><!WA2><!WA2><!WA2><a href="http://www.cs.cornell.edu/Info/People/sam/sam.html">
Sam Toueg</a>.
This paper has 42 pages.  To get a postscript copy, click
<!WA3><!WA3><!WA3><!WA3><!WA3><!WA3><!WA3><!WA3><a href="ftp://ftp.cs.cornell.edu/pub/chandra/failure.detectors.weakest.ps.Z">here</a>
(or <!WA4><!WA4><!WA4><!WA4><!WA4><!WA4><!WA4><!WA4><a href="ftp://ftp.db.toronto.edu/pub/vassos/failure.detectors.weakest.ps.Z">here</a>
to get it from the mirror site).  A preliminary version of this paper appeared
in PODC92.
<h2>Abstract</h2>
We determine what information about failures is necessary and sufficient to
	solve Consensus in asynchronous distributed systems subject to crash
	failures.
In
<!WA5><!WA5><!WA5><!WA5><!WA5><!WA5><!WA5><!WA5><a href="http://www.cs.cornell.edu/Info/People/chandra/UnreliableFD.html">[CT91]</a>,
we proved that <i>W</i>, 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 <i>W</i>.
Thus, <i>W</i> is indeed the weakest failure detector for solving Consensus
	in asynchronous systems with a majority of correct processes.
<hr>
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.
<hr>
<i>Maintained by <!WA6><!WA6><!WA6><!WA6><!WA6><!WA6><!WA6><!WA6><a href="http://www.cs.cornell.edu/Info/People/chandra/home.html">[e-mail]</a></i>