Bencivenga, DanteGiakkoupis, GeorgeWoelfel, Philipp2024-05-162024-05-162024Bencivenga, 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/podchttps://hdl.handle.net/1880/118732https://doi.org/10.11575/PRISM/43575At 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.en© Philipp Woelfel, Dante Bencivenga, George Giakkoupis | ACM 2024. This is the author's version of the work. It is posted here for your personal use. Not for redistribution. The definitive Version of Record will be published in PODC '24: Proceedings of the 2024 ACM Symposium on Principles of Distributed Computing, https://dl.acm.org/conference/podcAttribution-NonCommercial-NoDerivatives 4.0 InternationalArticlehttps://doi.org/10.11575/prism/43575