Page Content
Publications by Type: Technical Reports
| Citation key | GK-FDTB-tr-03 |
|---|---|
| Author | Guerraoui, Rachid and Kouznetsov, Petr |
| Year | 2003 |
| Note | No. IC-EPFL ID:200348 / LPD-REPORT-2003-012 |
| Institution | École Polytechnique Fédérale de Lausanne, Switzerland |
| Abstract | 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. |
| Bibtex Type of Publication | Technical report |
Back [3]
r-03.pdf
ations/by_type/techreports/parameter/en/?no_cache=1&
;tx_sibibtex_pi1%5Bdownload_bibtex_uid%5D=197268&tx
_sibibtex_pi1%5Bcontentelement%5D=tt_content%3A361436
ations/by_type/techreports/parameter/en/
Zusatzinformationen / Extras
Quick Access:
Schnellnavigation zur Seite über Nummerneingabe
Auxiliary Functions
Copyright TU Berlin 2008