# On the Computability Power and the Robustness of Set Agreement-oriented Failure Detector Classes

Abstract : This paper considers the failure detector classes that have been considered in the literature to solve $k$-set agreement, and studies their relative power. It shows that the family of failure detector classes $\Diamond {\cal S}_x$ ($0\leq x \leq n$), and $\Diamond \psi^y$ ($0\leq y \leq n$), can be added'' to provide a failure detector of the class $\Omega^z$ (a generalization of $\Omega$). It also characterizes the power of such an addition'', namely, $\Diamond {\cal S}_x +\Diamond \psi^y \leadsto \Omega^z \Leftrightarrow x+y+z>t+1$, where $t$ is the maximum number of processes that can crash in a run. As an example, the paper shows that, while $\Diamond {\cal S}_{t}$ allows solving 2-set agreement (and not consensus) and $\Diamond \psi^{1}$ allows solving $t$-set agreement (but not $(t-1)$-set agreement), a system with failure detectors of both classes can solve consensus. More generally, the paper studies the failure detector classes $\Diamond {\cal S}_x$, $\Diamond \psi^y$ and $\Omega^z$, and shows which reductions among these classes are possible and which are not.The paper presents also a message-passing $\Omega^k$-based $k$-set agreement protocol. In that sense, it can be seen as a step toward the characterization of the weakest failure detector class that allows solving the $k$-set agreement problem.
Keywords :
Document type :
Reports
Domain :

Cited literature [30 references]

https://hal.inria.fr/inria-00107220
Contributor : Anne Jaigu <>
Submitted on : Tuesday, October 17, 2006 - 4:33:54 PM
Last modification on : Thursday, January 7, 2021 - 4:18:18 PM
Long-term archiving on: : Tuesday, April 6, 2010 - 8:02:21 PM

### Identifiers

• HAL Id : inria-00107220, version 1

### Citation

Achour Mostefaoui, Sergio Rajsbaum, Michel Raynal, Corentin Travers. On the Computability Power and the Robustness of Set Agreement-oriented Failure Detector Classes. [Research Report] PI 1819, 2006, pp.31. ⟨inria-00107220⟩

Record views