-----------------------------------------------------------------------
TDS Seminar TDS Seminar TDS Seminar TDS Seminar TDS Seminar TDS Seminar
-----------------------------------------------------------------------

Title:   Boosting Fault-Tolerance in Asynchronous Message Passing 
         Systems is Impossible
Speaker: Paul Attie

Place:   NE43-308
Time:    1-2:30pm
Date:    Dec. 13, 2002

We show that it is impossible to ``boost'' the level of
fault-tolerance of a system solving consensus by combining less
fault-tolerant components into a more fault-tolerant system. To do
this, we consider an asynchronous distributed computing model in which
a known set of processes interact in two ways: by using reliable
point-to-point channels, and by accessing shared services.  Each of
the shared services is connected to a subset of all the processes.

Our boosting impossibility result is: for any $f \geq 1$, the
consensus problem is unsolvable in this model in the presence of up to
$f$ process stopping failures, if each of the shared services is
assumed to tolerate only $f-1$ process failures.  This result holds
regardless of the types of the shared services and the pattern of
connectivity of processes and services.  In particular, it is
impossible to construct a protocol to solve the consensus problem for
$f$ process failures using any number of consensus services that
tolerate $f-1$ process failures.

Interestingly, it is possible to boost the level of a system solving
problems easier than consensus. For example, we show that the
$k$-consensus problem is solvable for $2k-1$ failures using only
(consensus) services that tolerate only $1$ failure apiece.

Joint work with Nancy Lynch and Sergio Rajsbaum

-----------------------------------------------------------------------