TU Berlin

Internet Network ArchitecturesPublications by Type: Articles


zur Navigation

Es gibt keine deutsche Übersetzung dieser Webseite.

Publications by Type: Journal and Magazine Articles

The Impossibility of Boosting Distributed Service Resilience
Zitatschlüssel AGKLR-IBDSR-11
Autor Attie, Paul and Guerraoui, Rachid and Kuznetsov, Petr and Lynch, Nancy and Rajsbaum, Sergio
Seiten 927–950
Jahr 2011
ISSN 0890-5401
DOI http://dx.doi.org/10.1016/j.ic.2010.07.005
Journal Information and Computation
Jahrgang 209
Nummer 6
Monat June
Verlag Elsevier
Zusammenfassung We study f-resilient services, which are guaranteed to operate as long as no more than f of the associated processes fail. We prove three theorems asserting the impossibility of boosting the resilience of such services. Our first theorem allows any connection pattern between processes and services but assumes these services to be atomic (linearizable) objects. This theorem says that no distributed system in which processes coordinate using f-resilient atomic objects and reliable registers can solve the consensus problem in the presence of f+1 undetectable process stopping failures. In contrast, we show that it is possible to boost the resilience of some systems solving problems easier than consensus: for example, the 2-set consensus problem is solvable for 2n processes and 2n-1 failures (i.e., wait-free) using n-process consensus services resilient to n-1 failures (wait-free). Our proof is short and self-contained. We then introduce the larger class of failure-oblivious services. These are services that cannot use information about failures, although they may behave more flexibly than atomic objects. An example of such a service is totally ordered broadcast. Our second theorem generalizes the first theorem and its proof to failure-oblivious services. Our third theorem allows the system to contain failure-aware services, such as failure detectors, in addition to failure-oblivious services. This theorem 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 using failure-aware services if arbitrary connection patterns between processes and services are allowed: consensus is solvable for any number of failures using only 1-resilient 2-process perfect failure detectors. As far as we know, this is the first time a unified framework has been used to describe both atomic and non-atomic objects, and the first time boosting analysis has been performed for services more general than atomic objects.
Link zur Publikation Download Bibtex Eintrag



Schnellnavigation zur Seite über Nummerneingabe