TU Berlin

Internet Network ArchitecturesMarco Canini's Publications


zur Navigation

Es gibt keine deutsche Übersetzung dieser Webseite.

Marco Caninis's Publications

On Failure Detectors and Type Boosters
Zitatschlüssel GK-FDTB-03
Autor Guerraoui, Rachid and Kouznetsov, Petr
Buchtitel 17th International Conference on Distributed Computing (DISC)
Seiten 292-305
Jahr 2003
ISBN 978-3-540-20184-7
ISSN 0302-9743
DOI http://dx.doi.org/10.1007/978-3-540-39989-6_21
Ort Sorrento, Italy
Adresse Berlin / Heidelberg, Germany
Jahrgang 2848
Verlag Springer
Serie Lecture Notes in Computer Science (LNCS)
Zusammenfassung The power of a set S of object types can be measured as the maximum number n of processes that can solve consensus using only types in S and registers. This number, denoted by h^r_m(S), is called the consensus power of S. The use of failure detectors can however ``boost'' the consensus power of types. This paper addresses the weakest failure detector type booster question, which consists in determining the weakest failure detector D such that, for any set S of types with h_m^r(S)=n, h_m^r(S;D)=n+1. We consider the failure detector Ω_n (introduced in (Neiger, 1995)) which outputs, at each process, a set of at most n processes so that, eventually, all correct processes detect the same set of processes that includes at least one correct process. We prove that Ω_n is the weakest failure detector type booster for deterministic one-shot types. As an interesting corollary of our result, we show that Ω_f is the weakest failure detector to boost the power of (f-1)-resilient objects solving consensus.
Download Bibtex Eintrag



Schnellnavigation zur Seite über Nummerneingabe