On set consensus numbers

It is conjectured that the only way a failure detector (FD) can help solving n-process tasks is by providing κ -set consensus for some κ ε {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 ofZieliński's result. We show that any FD that solves a colorless task that cannot be solved read-write κ -resiliently, also solves κ -set consensus. More generally, we show that every colorless task T can be characterized by its set consensus number: the largest κ ε {1, . . . , n} such that T is solvable (κ ε ?1)-resiliently. A task T with set consensus number κ is, in the failure detector sense, equivalent to κ -set consensus, i.e., a FD solves T if and only if it solves κ -set consensus.As a corollary,we determine the weakest FD for solving κ -set consensus in every environment, i.e., for all assumptions on when and where failures might occur.