TY - JOUR
T1 - On the uncontended complexity of anonymous agreement
AU - Capdevielle, Claire
AU - Johnen, Colette
AU - Kuznetsov, Petr
AU - Milani, Alessia
N1 - Publisher Copyright:
© 2017, Springer-Verlag Berlin Heidelberg.
PY - 2017/12/1
Y1 - 2017/12/1
N2 - In this paper, we study uncontended complexity of anonymous k-set agreement algorithms, counting the number of memory locations used and the number of memory updates performed in operations that encounter no contention. We assume that in contention-free executions of a k-set agreement algorithm, only “fast” read and write operations are performed, and more expensive synchronization primitives, such as CAS, are only used when contention is detected. We call such concurrent implementations interval-solo-fast and derive the first nontrivial tight bounds on space complexity of anonymous interval-solo-fast k-set agreement.
AB - In this paper, we study uncontended complexity of anonymous k-set agreement algorithms, counting the number of memory locations used and the number of memory updates performed in operations that encounter no contention. We assume that in contention-free executions of a k-set agreement algorithm, only “fast” read and write operations are performed, and more expensive synchronization primitives, such as CAS, are only used when contention is detected. We call such concurrent implementations interval-solo-fast and derive the first nontrivial tight bounds on space complexity of anonymous interval-solo-fast k-set agreement.
U2 - 10.1007/s00446-017-0297-z
DO - 10.1007/s00446-017-0297-z
M3 - Article
AN - SCOPUS:85015658464
SN - 0178-2770
VL - 30
SP - 459
EP - 468
JO - Distributed Computing
JF - Distributed Computing
IS - 6
ER -