Efficient Randomized LL/SC that Preserves History Independence

The search context does not contain specific details regarding an "Efficient Randomized LL/SC that Preserves History Independence" implementation; the provided documents primarily focus on strongly linearizable implementations of LL/SC from CAS objects.

However, related research in the context highlights:

• Strong Linearizability: Recent work (e.g., Naderi-Semiromi and Woelfel, PODC '24) presents a strongly linearizable implementation of LL/SC from CAS objects with constant step complexity and bounded word-size ($O(\log n)$ bits). This ensures that randomized algorithms preserve their probability distributions under a strong adaptive adversary.
• Historical Context: Earlier practical constructions (e.g., Blelloch and Wei) achieved constant-time LL/SC implementations from CAS but often relied on unbounded sequence numbers or specific space complexities ($O(n^3)$ for strongly linearizable variants).
• Gap: The specific constraint of "preserving history independence" via a "randomized" approach for $m$ objects is not explicitly detailed in the provided snippets, which instead emphasize strong linearizability as the condition for preserving probabilistic behavior in randomized algorithms.

Problem and setting. The paper addresses the design of efficient shared-memory implementations of load-linked/store-conditional (LL/SC) primitives. Specifically, it studies how to implement \(m\) linearizable LL/SC objects in a system of \(n\) processes using only bounded base objects such as compare-and-swap (CAS) and registers, which are the primitives typically available in modern hardware. The analysis assumes a bounded level of outstanding optimistic work: each process can have at most \(\tau\) pending LL operations. This is a natural model for optimistic concurrency control, where processes repeatedly attempt to load a value and later commit an update, but only a limited number of attempts can be in flight at once.

Key contribution and insight. The main contribution is a randomized LL/SC implementation that achieves constant expected step complexity while preserving history independence. This is significant because the best deterministic constructions known for this setting require a space cost on the order of \(\Omega(n^2\tau + m)\) base objects, reflecting a quadratic dependence on the number of processes. The paper’s randomized approach is aimed at circumventing that deterministic barrier: by using randomization to coordinate or break conflicts, the algorithm can keep the expected number of steps per operation constant and avoid paying the full \(n^2\)-style overhead in object space. In addition, the implementation is history independent, meaning that the internal state of the object does not leak information about the sequence of operations that produced it, beyond what is already observable in the object’s external behavior.

Why it matters. LL/SC is a foundational primitive for optimistic and lock-free concurrent data structures, so efficient implementations are important for scalable shared-memory systems. History independence is an increasingly important security and privacy property, especially in settings where low-level object state may be observable through side channels, debugging interfaces, or forensic analysis. By combining constant expected step complexity, linearizability, and history independence under realistic bounded hardware primitives, this work shows that randomized shared-memory objects can be both highly efficient and strongly private. It therefore advances the design of concurrent objects that are performant in practice while also resisting leakage of operational history.