Strongly Linearizable LL/SC from CAS

Simple item page
dc.contributor.authorNaderi-Semiromi, Fatemeh
dc.contributor.authorWoelfel, Philipp
dc.date.accessioned2024-05-16T18:57:36Z
dc.date.available2024-05-16T18:57:36Z
dc.date.issued2024
dc.description.abstractWe 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
dc.description.grantingagencyNatural Sciences and Engineering Research Council (NSERC)
dc.identifier.citationNaderi-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
dc.identifier.urihttps://hdl.handle.net/1880/118729
dc.identifier.urihttps://doi.org/10.11575/PRISM/43572
dc.language.isoenen
dc.publisherACM
dc.publisher.facultyScienceen
dc.publisher.hasversionsubmittedVersion
dc.publisher.institutionUniversity of Calgaryen
dc.publisher.policyhttps://www.acm.org/publications/policies/publication-rights-and-licensing-policy
dc.relation.ispartofseriesPODC 2024
dc.rights© 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/podc
dc.rights.urihttp://creativecommons.org/licenses/by/4.0/
dc.subjectwait-freedom
dc.subjectstrong linearizability
dc.subjectshared memory
dc.subjecttheory of computation
dc.subjectLL/SC
dc.subjectABA
dc.titleStrongly Linearizable LL/SC from CAS
dc.typeTechnical Report
dc.typeArticle
ucalgary.scholar.levelFaculty
Files
Original bundle
Now showing 1 - 1 of 1
Thumbnail Image
Name:
TR_2024-05-09_PRISM.pdf
Size:
996.25 KB
Format:
Adobe Portable Document Format
Download
License bundle
Now showing 1 - 1 of 1
No Thumbnail Available
Name:
license.txt
Size:
2.25 KB
Format:
Item-specific license agreed upon to submission
Description:
Download
Collections
Science Research & Publications