Search papers, labs, and topics across Lattice.
This paper addresses the implementation of $m$ linearizable LL/SC objects with constant expected step complexity in a system of $n$ processes, leveraging randomization and FADD alongside CAS and registers. The authors achieve a significant improvement in space complexity, reducing it to $O(n\tau + m)$ against weak adaptive adversaries, while also enabling quiescently history-independent (QHI) algorithms. Notably, this work facilitates the practical application of a QHI dynamic hashing algorithm, demonstrating that efficient implementations are possible on existing hardware without increasing complexity asymptotically.
Achieving a space complexity reduction for LL/SC implementations opens the door to efficient dynamic hashing on standard hardware, without sacrificing performance.
We study the fundamental problem of implementing $m$ linearizable LL/SC objects with constant expected step complexity in a system of $n$ processes, using bounded base objects commonly available in hardware. Assuming that each process may have at most $\tau$ outstanding LL operations, the best known deterministic algorithm requires $\Omega(n^2\tau + m)$ base objects (CAS and registers) [Blelloch and Wei, DISC 2020]. Previously, no comparable randomized algorithm was known. By employing randomization and FADD in addition to CAS and registers, we obtain a space bound of $O(n\tau+m)$ against the weak adaptive adversary. For $m=O(1)$ this matches a lower bound for algorithms using CAS and registers [Aghazadeh and Woelfel, PODC 2015]. In addition, our object can be employed by quiescently history-independent (QHI) algorithms: Whenever no operation on the object is pending and no process has an outstanding LL operation, its internal memory state is uniquely determined by the values of the $m$ LL/SC objects. An important application is a QHI dynamic hashing algorithm presented at STOC 2025, which uses $\Theta(m)$ hardware LL/SC objects to maintain a hash table of size $m$ [Attiya, Bender, Farach-Colton, Oshman, and Schiller, STOC 2025]. But LL/SC is not available in hardware, and prior to our work no wait-free or efficiently lock-free software implementation of LL/SC with similar properties was known. Our work demonstrates that one can actually implement the hashing algorithm on available hardware, without an asymptotic increase in step and space complexity, under the reasonable assumption that $m=\Omega(n)$.
