TU Berlin

Internet Network ArchitecturesPublications by Type: Conference and Workshop Papers

Inhalt

zur Navigation

Es gibt keine deutsche Übersetzung dieser Webseite.

Publications by Type: Conference and Workshop Publications

see also conference papers, workshop papers, demos, and posters. (under construction)

The Impossibility of Boosting Distributed Service Resilience
Zitatschlüssel AGKLR-IBDSR-05
Autor Attie, Paul and Guerraoui, Rachid and Kouznetsov, Petr and Lynch, Nancy and Rajsbaum, Sergio
Buchtitel Proceedings of the 25th IEEE International Conference on Distributed Computing Systems (ICDCS '05)
Seiten 39–48
Jahr 2005
ISBN 0-7695-2331-5
ISSN 1063-6927
DOI http://dx.doi.org/10.1109/ICDCS.2005.79
Ort Columbus, OH, USA
Monat June
Zusammenfassung 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, 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.
Link zur Publikation Download Bibtex Eintrag

Navigation

Direktzugang

Schnellnavigation zur Seite über Nummerneingabe