Efficient randomized LL/SC that preserves history independence solves a rare problem: how to implement LL/SC on standard hardware primitives without breaking quiescent history independence (QHI).
The main issue here is not linearizability per se. The problem is that LL/SC relies on context state, and this state can easily turn into a history leakage channel. If open links remain in a quiescent state, then the snapshot of shared memory shows more than it should of the abstract state of the object. This is where many practical schemes hit a compromise between correctness, privacy, and space complexity.
The authors start with a limitation that sets the entire architecture of the solution: bounded base objects that are actually found in hardware, and up to τ outstanding LL() operations per process. Previously, the best deterministic scheme required Ω(n²τ + m) base objects. Here, a different path is chosen: randomization plus FADD along with CAS and registers. This provides an O(nτ + m) space bound against a weak adaptive adversary and constant expected step complexity. For m = O(1), this coincides with the known lower bound for schemes on CAS and registers, so the result does not appear to be a local trick, but rather a precise fit within the bounds of what is possible.
The key engineering idea is to separate two layers of state. One layer contains the value-tag pair in the CAS object. The other contains usage counts for tag reuse. The tag is needed not as a label for humans, but as a mechanism to prevent ABA. If the tag has already been read by an outstanding LL() and is still protected, SC() has no right to reuse it. Therefore, LL() first reads the value-tag, then increments the corresponding usage count, and then re-reads the object. If the state has changed, the operation can roll back to an earlier linearization point and complete as if the protected link had not been established. This is a cautious solution. It makes the algorithm more complex, but preserves the correct semantics under contention.
The most interesting part begins where the authors attempt to maintain QHI. A simple “history-independent implementation” is not enough because the abstract state of LL/SC in the model includes context. In a quiescent state, open links cannot be left, otherwise an attacker will see traces of past LL() calls. Therefore, the algorithm introduces CL(), which not only clears the local state of the process but also ensures the canonical representation in shared memory. When the system becomes settled, all tags and counters must come to zero. This is no longer just a correctness issue, but a question of whether the memory snapshot can be considered a valid representation of the abstract state.
The implementation achieves this through an additional activity counter C[i] for each LL/SC object. LL(i) increments C[i], while CL(i) decrements it. If after decrementing the object becomes “the last active,” CL() attempts to reset the tag field to zero. This is where the main trade-off arises: a zero tag cannot be treated as a regular protected tag, so LL(), SC(), and VL() receive additional logic. LL() always accepts the zero tag, SC() makes a second CAS attempt if the tag has already been reset, and VL() considers zero a valid case. This slightly complicates the execution path but allows the shared memory to return to canonical form without violating abstract semantics.
From an implementation perspective, this is not a free improvement. The authors explicitly point out the cost: bounded tags must fit into the CAS object, and the size of the tag depends on ⌈log(τn)⌉ + 1. In return, the algorithm achieves what was previously unavailable simultaneously: efficient multi-object LL/SC, wait-free behavior with expected constant step complexity, and QHI-preserving property. Moreover, for history-independent dynamic hashing from STOC 2025, there emerges a practical opportunity to operate on available hardware without asymptotic blow-up in step complexity and space complexity, if m = Ω(n). This is an important consequence, but not a marketing one. It means that the algorithm bridges the gap between the theoretical model and what can be deployed on real systems.
It is also worth noting the boundary of applicability. This result does not provide multi-word LL/SC in the same form and also requires additional FADD objects. The authors themselves show that this is not a final point, but a pragmatic step forward. However, this is typically how concurrency engineering progresses: not through an ideal abstraction, but through a scheme that withstands contention, does not leak through the history channel, and remains asymptotically fair.
Information source
arXiv is the largest open preprint repository (since 1991, under the auspices of Cornell), where researchers quickly post working versions of papers; the materials are publicly accessible but do not undergo full peer review, so results should be considered preliminary and, where possible, checked against updated versions or peer‑reviewed journals. arxiv.org