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.
Type de document :
Rapport
[Research Report] PI 1819, 2006, pp.31
Liste complète des métadonnées

Littérature citée [30 références]  Voir  Masquer  Télécharger

https://hal.inria.fr/inria-00107220
Contributeur : Anne Jaigu <>
Soumis le : mardi 17 octobre 2006 - 16:33:54
Dernière modification le : mardi 24 avril 2018 - 13:52:05
Document(s) archivé(s) le : mardi 6 avril 2010 - 20:02:21

Fichiers

Identifiants

  • 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〉

Partager

Métriques

Consultations de la notice

345

Téléchargements de fichiers

51