HAL will be down for maintenance from Friday, June 10 at 4pm through Monday, June 13 at 9am. More information
Skip to Main content Skip to Navigation

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.
Complete list of metadata

Cited literature [30 references]  Display  Hide  Download

Contributor : Anne Jaigu Connect in order to contact the contributor
Submitted on : Tuesday, October 17, 2006 - 4:33:54 PM
Last modification on : Tuesday, June 15, 2021 - 4:13:23 PM
Long-term archiving on: : Tuesday, April 6, 2010 - 8:02:21 PM


  • HAL Id : inria-00107220, version 1


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


Files downloads