TY - GEN
T1 - On the uncontended complexity of anonymous consensus
AU - Capdevielle, Claire
AU - Johnen, Colette
AU - Kuznetsov, Petr
AU - Milani, Alessia
N1 - Publisher Copyright:
© Claire Capdevielle, Colette Johnen, Petr Kuznetsov, and Alessia Milani.
PY - 2016/9/1
Y1 - 2016/9/1
N2 - Consensus is one of the central distributed abstractions. By enabling a collection of processes to agree on one of the values they propose, consensus can be used to implement any generic replicated service in a consistent and fault-tolerant way. In this paper, we study uncontended complexity of anonymous consensus algorithms, counting the number of memory locations used and the number of memory updates performed in operations that encounter no contention. We assume that contention-free operations on a consensus object perform "fast" reads and writes, and resort to more expensive synchronization primitives, such as CAS, only when contention is detected. We call such concurrent implementations intervalsolo-fast and derive one of the first nontrivial tight bounds on space complexity of anonymous interval-solo-fast consensus.
AB - Consensus is one of the central distributed abstractions. By enabling a collection of processes to agree on one of the values they propose, consensus can be used to implement any generic replicated service in a consistent and fault-tolerant way. In this paper, we study uncontended complexity of anonymous consensus algorithms, counting the number of memory locations used and the number of memory updates performed in operations that encounter no contention. We assume that contention-free operations on a consensus object perform "fast" reads and writes, and resort to more expensive synchronization primitives, such as CAS, only when contention is detected. We call such concurrent implementations intervalsolo-fast and derive one of the first nontrivial tight bounds on space complexity of anonymous interval-solo-fast consensus.
KW - Consensus
KW - Interval contention
KW - Lower bounds
KW - Solo-fast
KW - Space and time complexity
U2 - 10.4230/LIPIcs.OPODIS.2015.12
DO - 10.4230/LIPIcs.OPODIS.2015.12
M3 - Conference contribution
AN - SCOPUS:85013441129
T3 - Leibniz International Proceedings in Informatics, LIPIcs
SP - 12.1-12.16
BT - 19th International Conference on Principles of Distributed Systems, OPODIS 2015
A2 - Anceaume, Emmanuelle
A2 - Cachin, Christian
A2 - Potop-Butucaru, Maria
PB - Schloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing
T2 - 19th International Conference on Principles of Distributed Systems, OPODIS 2015
Y2 - 14 December 2015 through 17 December 2015
ER -