Skip to Main content Skip to Navigation
Conference papers

Anonymous Agreement: The Janus Algorithm

Zohir Bouzid 1 Pierre Sutra 2 Corentin Travers 3, * 
* Corresponding author
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.
Complete list of metadata

Cited literature [28 references]  Display  Hide  Download
Contributor : Corentin Travers Connect in order to contact the contributor
Submitted on : Thursday, September 22, 2011 - 2:02:28 PM
Last modification on : Saturday, June 25, 2022 - 10:32:39 AM
Long-term archiving on: : Friday, December 23, 2011 - 2:25:42 AM


Files produced by the author(s)



Zohir Bouzid, Pierre Sutra, Corentin Travers. Anonymous Agreement: The Janus Algorithm. OPODIS'11 - 15th International Conference On Principles Of Distributed Systems, Dec 2011, Toulouse, France. pp.175-190, ⟨10.1007/978-3-642-25873-2_13⟩. ⟨inria-00625704⟩



Record views


Files downloads