TY - GEN
T1 - Anonymous agreement
T2 - 15th International Conference on Principles of Distributed Systems, OPODIS 2011
AU - Bouzid, Zohir
AU - Sutra, Pierre
AU - Travers, Corentin
PY - 2011/12/26
Y1 - 2011/12/26
N2 - 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(√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(√n - c + 1 + log c/log log c) individual write complexity O(n - c + log c/log log c) and individual step complexity.
AB - 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(√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(√n - c + 1 + log c/log log c) individual write complexity O(n - c + log c/log log c) and individual step complexity.
KW - Anonymity
KW - asynchronous shared memory
KW - consensus
KW - failure detectors
KW - homonym processes
KW - indulgent algorithms
U2 - 10.1007/978-3-642-25873-2_13
DO - 10.1007/978-3-642-25873-2_13
M3 - Conference contribution
AN - SCOPUS:84055222632
SN - 9783642258725
T3 - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
SP - 175
EP - 190
BT - Principles of Distributed Systems - 15th International Conference, OPODIS 2011, Proceedings
Y2 - 13 December 2011 through 16 December 2011
ER -