Paper Info
Title
Anonymous agreement: the janus algorithm
Abstract
We consider 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. We present Janus, a new anonymous consensus algorithm that reaches decision after $O(\sqrt{n})$ writes in every solo execution. 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 system in which c, 1≤c≤n, identities are available. In every solo execution, the modified algorithm achieves $O(\sqrt{n-c+1} + \frac{\log{c}}{\log{\log{c}}})$ individual write complexity and $O(n-c+\frac{\log{c}}{\log{\log{c}}})$ individual step complexity.
Year
DOI
Venue
2011
10.1007/978-3-642-25873-2_13
OPODIS
Keywords
Field
DocType
anonymous eventual leader election,janus algorithm,arbitrary number,modified algorithm,anonymous agreement,present janus,consensus problem,crash failure,individual step complexity,new anonymous consensus algorithm,solo execution,homonymous system,anonymity,consensus
Leader election,Consensus,Consensus algorithm,Janus,Computer science,Upper and lower bounds,Algorithm,Real-time computing,Anonymity,Distributed computing
Conference
Volume
ISSN
Citations 
7109
0302-9743
3
PageRank 
References 
Authors
0.42
27
3
Name
Order
Citations
PageRank
Zohir Bouzid114612.63
Pierre Sutra215214.73
Corentin Travers337126.30