Efficient Randomized DCAS

1 WIDE - the World Is Distributed Exploring the tension between scale and coordination
Inria Rennes – Bretagne Atlantique , IRISA-D1 - SYSTÈMES LARGE ÉCHELLE
Abstract : Double Compare-And-Swap (DCAS) is a tremendously useful synchronization primitive, which is also notoriously difficult to implement efficiently from objects that are provided by hardware. We present a randomized implementation of DCAS with $O(\log n)$ expected amortized step complexity against the oblivious adversary, where $n$ is the number of processes in the system. This is the only algorithm to-date that achieves sub-linear step complexity. We achieve that by first implementing two novel algorithms as building blocks. One is a mechanism that allows processes to repeatedly agree on a random value among multiple proposed ones, and the other one is a restricted bipartite version of DCAS.
Keywords :
Document type :
Conference papers
Domain :

https://hal.inria.fr/hal-03195692
Contributor : George Giakkoupis <>
Submitted on : Monday, April 12, 2021 - 9:08:50 AM
Last modification on : Friday, April 16, 2021 - 9:58:10 AM

File

DCAS.pdf
Files produced by the author(s)

Identifiers

• HAL Id : hal-03195692, version 1

Citation

George Giakkoupis, Mehrdad Jafari Giv, Philipp Woelfel. Efficient Randomized DCAS. STOC 2021 - 53rd Annual ACM SIGACT Symposium on Theory of Computing, Jun 2021, Rome (Virtual), Italy. pp.1-64. ⟨hal-03195692⟩

Record views