(anti−Ωx × Σz)-based k-set Agreement Algorithms

Abstract : This paper considers the k-set agreement problem in a crash-prone asynchronous message passing system enriched with failure detectors. Two classes of failure detectors have been previously identified as necessary to solve asynchronous k-set agreement: the class anti-leader anti−Ωk and the weak-quorum class Σk. The paper investigates the families of failure detector (anti−Ωx)1xn and (Σz)1zn. It characterizes in an n processes system equipped with failure detectors anti−Ωx and Σz for which values of k, x and z k-set-agreement can be solved. While doing so, the paper (1) disproves previous conjunctures about the weakest failure detector to solve k-set-agreement in the asynchronous message passing model and, (2) introduces the first indulgent algorithm that tolerates a majority of processes failures.
Type de document :
Rapport
[Research Report] 2010, pp.19
Liste complète des métadonnées

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

https://hal.inria.fr/inria-00519606
Contributeur : Zohir Bouzid <>
Soumis le : lundi 20 septembre 2010 - 20:47:36
Dernière modification le : vendredi 31 août 2018 - 09:25:53
Document(s) archivé(s) le : mardi 21 décembre 2010 - 03:07:39

Fichiers

SigmaSA-TR.pdf
Fichiers produits par l'(les) auteur(s)

Identifiants

  • HAL Id : inria-00519606, version 1

Collections

Citation

Zohir Bouzid, Corentin Travers. (anti−Ωx × Σz)-based k-set Agreement Algorithms. [Research Report] 2010, pp.19. 〈inria-00519606〉

Partager

Métriques

Consultations de la notice

307

Téléchargements de fichiers

85