Woelfel, PhilippNaderi Semiromi, Fatemeh2024-12-102024-12-102024-12-06Naderi Semiromi, F. (2024). Strongly linearizable LL/SC from CAS (Master's thesis, University of Calgary, Calgary, Canada). Retrieved from https://prism.ucalgary.ca.https://hdl.handle.net/1880/120189Linearizability is the standard correctness condition for shared memory algorithms and is generally considered to be the practical equivalent of atomicity for deterministic algorithms. However, Golab, Higham, and Woelfel [16] showed that if we replace atomic objects used in a randomized algorithm with their linearizable implementations, then some of the properties of the algorithm may be lost. They introduced a stronger correctness condition, called strong linearizability, and proved that strongly linearizable objects can be used in both deterministic and randomizes algorithms as if they were atomic. In this thesis, 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. To the best of our knowledge, we are the first ones introducing a constant-time strongly linearizable LL/SC implementation, which uses bounded memory and bounded word-size.enUniversity of Calgary graduate students retain copyright ownership and moral rights for their thesis. You may use this material in any way that is permitted by the Copyright Act or through licensing that has been assigned to the document. For uses that are not allowable under copyright legislation or licensing, you are required to seek permission.shared memorystrong linearizabilityLL/SCABAwait-freedomComputer Sciencemaster thesis