Paper Info
Title
LL/SC and Atomic Copy: Constant Time, Space Efficient Implementations using only pointer-width CAS
Abstract
The Load-Link/Store-Conditional (LL/SC) primitive is considered the most suitable for implementing lock-free algorithms and data structures. However, the full semantics of LL/SC are not supported by any modern machine, so there has been a significant amount of work on simulations of LL/SC using Compare and Swap (CAS), a synchronization primitive that enjoys widespread hardware support. However, all of the algorithms so far that are constant time either use unbounded sequence numbers (and thus base objects of unbounded size), or require $\Omega(MP)$ space for $M$ LL/SC object (where $P$ is the number of processes). We present a constant time implementation of $M$ LL/SC objects using only $\Theta(M+P^2)$ space and requiring only pointer-sized CAS objects. Our implementation can also be used to implement $L$-word $LL/SC$ objects in $\Theta(L)$ time (for both $LL$ and $SC$) and $\Theta((M+P^2)L)$ space. We focus on the setting where each process can have at most one LL/SC pair at a time. To support $k$ overlapping LL/SC pairs per process, our algorithms incur an extra factor of $k$ in their space usage. To achieve these bounds, we begin by 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 memory location. The only restriction is that the destination of the copy must be single-writer, which means that only one process is allowed to write/copy into it. We believe this primitive will be very useful in designing other concurrent algorithms as well.
Year
DOI
Venue
2020
10.4230/LIPIcs.DISC.2020.5
DISC
DocType
Citations 
PageRank 
Conference
0
0.34
References 
Authors
0
2
Name
Order
Citations
PageRank
Guy E. Blelloch12927207.30
Wei Yuanhao200.34