| Publication Title: |
Impossibility of boosting distributed service resilience |
| Publication Author: |
Attie, Paul |
| Additional Authors: |
Rachid Guerraoui, Petr Kouznetsov, Nancy Lynch, Sergio Rajsbaum |
| LCS Document Number: |
MIT-LCS-TR-982 |
| Publication Date: |
2-25-2005 |
| LCS Group: |
Theory of Computation |
| Additional URL: |
|
| Abstract: |
| We prove two theorems saying that no distributed system in which
processes coordinate using reliable registers and f-resilient services
can solve the consensus problem in the presence of f+1 undetectable
process stopping failures. (A service is f-resilient if it is
guaranteed to operate as long as no more than f of the processes
connected to it fail.)
Our first theorem assumes that the given services are atomic objects,
and allows any connection pattern between processes and services. In
contrast, we show that it is possible to boost the resilience of
systems solving problems easier than consensus: the k-set consensus
problem is solvable for 2k-1 failures using 1-resilient consensus
services. The first theorem and its proof generalize to the larger
class of failure-oblivious services.
Our second theorem allows the system to contain failure-aware
services, such as failure detectors, in addition to failure-oblivious
services; however, it requires that each failure-aware service be
connected to all processes. Thus, f+1 process failures overall can
disable all the failure-aware services. In contrast, it is possible
to boost the resilience of a system solving consensus if arbitrary
patterns of connectivity are allowed between processes and
failure-aware services: consensus is solvable for any number of
failures using only 1-resilient 2-process perfect failure detectors. |
| To obtain this publication: |
|
|
|
To purchase a printed copy of this publication please contact
MIT
Document Services.
|