(anti-Omega^x × Σ_z) based k-set agreement algorithms

Zohir Bouzid 1 Corentin Travers 2, 3, *
* Auteur correspondant
1 NPA - Networks and Performance Analysis
LIP6 - Laboratoire d'Informatique de Paris 6
2 ASAP - As Scalable As Possible: foundations of large scale dynamic distributed systems
Inria Rennes – Bretagne Atlantique , IRISA-D1 - SYSTÈMES LARGE ÉCHELLE
Abstract : This paper considers the k-set agreement problem in a crashprone 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 )1≤x≤n and (Σz )1≤z≤n . 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 :
Communication dans un congrès
Chenyang Lu and Toshimitsu Masuzawa and Mohamed Mosbah. OPODIS, Dec 2010, Tozeur, Tunisia. Springer, 6490, pp.189-204, 2010, Lecture Notes in Computer Science. 〈10.1007/978-3-642-17653-1_16〉
Liste complète des métadonnées

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

https://hal.inria.fr/hal-00992778
Contributeur : Corentin Travers <>
Soumis le : lundi 19 mai 2014 - 11:51:09
Dernière modification le : mardi 16 janvier 2018 - 15:54:13
Document(s) archivé(s) le : lundi 10 avril 2017 - 23:42:49

Fichier

8.pdf
Fichiers produits par l'(les) auteur(s)

Identifiants

Citation

Zohir Bouzid, Corentin Travers. (anti-Omega^x × Σ_z) based k-set agreement algorithms. Chenyang Lu and Toshimitsu Masuzawa and Mohamed Mosbah. OPODIS, Dec 2010, Tozeur, Tunisia. Springer, 6490, pp.189-204, 2010, Lecture Notes in Computer Science. 〈10.1007/978-3-642-17653-1_16〉. 〈hal-00992778〉

Partager

Métriques

Consultations de la notice

647

Téléchargements de fichiers

117