Naderi-Semiromi, FatemehWoelfel, Philipp2024-05-162024-05-162024Naderi-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/podchttps://hdl.handle.net/1880/11872910.11575/PRISM/43572We 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.en© Philipp Woelfel & Fatemeh Naderi-Semiromi| 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/podchttp://creativecommons.org/licenses/by/4.0/wait-freedomstrong linearizabilityshared memorytheory of computationLL/SCABATechnical Report