The paper Efficient Randomized DCAS, a joint work by George Giakkoupis (WIDE), Mehrdad Jafari Giv and Philipp Woelfel (University of Calgary, Canada) has been accepted at the 53rd ACM Symposium on Theory of Computing (STOC 2021).
Double-Compare-And-Swap (DCAS) is a tremendously useful shared-memory synchronization primitive, which is also notoriously difficult to implement from objects that are provided by hardware. The paper presents a randomized DCAS implementation with logarithmic expected amortized step complexity against the oblivious adversary.
This is the only algorithm to-date that achieves sub-linear step complexity.
Congratulation to all involved!
