Congratulations to George Giakkoupis for his paper entitled “Faster Randomized Repeated Choice and DCAS” with Dante Bencivenga and Philipp Woelfel, accepted at PODC 2024.
In this paper, the authors revisit the Double-Compare-and-Swap (DCAS) problem. DCAS is a useful and fundamental synchronization primitive for shared memory systems, which, contrary to CAS, is not available in hardware. In this paper, they improve the performance of the best-known DCAS implementation (Giakkoupis et al. STOC 21), improving its expected amortized step complexity from logarithmic to double-logarithmic. They achieve that by presenting a new implementation of a Repeated Choice object, which is a key building block of the DCAS implementation.
