caa a22 4500 44535495X CHVBK 20180317142857.0 cr unu---uuuuu 170323e20111101xx s 000 0 eng 10.1007/s00446-011-0142-8 doi (NATIONALLICENCE)springer-10.1007/s00446-011-0142-8 On set consensus numbers [Elektronische Daten] [Eli Gafni, Petr Kuznetsov] 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\in\{1,\ldots,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 $${\mathcal{T}}$$ can be characterized by its set consensus number: the largest $${k\in\{1,\ldots,n\}}$$ such that $${\mathcal{T}}$$ is solvable (k − 1)-resiliently. A task $${\mathcal{T}}$$ with set consensus number k is, in the failure detector sense, equivalent to k-set consensus, i.e., a FD solves $${\mathcal{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. Springer-Verlag, 2011 Gafni Eli Computer Science Department, University of California, Los Angeles, CA, USA aut Kuznetsov Petr TU Berlin/Deutsche Telekom Laboratories, Berlin, Germany aut Distributed Computing Springer-Verlag 24/3-4(2011-11-01), 149-163 0178-2770 24:3-4<149 2011 24 446 https://doi.org/10.1007/s00446-011-0142-8 text/html Onlinezugriff via DOI 1 research-article jats NATIONALLICENCE 856 40 https://doi.org/10.1007/s00446-011-0142-8 text/html Onlinezugriff via DOI NATIONALLICENCE 700 1- Gafni Eli Computer Science Department, University of California, Los Angeles, CA, USA aut NATIONALLICENCE 700 1- Kuznetsov Petr TU Berlin/Deutsche Telekom Laboratories, Berlin, Germany aut NATIONALLICENCE 773 0- Distributed Computing Springer-Verlag 24/3-4(2011-11-01), 149-163 0178-2770 24:3-4<149 2011 24 446 Metadata rights reserved Springer special CC-BY-NC licence nationallicence BK010053 XK010053 XK010000 NATIONALLICENCE NATIONALLICENCE NL-springer