HAL will be down for maintenance from Friday, June 10 at 4pm through Monday, June 13 at 9am. More information
Skip to Main content Skip to Navigation
Conference papers

Efficient Randomized DCAS

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.
Document type :
Conference papers
Complete list of metadata

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


Files produced by the author(s)



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


Files downloads