Strongly Linearizable LL/SC from CAS
Date
2024-12-06
Authors
Journal Title
Journal ISSN
Volume Title
Publisher
Abstract
Linearizability 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.
Description
Keywords
shared memory, strong linearizability, LL/SC, ABA, wait-freedom
Citation
Naderi Semiromi, F. (2024). Strongly linearizable LL/SC from CAS (Master's thesis, University of Calgary, Calgary, Canada). Retrieved from https://prism.ucalgary.ca.