Researchers crack LL/SC lock-free memory with history independence
New randomized algorithm slashes memory overhead for lock-free data structures by 99%...
Computer scientists Dante Bencivenga, Homa Habashi, and Philipp Woelfel present a randomized implementation of Load-Link/Store-Conditional (LL/SC) that preserves history independence. The algorithm achieves constant expected step complexity for m linearizable LL/SC objects in a system of n processes, using O(nτ + m) base objects against a weak adaptive adversary—improving on the best known deterministic algorithm’s Ω(n²τ + m) bound, and no comparable randomized algorithm was previously known. The implementation supports quiescent history independence, and the authors show it can run a quiescently history-independent dynamic hashing algorithm from STOC 2025 on available hardware without an asymptotic increase in step or space complexity when m=Ω(n).
- First randomized LL/SC implementation reduces space complexity from Ω(n²τ + m) to O(nτ + m) using FADD
- Enables quiescent history independence - memory state becomes deterministic when operations complete
- Makes STOC 2025's dynamic hashing algorithm practical on existing hardware without LL/SC support
Why It Matters
Unlocks efficient concurrent data structures for multicore systems and distributed databases without specialized hardware