Strongly Linearizable LL/SC from CAS

Simple item page
dc.contributor.advisorWoelfel, Philipp
dc.contributor.authorNaderi Semiromi, Fatemeh
dc.contributor.committeememberEberly, Wayne
dc.contributor.committeememberCensor-Hillel, Keren
dc.date2025-06-09
dc.date.accessioned2024-12-10T23:16:39Z
dc.date.available2024-12-10T23:16:39Z
dc.date.issued2024-12-06
dc.description.abstractLinearizability 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.
dc.identifier.citationNaderi Semiromi, F. (2024). Strongly linearizable LL/SC from CAS (Master's thesis, University of Calgary, Calgary, Canada). Retrieved from https://prism.ucalgary.ca.
dc.identifier.urihttps://hdl.handle.net/1880/120189
dc.language.isoen
dc.publisher.facultyGraduate Studies
dc.publisher.institutionUniversity of Calgary
dc.rightsUniversity 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.
dc.subjectshared memory
dc.subjectstrong linearizability
dc.subjectLL/SC
dc.subjectABA
dc.subjectwait-freedom
dc.subject.classificationComputer Science
dc.titleStrongly Linearizable LL/SC from CAS
dc.typemaster thesis
thesis.degree.disciplineComputer Science
thesis.degree.grantorUniversity of Calgary
thesis.degree.nameMaster of Science (MSc)
ucalgary.thesis.accesssetbystudentI do not require a thesis withhold – my thesis will have open access and can be viewed and downloaded publicly as soon as possible.
Files
Original bundle
Now showing 1 - 1 of 1
Thumbnail Image
Name:
ucalgary_2024_naderi semiromi_fatemeh.pdf
Size:
1.09 MB
Format:
Adobe Portable Document Format
Download
License bundle
Now showing 1 - 1 of 1
No Thumbnail Available
Name:
license.txt
Size:
2.62 KB
Format:
Item-specific license agreed upon to submission
Description:
Download
Collections
Open Theses and Dissertations