Faster Randomized Repeated Choice and DCAS
Date
2024
Journal Title
Journal ISSN
Volume Title
Publisher
ACM
Abstract
At STOC 2021, Giakkoupis, Giv, and Woelfel, presented an efficient randomized implementation of Double Compare-And-Swap (DCAS) from Compare-And-Swap (CAS) objects. DCAS is a useful and fundamental synchronization primitive for shared memory systems, which, contrary to CAS, is not available in hardware. The DCAS algorithm has O(logn) expected amortized step complexity against an oblivious adversary, where nn is the number of processes in the system. The bottleneck of this algorithm is a building block, introduced in the same paper: A repeated choice (RC) object, which allows processes to propose values, and later agree on (and “lock in”) one of the proposed values, which is roughly uniformly distributed among the “recently” proposed ones. The object can then be unlocked, and the process be repeated.
The RC implementation introduced by Giakkoupis et al. has step complexity O(logn). In this paper, we present a more efficient RC algorithm, with similar probabilistic guarantees, but expected step complexity O(loglogn). We then show how this improved RC object can be used to achieve an exponential improvement in the expected amortized step complexity of DCAS.
Description
Keywords
Citation
Bencivenga, D., Giakkoupis, G., & Woelfel, P. (2024, Jun. 17-24). Faster randomized repeated choice and DCAS. PODC '24: Proceedings of the 2024 ACM Symposium on Principles of Distributed Computing. Nantes, France. https://dl.acm.org/conference/podc