Anonymous Agreement: The Janus Algorithm

Zohir Bouzid 1 Pierre Sutra 2 Corentin Travers 3, *
* Auteur correspondant
1 NPA - Networks and Performance Analysis
LIP6 - Laboratoire d'Informatique de Paris 6
2 Regal - Large-Scale Distributed Systems and Applications
LIP6 - Laboratoire d'Informatique de Paris 6, Inria Paris-Rocquencourt
Abstract : The paper considers the consensus problem in an n-process shared-memory distributed system when processes are anonymous, i.e., they have no identities and are programmed identically. Janus, a new anonymous consensus algorithm that reaches decision after O( n) writes in every solo execution is presented. The set of values that can be proposed is unbounded and the algorithm tolerates an arbitrary number of crash failures. The algorithm relies on an anonymous eventual leader election mechanism. Furthermore, during solo executions in which a non-faulty process is elected since the beginning, the individual step complexity of Janus is O(n), matching a recent lower bound by Aspnes and Ellen (SPAA 2011). The algorithm is then extended to the case of homonymous systems in which c, 1 ≤ c ≤ n, identities are available. In every solo execution, the modified algorithm achieves O(n − c + log c/log log c) individual step complexity.
Type de document :
Communication dans un congrès
Antonio Fernández Anta and Giuseppe Lipari and Matthieu Roy. OPODIS'11 - 15th International Conference On Principles Of Distributed Systems, Dec 2011, Toulouse, France. Springer, 7109, pp.175-190, 2011, Lecture Notes in Computer Science. 〈10.1007/978-3-642-25873-2_13〉
Liste complète des métadonnées

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

https://hal.inria.fr/inria-00625704
Contributeur : Corentin Travers <>
Soumis le : jeudi 22 septembre 2011 - 14:02:28
Dernière modification le : vendredi 31 août 2018 - 09:25:54
Document(s) archivé(s) le : vendredi 23 décembre 2011 - 02:25:42

Fichiers

main-longversion.pdf
Fichiers produits par l'(les) auteur(s)

Identifiants

Collections

Citation

Zohir Bouzid, Pierre Sutra, Corentin Travers. Anonymous Agreement: The Janus Algorithm. Antonio Fernández Anta and Giuseppe Lipari and Matthieu Roy. OPODIS'11 - 15th International Conference On Principles Of Distributed Systems, Dec 2011, Toulouse, France. Springer, 7109, pp.175-190, 2011, Lecture Notes in Computer Science. 〈10.1007/978-3-642-25873-2_13〉. 〈inria-00625704〉

Partager

Métriques

Consultations de la notice

610

Téléchargements de fichiers

215