direkt zum Inhalt springen

direkt zum Hauptnavigationsmenü

Sie sind hier

TU Berlin

Page Content

Petr Kuznetsov's Publications

On Set Consensus Numbers
Citation key GK-OSCN-11
Author Gafni, Eli and Kuznetsov, Petr
Pages 149-163
Year 2011
ISSN 0178-2770
Online ISSN 1432-0452
DOI http://dx.doi.org/10.1007/s00446-011-0142-8
Address Berlin / Heidelberg, Germany
Journal Distributed Computing
Volume 24
Number 3–4
Note Special Issue on DISC 2009
Publisher Springer
Abstract 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 entry

Zusatzinformationen / Extras

Quick Access:

Schnellnavigation zur Seite über Nummerneingabe

Auxiliary Functions