Faster Randomized Repeated Choice and DCAS

Simple item page
dc.contributor.authorBencivenga, Dante
dc.contributor.authorGiakkoupis, George
dc.contributor.authorWoelfel, Philipp
dc.date.accessioned2024-05-16T18:50:06Z
dc.date.available2024-05-16T18:50:06Z
dc.date.issued2024
dc.description.abstractAt 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.
dc.description.grantingagencyNatural Sciences and Engineering Research Council (NSERC)
dc.identifier.citationBencivenga, 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
dc.identifier.doihttps://doi.org/10.11575/prism/43575
dc.identifier.urihttps://hdl.handle.net/1880/118732
dc.identifier.urihttps://doi.org/10.11575/PRISM/43575
dc.language.isoenen
dc.publisherACM
dc.publisher.facultyScienceen
dc.publisher.hasversionsubmittedVersion
dc.publisher.institutionUniversity of Calgary, University of Rennes
dc.publisher.policyhttps://www.acm.org/publications/policies/publication-rights-and-licensing-policy
dc.relation.ispartofseriesPODC 2024
dc.rights© 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/podc
dc.rightsAttribution-NonCommercial-NoDerivatives 4.0 International
dc.rights.urihttp://creativecommons.org/licenses/by-nc-nd/4.0/
dc.titleFaster Randomized Repeated Choice and DCAS
dc.typeArticle
dc.typeTechnical Report
ucalgary.scholar.levelFaculty
Files
Original bundle
Now showing 1 - 1 of 1
Thumbnail Image
Name:
full_version.pdf
Size:
1.18 MB
Format:
Adobe Portable Document Format
Download
License bundle
Now showing 1 - 1 of 1
No Thumbnail Available
Name:
license.txt
Size:
2.25 KB
Format:
Item-specific license agreed upon to submission
Description:
Download
Collections
Science Research & Publications