In search of the holy grail: Looking for the weakest failure detector for wait-free set agreement

Abstract : Asynchronous failure detector-based set agreement algorithms proposed so far assume that all the processes participate in the algorithm. This means that (at least) the processes that do not crash propose a value and consequently execute the algorithm. It follows that these algorithms can block forever (preventing the correct processes from terminating) when there are correct processes that do not participate in the algorithm. This paper investigates the wait-free set agreement problem, i.e., the case where the correct participating processes have to decide a value whatever the behavior of the other processes (i.e., the processes that crash and the processes that are correct but do not participate in the algorithm). The paper presents a wait-free set agreement algorithm. This algorithm is based on a leader failure detector class that takes into account the notion of participating processes. Interestingly, this algorithm enjoys a first class property, namely, design simplicity. \\ Ce rapport propose un détecteur de faute candidat à être le plus faible détecteur de fautes pour résoudre l'accord ensembliste asynchrone et sans attente.
Type de document :
Rapport
[Research Report] PI 1811, 2006, pp.14
Liste complète des métadonnées

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

https://hal.inria.fr/inria-00089977
Contributeur : Anne Jaigu <>
Soumis le : vendredi 25 août 2006 - 14:05:11
Dernière modification le : mercredi 16 mai 2018 - 11:23:01
Document(s) archivé(s) le : lundi 5 avril 2010 - 23:16:19

Fichiers

Identifiants

  • HAL Id : inria-00089977, version 1

Collections

Citation

Michel Raynal, Corentin Travers. In search of the holy grail: Looking for the weakest failure detector for wait-free set agreement. [Research Report] PI 1811, 2006, pp.14. 〈inria-00089977〉

Partager

Métriques

Consultations de la notice

199

Téléchargements de fichiers

108