direkt zum Inhalt springen

direkt zum Hauptnavigationsmenü

Sie sind hier

TU Berlin

Inhalt des Dokuments

Es gibt keine deutsche Übersetzung dieser Webseite.

Marco Caninis's Publications

On Set Consensus Numbers
Zitatschlüssel GK-OSCN-11
Autor Gafni, Eli and Kuznetsov, Petr
Seiten 149-163
Jahr 2011
ISSN 0178-2770
Online ISSN 1432-0452
DOI http://dx.doi.org/10.1007/s00446-011-0142-8
Adresse Berlin / Heidelberg, Germany
Journal Distributed Computing
Jahrgang 24
Nummer 3–4
Notiz Special Issue on DISC 2009
Verlag Springer
Zusammenfassung It is conjectured that the only way a failure detector (FD) can help solving n-process tasks is by providing k-set consensus for some k∈1...n among all the processes. It was recently shown by Zieliński that any FD that allows for solving a given n-process task that is unsolvable read-write wait-free, also solves (n−1)-set consensus. In this paper, we provide a generalization of Zieliński’s result. We show that any FD that solves a colorless task that cannot be solved read-write k-resiliently, also solves k-set consensus. More generally, we show that every colorless task T can be characterized by its set consensus number: the largest k∈1...n such that T is solvable (k−1)-resiliently. A task T with set consensus number k is, in the failure detector sense, equivalent to k-set consensus, i.e., a FD solves T if and only if it solves k-set consensus. As a corollary, we determine the weakest FD for solving k-set consensus in every environment, i.e., for all assumptions on when and where failures might occur.
Download Bibtex Eintrag

Zusatzinformationen / Extras

Direktzugang:

Schnellnavigation zur Seite über Nummerneingabe