Efficient randomized DCAS

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.

Authors

• George Giakkoupis
• Mehrdad Jafari Giv
• Philipp Woelfel

Keywords

• Oblivious Adversary
• Shared memory
• Randomized Algorithms
• Double-Compare-And-Swap
• DCAS