Strongly Linearizable LL/SC from CAS
Date
2024
Journal Title
Journal ISSN
Volume Title
Publisher
ACM
Abstract
We present an efficient strongly linearizable implementation of the load-linked/store-conditional (LL/SC) primitive from compare-and-swap (CAS) objects. Our algorithm has constant step complexity, and uses a bounded number of CAS objects and registers that can each store O (log n) bits, where n is the number of processes. All previously known wait-free LL/SC algorithms are either not strongly linearizable, or use objects of unbounded size.
Description
Keywords
wait-freedom, strong linearizability, shared memory, theory of computation, LL/SC, ABA
Citation
Naderi-Semiromi, F., & Woelfel, P. (2024, Jun. 17-21). Strongly linearizable LL/SC from CAS. PODC '24: Proceedings of the 2024 ACM Symposium on Principles of Distributed Computing. Nantes, France. https://dl.acm.org/conference/podc