direkt zum Inhalt springen

direkt zum Hauptnavigationsmenü

Sie sind hier

TU Berlin

Inhalt des Dokuments

Es gibt keine deutsche Übersetzung dieser Webseite.

All publications

Failure Detectors as Type Boosters
Zitatschlüssel GK-FDATB-08
Autor Guerraoui, Rachid and Kouznetsov, Petr
Seiten 343–358
Jahr 2008
ISSN 0178-2770
DOI http://dx.doi.org/10.1007/s00446-007-0043-z
Adresse Berlin / Heidelberg, Germany
Journal Distributed Computing Journal (DC)
Jahrgang 20
Nummer 5
Monat February
Verlag Springer
Zusammenfassung The power of an object type T can be measured as the maximum number n of processes that can solve consensus using only objects of T and registers. This number, denoted cons(T), is called the consensus power of T. This paper addresses the question of the weakest failure detector to solve consensus among a number k>n of processes that communicate using shared objects of a type T with consensus power n. In other words, we seek for a failure detector that is sufficient and necessary to ``boost'' the consensus power of a type T from n to k. It was shown in Neiger (Proceedings of the 14th annual ACM symposium on principles of distributed computing (PODC), pp. 100–109, 1995) that a certain failure detector, denoted Ω_n , is sufficient to boost the power of a type T from n to k, and it was conjectured that Ω_n was also necessary. In this paper, we prove this conjecture for one-shot deterministic types. We first show that, for any one-shot deterministic type T with cons(T)≤n, Ω_n is necessary to boost the power of T from n to n+1. Then we go a step further and show that Ω_n is also the weakest to boost the power of (n+1)-ported one-shot deterministic types from n to any k>n. Our result generalizes, in a precise sense, the result of the weakest failure detector to solve consensus in asynchronous message-passing systems (Chandra et al. in J ACM 43(4):685–722, 1996). As a corollary, we show that Ω_t is the weakest failure detector to boost the resilience level of a distributed shared memory system, i.e., to solve consensus among n>t processes using (t−1)-resilient objects of consensus power t.
Link zur Publikation Download Bibtex Eintrag

Zusatzinformationen / Extras

Direktzugang:

Schnellnavigation zur Seite über Nummerneingabe