HAL will be down for maintenance from Friday, June 10 at 4pm through Monday, June 13 at 9am. More information

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 Connect in order to contact the contributor
Submitted on : Monday, April 12, 2021 - 9:08:50 AM
Last modification on : Monday, April 4, 2022 - 9:28:29 AM
Long-term archiving on: : Tuesday, July 13, 2021 - 6:15:46 PM

File

DCAS.pdf
Files produced by the author(s)

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, ⟨10.1145/3406325.3451133⟩. ⟨hal-03195692⟩

Record views