2026-07-24T02:02:40Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:13083 2024-03-06T10:51:31Z ddc:004 open_access

LL/SC and Atomic Copy: Constant Time, Space Efficient Implementations Using Only Pointer-Width CAS Blelloch, Guy E. Wei, Yuanhao LL/SC Atomic Copy CAS Constant Time When designing concurrent algorithms, Load-Link/Store-Conditional (LL/SC) is a very useful primitive since it avoids ABA problems. The full semantics of LL/SC are not supported in hardware by any modern architecture, so there has been a significant amount of work on simulations of LL/SC using CAS. However, all previous algorithms that are constant time either use unbounded sequence numbers (and thus base objects of unbounded size), or require Ω(MP) space to implement M LL/SC objects for P processes. We present the first constant time implementation of LL/SC from bounded-sized CAS objects using only constant space overhead per LL/SC variable. In particular, our implementation uses Θ(M+kP²) space, where k is the number of outstanding LL operations per process, and only requires pointer-width CAS operations. In most algorithms that use LL/SC, k is a small constant which reduces our additive space overhead to Θ(P²). Our algorithm can also be extended to implement L word LL/SC objects in Θ(L) time for LL and SC, O(1) time for VL, and Θ((M+kP²)L) space. To achieve these bounds, our main technical contribution is implementing a new primitive called Single-Writer Copy which takes a pointer to a word sized memory location and atomically copies its contents into another object. The restriction is that only one process is allowed to write/copy into the destination object at a time. The ability to read from one memory location and write to another atomically, and in constant-time, is very powerful and we believe this primitive will be useful in designing other algorithms. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Guy E. Blelloch and Yuanhao Wei 2020 Is Part Of LIPIcs, Volume 179, 34th International Symposium on Distributed Computing (DISC 2020) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.DISC.2020.5 urn:nbn:de:0030-drops-130831 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.DISC.2020.5 eng https://creativecommons.org/licenses/by/3.0/legalcode