Efficient Randomized LL/SC that Preserves History Independence

Efficient Randomized LL/SC that Preserves History Independence Dante Bencivenga # University of Calgary, Canada

Homa Habashi # University of Calgary, Canada

Philipp Woelfel # University of Calgary, Canada

arXiv:2608.12946v1 [cs.DC] 13 Aug 2026

Abstract 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 τ outstanding LL() operations, the best known deterministic algorithm requires Ω(n2 τ + m) base objects (CAS and registers) [14]. 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τ + m) against the weak adaptive adversary. For m = O(1) this matches a lower bound for algorithms using CAS and registers [3]. 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 Θ(m) hardware LL/SC objects to maintain a hash table of size m [8]. 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 = Ω(n). 2012 ACM Subject Classification Theory of computation → Shared memory algorithms; Theory of computation → Design and analysis of algorithms; Theory of computation → Concurrent algorithms Keywords and phrases LL/SC, concurrent algorithms, history independence, randomized algorithms, wait-freedom Funding Dante Bencivenga: Natural Sciences and Engineering Research Council of Canada (NSERC) Canada Graduate Scholarship – Doctoral (CGS-D) 578918-2023/198 and University of Calgary Eyes High Doctoral Recruitment Scholarship Philipp Woelfel: Natural Sciences and Engineering Research Council of Canada (NSERC) reference number RGPIN-2025-04233

Contents 1 Introduction 1.1 Improved Space Complexity . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1.2 History Independence . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1.3 Other Related Work . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

2 3 4 5

2 Preliminaries 2.1 Sequential Specification . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2.2 Outstanding LL() Operations . . . . . . . . . . . . . . . . . . . . . . . . . . . 2.3 History Independence . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

6 6 7 7

2

Efficient Randomized LL/SC that Preserves History Independence

2.4

QHI-Preserving LL/SC . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

3 Implementation

10

3.1

High-Level Description . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 10

3.2

Pseudocode . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 12

3.3

Low-Level Description . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 12

4 Analysis

16

4.1

Complexity . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 16

4.2

History Independence . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 20

4.3

Correctness . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 22

5 Conclusion

1

9

27

Introduction

Compare-And-Swap (CAS) is one of the most fundamentally and practically important shared memory primitives. A CAS object supports the standard Read() operation, as well as a CAS(old, new) operation that writes new to the object if its current value equals old. If this condition holds, the operation succeeds and returns True; otherwise, it fails, leaves the object unchanged, and returns False. Unfortunately, CAS suffers from the ABA problem, meaning there is no guarantee that the value of the object remains unchanged between a Read() returning v and a subsequent successful CAS(v, v ′ ). Being able to detect such ABAs is critical for the correctness of many concurrent algorithms. Load-Linked/Store-Conditional (LL/SC), is the ABA-free counterpart of CAS. An LL/SC object L supports two operations, LL() and SC(). The LL() operation returns the current value of the object, while SC(v) attempts to store v into the object. The store succeeds if and only if no other successful SC() has been performed since the calling process’s most recent LL(). Otherwise, the operation fails and the object’s value remains unchanged. In any case, the SC() operation returns a Boolean value indicating success or failure. Because LL/SC objects do not suffer from the ABA problem, they overcome a major limitation of CAS. It is therefore unsurprising that many shared memory algorithms rely on LL/SC instead of CAS [2, 9–11, 16, 25, 28–30, 41, 42, 46]. Unfortunately, unlike CAS, LL/SC is not available on common hardware architectures. Therefore, many software implementations have been devised [4–6, 14, 18, 27, 31–35, 37, 39, 40, 43]. In this paper we present a new efficient randomized implementation of a collection of multiple LL/SC objects that improves on the state of the art in two key ways: First, it achieves a lower space complexity compared to existing LL/SC implementations built from bounded shared memory primitives that are commonly available in hardware, while also achieving constant expected step complexity. Second, the implementation can be used in algorithms that assume hardware LL/SC (which does not exist) to achieve quiescent history independence [7]. No other known efficient wait-free algorithm has this property. Our algorithm is Las Vegas in the sense that randomization affects only running time and not correctness or history independence. We will now describe each of these results, which are both derived from the same algorithm.

D. Bencivenga, H. Habashi, and P. Woelfel

1.1

Improved Space Complexity

A simple way to implement LL/SC using CAS is to augment each CAS object with an unbounded sequence number that increments with every successful SC() operation. Significant efforts have been made to avoid using unbounded sequence numbers. We will assume throughout the following that shared memory hardware objects are of bounded size (in particular, unbounded sequence numbers cannot be used), and will refer to the number of such objects used as the space complexity. The best algorithms that implement a single LL/SC object from commonly available hardware primitives achieve constant step complexity and O(n) space complexity, where n is the number of processes [14, 32]. For implementations from CAS objects, this matches a known time-space tradeoff [3]. Many algorithms require multiple LL/SC objects. The naive approach of composing m independent LL/SC implementations leads to an undesirably high space complexity of Θ(n · m). Better space complexities are often in terms of the maximum number of outstanding LL() operations, which informally are LL() operations which have been executed but have not yet been paired with a subsequent SC() (see Section 2.2 for a formal discussion). The LL/SC algorithm by Blelloch and Wei [14] improves on the naive approach by implementing m LL/SC objects using O(n2 τ + m) bounded CAS objects and registers, where τ is an upper bound on the number of outstanding LL() operations per process. As the authors argue, τ is typically a small constant. However, if τ were to asymptotically exceed m/n, then the space complexity of their algorithm would become worse than that of the naive composition. We are not aware of any comparably efficient randomized solutions. Our randomized algorithm also implements m LL/SC objects and has constant expected step complexity (against the weak adaptive adversary), while improving upon the best known space bounds. If the total number of outstanding LL() operations across all LL/SC objects is known in advance to be at most k, then only O(k + m) bounded hardware primitives suffice. We use registers, CAS objects, and fetch-and-add (FADD) objects, each of which is widely available in hardware. For τ outstanding LL() operations per process, this yields a space improvement from the O(n2 τ + m) base objects of Blelloch and Wei [14] to O(nτ + m). Since τ ≤ m, our algorithm never needs asymptotically more hardware objects than the naive composition of m optimal LL/SC implementations. On the downside, our algorithm requires storing bounded tags of size ⌈log(τ n)⌉ + 1 within CAS objects, in addition to the LL/SC value. In contrast, the algorithm of Blelloch and Wei can implement multi-width LL/SC using only pointer-width CAS objects. In practice, in the case where the value stored is a 64-bit heap pointer, the 16 high-order bits and 3 low-order bits are zero in typical modern systems, leaving 19 bits to store a tag [36]. Blelloch and Wei [14] argue that τ ≤ 2 in practice, although a later history-independent hash table [8] uses τ = 3; we do not know of any algorithm using LL/SC (QHI or not) which requires τ larger than 3. This implies that tagged pointers can support up to 218 /3 processes for our implementation, which is far above currently practical thread counts. In cases where all 64 bits are required (e.g., double-precision floats), most architectures support double-width CAS for 128 aligned bits. Additionally, our implementation supports a CL() (“clear link”) operation, enabling a process to “undo” a preceding LL() (clearing the calling process’s outstanding LL() operation on a given LL/SC object), which helps to reduce the space complexity. It also supports a VL() (“validate link”) operation, allowing a process to verify whether an SC() would succeed at that point, without changing the object’s state or causing future SC() calls to fail. This is often helpful in algorithms involving multiple LL/SC objects. Our algorithm’s basic structure is similar to early bounded-tag LL/SC implementations

3

4

Efficient Randomized LL/SC that Preserves History Independence

such as that of Anderson and Moir [6] and Moir [40]. The space complexity bottleneck of many such algorithms is due to needing to track which tags can be safely reused, and choosing one in constant time. This is difficult to accomplish deterministically, so we instead employ randomization to choose new tags for SC(), and use FADD objects to count how many outstanding LL() operations have read each tag. These usage counts prevent ABAs of the tag fields by ensuring that the new tags chosen by SC() calls have not been read by any outstanding LL() operation. The counts are inspired by reference counting techniques [17, 22, 48], but since we don’t use them to free memory, we can circumvent the usual complications involved in safe memory reclamation.

1.2

History Independence

In a history-independent data structure, an attacker obtaining a snapshot of the memory cannot learn anything about the past operations applied to the data structure, beyond what is implied by the current abstract data structure state. This is an important privacy property, which has been extensively studied in sequential computing [1,12,13,15,20,21,23,24,38,44,45]. While there is a history-independent hash table in a partially concurrent setting [47], only recently has a systematic study of history independence in the concurrent setting been initiated by Attiya, Bender, Farach-Colton, Oshman, and Schiller [7]. Common techniques, such as using sequence numbers or tags to avoid ABAs, timestamps to order operations, or process identifiers to support synchronization, cannot easily be employed in history-independent data structures, as they encode traces of past executions. LL/SC exemplifies this: To deal with ABAs, an SC() operation succeeds if and only if there was no other successful SC() since the calling process’s preceding LL(), and therefore depends on a record of the past. If LL/SC were implemented in hardware, such metadata could not be retrieved by an attacker through reading shared memory. However, software implementations must store it in shared memory, potentially exposing it. We consider quiescent history independence (QHI), where the attacker can access memory only when no operations are in progress [7]. The authors of [7] also consider perfect history independence (PHI), in which the attacker can access memory at any time, but that often makes the attacker too strong: As they prove, PHI requires impractically large base objects to implement many types of concurrent objects. A slightly stronger property than QHI is state QHI [7], where the attacker can access memory during operations that cannot change the state of the abstract data structure. A recently proposed randomized hash table [8] satisfies state QHI while maintaining strong efficiency: a table of size m, storing elements from a universe of size u, uses O(m) shared memory objects of size 2 log u + O(1) bits each. It is lock-free with expected amortized step complexity O(c), where c bounds the number of concurrent operations on the same element. This algorithm critically depends on LL/SC. Since this synchronization primitive is not available in hardware, the hashing algorithm cannot be efficiently implemented on real systems without software support of some form of LL/SC that preserves the history independence of the algorithm. Observe that even if an LL/SC implementation is itself history-independent, it cannot be trivially used to replace atomic LL/SC: The state of an LL/SC object generally comprises context (see Section 2.1), describing the set of processes whose next SC() should succeed—we say that such a process has an open link to the object. Thus, if an LL/SC object has open links in a quiescent state, then an attacker can obtain information about the context. But algorithms employing atomic LL/SC, such as the hashing algorithm in [8], may assume that

D. Bencivenga, H. Habashi, and P. Woelfel

that context is not exposed.1 Thus, when using implemented LL/SC, it may be necessary to ensure that no process has an open link in a quiescent state. To facilitate that, Attiya et al. [7] suggested augmenting the LL/SC specification with an operation that allows processes to clear their open links before a quiescent state is entered. The authors called this operation release or RL(), but for consistency with earlier literature (e.g., [14, 40]) we call it clear link or short CL(). The authors showed that there exists a history-independent implementation of LL/SC with a CL() operation from a single CAS object. (The core algorithm is essentially the same one by Israeli and Rappoport [27].) In fact, the algorithm satisfies perfect history independence. This is an important existential result, used by the authors to show that a wait-free history-independent universal construction exists. However, the algorithm is not efficient and only lock-free (even though, perhaps surprisingly, the resulting universal construction is wait-free): Each successful SC() operation can prevent n − 1 LL() operations from making progress, leading to a worst-case amortized step complexity of Ω(n). Moreover, the underlying CAS object must be able to store n bits of metadata in addition to the value of the LL/SC object. Hence, the algorithm does not scale well with the number of processes. In this work, we define QHI-preserving LL/SC. That property is weaker than QHI, but sufficiently strong to preserve QHI of an algorithm in essentially the same way as QHI LL/SC does. We then show that our efficient implementation of multiple LL/SC objects has this property. It is the first efficient QHI-preserving LL/SC implementation from primitives that are commonly available in hardware. Our LL/SC implementation can be used in the universal construction of Attiya et al. [7] while preserving state QHI. Since our methods are randomized wait-free rather than just lock-free, their construction also becomes simpler (specifically, their pseudocode’s blue lines are not necessary for wait-free LL/SC and can be removed).2 The required bits of metadata per represented LL/SC object is reduced from n to log n+O(1). However, our implementation requires additional base objects, in this case 5n + 1 FADD objects, each with log n + O(1) bits. The hash table of [8] retains its asymptotic step and space complexity when substituting hardware LL/SC with our implementation, under the reasonable assumption that m = Ω(n). But, using our LL/SC implementation, the hash table is not state QHI anymore, and the size of its required CAS objects increases by an additive term of log n to 2 log u + log n + O(1). To preserve the space bounds, one needs to insert CL() operations in appropriate places, so that outstanding LL() operations are cleared whenever they are not needed anymore, as we discuss in Section 2.3. (This technique was introduced in the history-independent universal construction of [7].)

1.3

Other Related Work

Almost all prior implementations of m LL/SC objects either do not achieve constant worstcase step complexity [18, 27], use unbounded sequence numbers or tags [31, 33, 35, 39, 40], or require at least Ω(n · m) base objects. The sole exception that avoids all these drawbacks is the algorithm by Blelloch and Wei [14], discussed earlier. Other work addresses properties

1

Note that this assumption is only justified if an attacker has access to merely the shared memory, and cannot perform, for example, SC() operations. See also the discussion in Section 2.3. 2 Their algorithm also uses unconditional Store() operations, but they can be replaced by LL() followed by SC(), since in their context this SC() is guaranteed to succeed. Also, their conditional RL() (i.e., our CL()) in line 22 would need to be replaced by an unconditional CL() (see Footnote 3).

5

6

Efficient Randomized LL/SC that Preserves History Independence

such as strong linearizability [43], durability [31], or independence of the number of processes in the system [18, 31, 35]. A time-space tradeoff result states that a single 1-bit LL/SC object implemented from s bounded CAS objects and registers has step complexity Ω(n/s) [3]. Algorithms achieving optimality with respect to this tradeoff are known for s = Θ(n) [32] and s = O(1) [3]. Our algorithm is also optimal for s = Θ(n) (and m = 1).

2

Preliminaries

We use the standard asynchronous shared memory model, where n processes communicate by performing atomic shared memory operations on registers, CAS objects, and FADD objects. In fact, instead of the more general FADD, fetch-and-increment/decrement (FAID) suffices. This object stores an integer in the range {0, . . . , M − 1} for some positive integer M , and supports the operations FAI(), FAD(), and Read(). Each operation returns the object’s current value, and FAI() and FAD() respectively increment and decrement it. (Our algorithm guarantees that no overflow occurs.) Our algorithm is randomized, meaning that at any point a process can generate a (private) random number by performing a coin flip step. The adversary determines the order in which processes take steps, by deciding at any point during the execution, the next process to take a step. We assume the weak adaptive adversary, where a process always performs its next shared memory operation immediately after a coin flip step. I.e., while the weak adaptive adversary knows all past random decisions and adapts to them, it cannot intervene between a process’s coin flip and its following shared memory step. Even though we employ randomization, all correctness properties such as linearizability and QHI are achieved deterministically, i.e., they hold for all executions, regardless of the random decisions made.

2.1

Sequential Specification

An abstract object (also known as type) is a quintuple (Q, q0 , I, R, δ), where Q is a set of states, q0 is the initial state, I and R are sets of operations and responses, respectively, and δ : Q × I → Q × R is the transition function. This quintuple is also called the sequential specification of the object, as it defines the set of possible sequential executions: Whenever an object is in state q and operation i is invoked, δ(q, i) = (q ′ , r) defines the operation’s response r and resulting new state q ′ . To specify the abstract object LL/SC, we follow the definition in [7], which itself is based on [31]. (In [7], the specified object is called context-aware LL/SC. But context awareness is inherent to the specification, so we simply call it LL/SC.) Each state is a pair (v, L), where v is the object’s value and L is an n-bit sequence (ℓ1 , . . . , ℓn ), called context. Initially, ℓ1 = · · · = ℓn = 0, and the initial value of v can be defined arbitrarily. We say that p has an open link to the LL/SC object whenever ℓp = 1. A Read() returns the value v of the object. An LL() (“load-linked”) call by process p sets ℓp to 1 and returns the value v. An SC(x) (“store-conditional”) operation by process p succeeds if ℓp = 1, in which case it changes the state of the object to (x, (0, . . . , 0)) and returns True. If ℓp = 0, then the operation fails and returns False without changing the state of the object. Operation CL() (“clear link”) by process p simply resets ℓp to 0, and does not return anything. Finally, operation VL() (“verify link”) by process p returns a Boolean value that is true if and only if ℓp = 1. In this paper, we implement a collection of m LL/SC objects. Thus, the abstract object’s state is the cross product of the states of m individual LL/SC objects. Each operation now has one additional parameter that indicates which of the LL/SC objects in the collection is

D. Bencivenga, H. Habashi, and P. Woelfel

affected. For example, operations LL(i) and SC(i, x) behave as LL() and SC() operations defined above, affecting only the i-th LL/SC in the collection.

2.2

Outstanding LL() Operations

A process begins to have an outstanding LL() operation on object i (or, equivalently, an outstanding LL(i)) when it invokes an LL(i) operation, and it ceases to have an outstanding LL(i) when it completes one of the following operations: a SC(i, ·), CL(i), or a VL(i) operation that returns False. In particular, a process either has an outstanding LL(i) or it doesn’t; it cannot, e.g., have more than one outstanding LL() on the same object i. Outstanding LL() operations are related to but distinct from open links. Open links are defined by the sequential specification and refer to the abstract state of the LL/SC object. Outstanding LL() operations are defined by the local knowledge of each process, and change at invocation and response points of operations. If a process has an open link to object i while it is idle, then it also has an outstanding LL(i). However, a process may have an outstanding LL(i) without an open link to object i. In particular, a successful SC(i) operation by process p clears open links to object i from all processes, but only clears p’s outstanding LL(i)—other processes retain their outstanding LL(i) until they ‘discover’ that their open link has been cleared. The implementation uses a known bound k on the number of total outstanding LL() operations at any given point in the execution. Under a bound of τ outstanding LL() operations per process, we would thus have k = τ n.

2.3

History Independence

We consider a linearizable implementation of an abstract object together with a function h (called linearization function), which maps every execution on that object to a linearization. A linearization [26] h(E) of a concurrent execution E is a sequential execution of all operations which have responded in E and some operations which are pending (i.e., invoked but not yet responded) at the end of E, such that For any two calls a and b such that call a responds before call b is invoked in E, a appears before b in the linearization h(E), The invocation arguments and response values (if applicable) of each operation in E matches those in h(E), and The sequential execution h(E) is consistent with the object’s sequential specification. An implementation for which a linearization function exists is called linearizable. We assume that at certain points in time during an execution, an attacker gets access to the shared memory. The types of history independence defined in [7] differ mostly in their restrictions on when those attacks can occur. Formally, we can assume a set S of finite executions, so that attacks can only occur at the end of each execution E ∈ S. The implementation is history-independent, if for every execution E ∈ S, the state of the shared memory resulting from E is uniquely determined by the state of the abstract object resulting from the linearization h(E). (I.e., if two executions E, E ′ ∈ S yield different shared memory states, then the sequential executions h(E) and h(E ′ ) must also yield different abstract object states.) We focus on quiescent history independence (QHI), where an attack can occur only when the object is in a quiescent state (i.e., no operation is pending). Hence, S is the set of all executions that end in such a quiescent state.

7

8

Efficient Randomized LL/SC that Preserves History Independence

Now consider a simple object, say a dictionary with operations insert(), delete(), and lookup(). Suppose that in the implemented lookup() operation, some process p calls LL() to read the value of an LL/SC object L, and then p never follows up with an SC() call. Consider an execution E that consists of only one such complete lookup() operation, and let h(E) be its linearization. At the end of E, the context (ℓ1 , . . . , ℓn ) of L has ℓp = 1, because p has an open link to L. But if the process hadn’t called lookup(), ℓp would be 0. Thus, the abstract states of L at the end of E and at the end of the empty execution are different. On the other hand, the linearizations of the two executions are the empty execution and one where only one lookup() is being performed. Thus, both yield the same abstract object state of the dictionary (that is, the empty dictionary) even though the abstract state of the LL/SC object differs (in the value of ℓp ). Since the two executions end in quiescent configurations with different memory states (namely, the abstract state of L), QHI is violated. The QHI hashing algorithm in [8] does not perform such CL() operations, and in fact suffers exactly from the above problem: After an execution in which only a single lookup() operation is performed, the calling process has an open link to an LL/SC object, whereas in the empty execution it doesn’t. However, if one defines the state of an LL/SC object as its value without context, then a QHI LL/SC implementation would preserve QHI for algorithms using it, including the hashing algorithm in [8]. We will denote such an LL/SC object as context-oblivious. It depends on the attack model whether context-oblivious LL/SC can leak information in such an algorithm: If an attacker can only observe (read) shared memory, then it can indeed not learn more than the state represented by an abstract context-oblivious LL/SC. If, on the other hand, the attacker can run code on shared memory, then it can use VL() or SC() operations to expose open links to LL/SC objects, even if they are context-oblivious. In any case, technically it is problematic to assume context-oblivious LL/SC for history independence, as it is impossible to provide a sequential specification where the object’s state is well-defined and the outcome of an operation only depends on this state. Moreover (and as a result of that) it is impossible to implement context-oblivious LL/SC from other primitives. Hence, an LL/SC implementation satisfying (even perfect) history independence, such as [7], can in general not simply be used to replace context-oblivious LL/SC and still preserve history independence. As we have argued, the abstract state of implemented LL/SC objects must include its context. However, the abstract state of objects implemented using LL/SC typically does not depend on LL/SC context, since that is usually an implementation detail. It therefore follows that a QHI implementation typically has to ensure that there are no open links in quiescent configurations. For this reason, in their universal construction, Attiya et al. [7] employ CL() operations, by letting each process clear its open links before responding from a method call.3 Fortunately, it is easy to modify the hashing algorithm in [8] to satisfy this requirement: During each implemented operation, a process keeps track of the LL() operations it has called, and, at the end of the method call, clears all links by performing CL() operations. Clearly this does not increase the asymptotic step complexity. In general, this transformation

3

In their implementation, if a process can be sure that its open link will be cleared by another process’s successful SC() before the system enters a quiescent configuration, then it does not need to call CL(). Our implementation has a slightly stronger requirement that processes must clear their own outstanding LL() operations, even in this situation. This is necessary because we have FAID counters tracking the number of outstanding LL() operations, and the counters need to be decremented to avoid overflow and to ensure that they reach zero in quiescent configurations.

D. Bencivenga, H. Habashi, and P. Woelfel

can be applied to all algorithms where a process calling LL() in a method does not rely on that LL() operation in a future method call. This is the case in the hashing algorithm, and in perhaps all but some contrived algorithms4 . In an LL/SC implementation in which the space complexity depends on the number of outstanding LL() operations, such as ours, this general transformation may however increase the space complexity, especially if the algorithm contains loops. To preserve space complexity, CL() operations would need to be added once an outstanding LL() operation is no longer needed, to ensure that each process has a minimum number of outstanding LL() operations at any given time. For the hashing algorithm specifically [8], it is possible to show that there are always at most three outstanding LL() operations per process which may be later used in SC() or VL() operations. We illustrate how to add CL() operations to maintain at most three outstanding LL() operations per process at a time: CL(i) can be added in the insert(), lookup(), delete(), and help_op() methods immediately before each line which increments or decrements the variable i. In each of these cases, the outstanding LL(i) is no longer needed once i is changed. Immediately before each response point (including responses from internal help_op() calls), one can verify that the responding process has outstanding LL() operations for at most LL(i − 1), LL(i), and LL(i + 1), so CL() operations can be added for those three objects.

2.4

QHI-Preserving LL/SC

As discussed above, a QHI implementation of an abstract object that uses implemented LL/SC must typically prevent quiescent configurations from having open links. Thus, when implementing LL/SC for the purpose of using it in QHI algorithms, it makes sense to only require that no information is leaked when there are no outstanding LL() operations, and therefore no open links. This is especially the case when this relaxed requirement can lead to improved efficiency. In other words, for the purpose of using implemented LL/SC in QHI algorithms, there is little advantage in requiring an LL/SC object to not leak more information than just context in configurations where context is leaked anyway. This leads us to the definition of QHI-preserving LL/SC, where we allow arbitrary information leakage whenever there are outstanding LL() operations. A collection of LL/SC objects is in a settled state if no process has a pending method call on any object, and no process has an outstanding LL() on any object. Since LL/SC is a building block for other implementations, processes would usually only have an outstanding LL() operation when they have a pending method call for an implementation that uses LL/SC. As such, most implementations can ensure that CL() is called to clear any outstanding LL() operations before an implemented method responds. When such an implementation is in a quiescent state in the sense of no process having a pending method call, our LL/SC implementation is also in a settled state in the sense of having no outstanding LL() operations. An LL/SC implementation is QHI-preserving if, for every settled state reachable in any execution, its internal shared memory state is uniquely determined by the interpreted values of the LL/SC objects. Clearly, any QHI LL/SC implementation is also QHI-preserving, but the opposite is not necessarily true. However, in any QHI algorithm, where in every quiescent state there are no outstanding LL() operations, one can replace QHI LL/SC implementations with

4

One such contrived example is the implementation of a QHI LL/SC object from a single QHI LL/SC object.

9

10

Efficient Randomized LL/SC that Preserves History Independence

QHI-preserving ones, without sacrificing the QHI property of the algorithm. If a state QHI algorithm uses our LL/SC implementation, and also avoids LL(), SC(), CL(), and VL() operations in its non-state-changing operations (i.e., it only uses the Read() method on LL/SC objects), then it remains state QHI. This is the case for the universal construction of [7], and so using our implementation of LL/SC in that construction does preserve state QHI (see Section 1.2). Unfortunately, for the hashing algorithm discussed earlier [8], its non-state-changing lookup() method relies on LL() and VL() operations, and so it is not state QHI under our LL/SC implementation. As argued in Section 2.3, since LL() changes the abstract state of the LL/SC object, the hashing algorithm would not be state QHI under any LL/SC implemented from other primitives. Note also that even though our algorithm is randomized, it is deterministically QHIpreserving: Whenever the collection of LL/SC objects is in a settled state, the memory state is in a state that is deterministically and uniquely determined by the object’s abstract state.

3

Implementation

3.1

High-Level Description

We first explain how a simplified version of the algorithm works, without preserving quiescent history independence. Each LL/SC object is encoded as a CAS object storing a value-tag pair. The tag field stores a positive integer tag with a small, finite range (tag zero is reserved for preserving QHI), which allows SC() operations to detect changes since the calling process’s previous LL() operation, and hence prevent ABAs. Each possible tag has an associated usage count, stored in an array of FAID objects, which count how many outstanding LL() operations have read that tag. Each SC() operation attempts to change the object’s tag field to a randomly chosen new tag with zero usage count, via a CAS() operation. Our implementation guarantees that this CAS() attempt succeeds exactly if there was no other successful CAS() on the value-tag pair since the corresponding LL() operation last read the LL/SC object. More specifically, an LL() operation reads the value-tag pair, and attempts to protect the tag by incrementing its associated usage count. The calling process re-reads the value-tag pair, and if it has changed, then it can linearize before the change, such that its matching SC() and/or VL() calls can correctly return False. In this case, the calling process responds without saving the value-tag pair that it read, as though it did not perform any LL() operation at all. Otherwise, if the value-tag pair stays consistent after the process increments the tag’s usage count, then the process locally saves the value-tag pair for use in future operations on that LL/SC object. (In this case, the operation linearizes at the second read, since it is possible that the value-tag pair had an ABA after the first read and before the process protected the tag.) The usage count then remains nonzero while the LL() operation remains outstanding, which prevents a tag from being reused for that same object. Thus, the process can later tell whether it still has an open link for its outstanding LL() operation by simply checking whether the tag field has changed or not from its locally saved value. Indeed, this is exactly what a VL() operation does. An SC() operation by process p first tries to find a new tag that is not protected by any outstanding LL() operation, including its own outstanding LL(). It repeatedly reads the usage counts of randomly selected tags until it finds one with a count of zero, which is the only randomized step of the implementation. Since there are at most k outstanding LL() operations in total, and 2k possible tags, each usage count has a probability of at least 1/2 to be zero. (Recall that we assume the weak adaptive adversary, and therefore that p

D. Bencivenga, H. Habashi, and P. Woelfel

reads a usage count immediately after randomly choosing a tag, without any other process taking steps in between.) Then, p attempts a CAS() from the previous value-tag pair to the new value and newly chosen tag, and returns whether this CAS() succeeds. Note that the adversary can schedule other process steps in between choosing a new tag and this CAS() attempt, potentially making other SC() operations choose the same tag. However, if any other SC() successfully changes the value-tag pair in between these steps, then p’s CAS() attempt fails, because p already protected the tag read in its previous LL() call, preventing it from being reused during the SC(). (We discuss this in more detail in Section 3.3.2 and prove the claim in Lemma 17a.) The remaining operations are straightforward: A CL() operation decrements the read tag’s usage count, and clears the process’s locally saved value-tag pair. It is also called internally whenever an outstanding LL() operation is cleared. A Read() operation returns the value part of the value-tag pair.

3.1.1

History Independence

To preserve quiescent history independence, we first introduce a default tag of zero, such that all LL/SC objects’ tag fields are initialized to zero. This default tag does not have a usage count, but we instead add an activity counter to each LL/SC object, which is a FAID object that counts the number of outstanding LL() operations involving that object. This activity counter is then used to detect a settled state relative to this object, i.e., when no process has a pending method call or an outstanding LL() operation on that object. The LL() method increments this counter, and the CL() method (including internal calls of it) decrements it. The canonical state of shared memory during a settled state has all tag fields and all counters set to zero. While the counters naturally reach zero in a settled state, we need extra steps to ensure that tag fields are also reset to zero. The CL() method now takes on the responsibility of resetting an LL/SC object’s tag field to zero, if it decrements its activity counter to zero. Since other operations may still start working on the same object concurrently, the calling process takes similar steps to an LL() followed by an SC() operation, but only to change the tag field back to zero. In particular, the random selection of a tag with zero usage count is replaced with double-checking that the activity counter is still zero, and the CAS() only attempts to change the tag field to zero from its previously read value. If the CL() call detects any activity on the object, then it stops trying to reset the tag field, since it is no longer the ‘last’ operation working on the object. (I.e., another process would have incremented the activity counter again, relieving the calling process from its responsibility to reset the tag field). Note that this added step of CL() resetting the tag field to zero does not change the abstract state of the object, and in particular it must not clear any other process’s open link. Moreover, a CL() operation could be poised to reset a tag field to zero while other operations start working on the object, even though it checks the activity counter immediately before its attempted reset. As such, the LL(), SC() and VL() methods have extra logic to avoid misinterpreting a reset tag field as a successful SC() operation which cleared open links. In particular, the LL() method always accepts tag zero (also because tag zero does not have a usage count to increment), reverting its increment of a usage count in case it first reads a nonzero tag and then tag zero. If the SC() method’s first CAS() from its known value-tag pair fails, it now also attempts a second CAS() from the old value and tag zero to the new value-tag pair, in case the tag field was reset during its operation. The VL() method returns True if the tag field hasn’t changed or if it has changed to zero.

11

12

Efficient Randomized LL/SC that Preserves History Independence

3.2

Pseudocode

We present the implementation in pages 13 and 14. The red lines are only needed to preserve quiescent history independence, so a simpler algorithm following only the black lines implements LL/SC with the same asymptotic time and space complexity but without preserving history independence. (We only analyze the full algorithm in Section 4.) For the process-local static dictionary d, we use the default value ⊥ to mean that a given key does not have a value in d. When referring to pairs containing a value and a tag (which elements of L and d store), we use the dot operators .val and .tag to refer to the first and second fields of the pair, respectively.

3.3

Low-Level Description

We store the values of the LL/SC objects in an array L of CAS objects. In addition, each CAS object stores a non-negative bounded tag that is initialized to zero. The array R is used to count each tag’s usage, so that R[g] counts the number of processes that have an outstanding LL() operation that read the tag g; its purpose is to prevent ABAs. Similarly, array C is an activity counter for LL/SC objects, so that C[i] tracks how many processes have an outstanding LL(i); its purpose is to assist in preserving history independence. In any LL/SC implementation, processes need some way to keep track of their outstanding LL() operations, in order to be able to know whether their SC() and VL() calls should succeed. Here, processes use a local dictionary d, which stores, for each object i, a pair consisting of the last value and tag read from L[i], or the empty value ⊥ if the process has no outstanding LL(i). (The SC(i), VL(i), and CL(i) methods each return immediately when d[i] = ⊥, since they are only meaningful for a process with an outstanding LL(i).) Similarly to the high-level description, we begin by focusing on the black lines which satisfy the sequential specification without preserving history independence, and postpone discussion of the red lines, involving array C, most of the CL() method, and tag zero.

3.3.1

LL() Method

A calling process p reads the pair stored in L[i] (line 3), consisting of its value and tag, and stores this state in its local dictionary d (line 4). Next, p increments the corresponding usage count in R (line 6), then reads again to confirm that L[i] hasn’t changed (line 7). If L[i] has not changed upon the second read, then we say that p has successfully protected the tag from being reused (see the formal definition in Definition 9), and p returns in line 8, linearizing in line 7. This protection lasts until p next invokes CL(i), as line 25 decrements the usage count again. As we later discuss in the SC() method, the algorithm guarantees that a tag is only reused when no process protects it. Otherwise, L[i].tag has changed to a different value by the time p reads it in line 7. In this case, we take advantage of the fact that an SC(i) is required to fail if there was an intervening SC(i, ·) in between a process’s LL(i) and SC(i). We thus retroactively set p’s LL(i) call’s linearization point (which defines the order of the execution’s linearization) to the first read in line 3 to satisfy the sequential specification. (Although this is a standard trick for LL/SC implementations, this retroactive linearization point prevents this LL() implementation from being strongly linearizable [19].) The CL(i) call in line 13 sets d[i] to ⊥ (line 26), as though p had no outstanding LL(i), which forces p’s following SC(i) to fail in line 15. (In this case, p still does have an outstanding LL(i) by definition, because the fact that the next SC(i) will fail is not directly visible by an algorithm using our LL/SC implementation.)

D. Bencivenga, H. Habashi, and P. Woelfel

Constants: U is the set of values that LL/SC objects can have m is the number of LL/SC objects n is the number of processes k is the maximum number of outstanding LL() operations that processes can have in total Shared Data: L[i] for i ∈ {1, . . . , m} is a CAS object storing a pair in U × {0, 1, . . . , 2k} C[i] for i ∈ {1, . . . , m} is a FAID object storing a number in {0, . . . , n} R[g] for g ∈ {1, . . . , 2k} is a FAID object storing a number in {0, . . . , k} Process-local static data: d is a dictionary storing keys in {1, . . . , m} and values in U × {0, 1, . . . , 2k} Initialization: L[i] ← (ui , 0∗ ), where ui is an application-dependent initial value from U C[i] ← 0 R[g] ← 0 d starts empty for each process (all indexing returns ⊥) ∗ In the non-QHI-preserving version (black lines only), tag fields are initialized to any nonzero value, e.g., all ones.

LL(i ∈ {1, . . . , m}) if d[i] ̸= ⊥ then CL(i) C[i].FAI() 3 (val, tag) ← L[i].Read() 4 d[i] ← (val, tag) 5 if tag = 0 then return val 6 R[tag].FAI() ′ ′ 7 (val , tag ) ← L[i].Read() ′ ′ ′ 8 if (val, tag) = (val , tag ) then return val ′ 9 if tag = 0 then 10 R[tag].FAD() 11 d[i] ← (val′ , 0) 12 return val′ 1 2

13 14

CL(i) return val SC(i ∈ {1, . . . , m}, u ∈ U )

if d[i] = ⊥ then return False repeat 18 tag ′ ← uniform and independent random sample from {1, . . . , 2k} ′ 19 until R[tag ].Read() = 0 ′ 20 result ← L[i].CAS(d[i], (u, tag )) ′ 21 if result = False then result ← L[i].CAS((d[i].val, 0), (u, tag )) 22 CL(i) 23 return result 15

17

13

14

Efficient Randomized LL/SC that Preserves History Independence

CL(i ∈ {1, . . . , m}) if d[i] = ⊥ then return if d[i].tag ̸= 0 then R[d[i].tag].FAD() 26 d[i] ← ⊥ 27 if C[i].FAD() > 1 then return 28 (val, tag) ← L[i].Read() 29 if tag = 0 then return 30 R[tag].FAI() 31 if L[i].Read() = (val, tag) then 32 if C[i].Read() = 0 then 33 L[i].CAS((val, tag), (val, 0)) 24 25

34

R[tag].FAD() Read(i ∈ {1, . . . , m})

35

return L[i].Read().val VL(i ∈ {1, . . . , m})

if d[i] = ⊥ then return False if L[i].Read().tag ∈ {d[i].tag, 0} then return True 38 CL(i) 39 return False 36 37

3.3.2

SC() Method

Line 15 ensures that the SC() returns False() in the case of the calling process not having any outstanding LL() (lines 24 and 36 serve a similar purpose). In lines 17–19, the active process chooses a random tag in the range of possible tags, until it sees one with a usage count of zero, implying that it is not protected by any process. Since there are 2k tags and at most k outstanding LL() operations which can protect tags, each attempt succeeds with probability at least 1/2. Recall that d[i] stores the previous value-tag pair read from L[i]. Line 20 then attempts a CAS() from the previous value-tag pair stored in d[i] to the new value (the second argument of SC()) and the newly chosen tag. The method linearizes at the point of this CAS() attempt, calls CL() to clear the calling process’s outstanding LL(), and returns whether the CAS() attempt succeeded. We now highlight that since SC() does not itself create an outstanding LL(), it does not need to protect any tag, and so it does not increment any usage count in R. This may appear problematic at first: Suppose that a process p pauses after seeing R[g] = 0 in line 19 and before its CAS() in line 20, and during this pause another process q sees that R[g] = 0 for the same tag g. Then, process q may use tag g for the same or different object, and it may no longer be true that R[g] = 0 at the time that p executes its CAS() in line 20. We next explain why this does not lead to any problem. First, our implementation does allow different LL/SC objects to share the same tag. Unlike memory management for pointers, the only use of tags is to prevent ABAs for individual LL/SC objects in between an LL() and matching SC(). As such, it does not matter if the same tag is used for different LL/SC objects, as that would not cause an ABA for a single object.

D. Bencivenga, H. Habashi, and P. Woelfel

Second, if process q chooses the same tag g and has a successful CAS() on the same object as p, then it is possible to prove that p’s CAS() will necessarily fail, preventing an ABA by p. The key protection invariant (see Lemma 17a) is that, as long as some process is protecting a tag for some object and therefore contributing to that tag’s usage count, no process can change the object’s tag field to the protected tag. For process p to have a successful CAS(), changing the tag field back to g after q’s successful CAS(), the tag field would have had to change back to the previous tag g ′ that p was expecting from d[i].tag. But p must have already done an LL(i) before its SC(i), thus protecting that expected tag g ′ . This is the only way that the protection invariant could be broken, but it requires that the invariant was already broken previously for tag g ′ , and so the invariant holds by induction over the execution.

3.3.3

Remaining Methods

The CL() method decrements the usage account for d[i].tag, ending the calling process p’s protection of that tag, and resets d[i] to clear p’s outstanding LL(i). The Read() method ignores the tag field and simply outputs the value of the object. The VL() method checks if the tag field hasn’t changed, and returns the appropriate response, calling CL() to clear the outstanding LL() operation in case the tag field has changed.

3.3.4

CL(), C, and Tag Zero: Preserving Quiescent History Independence

We now discuss the role of the red lines for preserving quiescent history independence. Recall (from page 13) that all tag fields are initialized to zero for the QHI-preserving version of the algorithm. The CL(i) method now ensures that L[i].tag is reset to zero when it clears the last outstanding LL() operation on a given object, so that the shared memory returns to its canonical representation upon entering a settled state. Recall that array C is a shared activity counter for outstanding LL() operations on each object. As such, an LL(i) call increments C[i] in line 2, which announces that a process has created an outstanding LL(i). Line 27 of a CL(i) call then decrements C[i]; if the count before the decrement was greater than one, then some other process has an outstanding LL(i), so the calling process p does not reset L[i].tag. Otherwise, p tries to reset L[i].tag to zero if it is nonzero, but with several checks to avoid doing so after some other process wakes up and starts working on the object. Lines 28, 30, and 31 work the same way as lines 3, 6, and 7 to try to protect the current tag g stored in L[i].tag. If g is zero or if L[i].tag changes from g, then CL(i) no longer needs to reset L[i].tag, so it decrements its usage count if necessary (line 34). Otherwise, after double-checking that no process has created an outstanding LL() on object i while p was protecting g (line 32), p resets the tag field via a CAS() in line 33. This last check ensures that any process which changes L[i].tag does so after p’s execution of line 32, while g is protected. Similarly to SC(), if the tag field changes after p reads it a second time in line 31, then the protection invariant ensures that the CAS() in line 33 fails, because p is protecting the tag that it read in line 28. This process of resetting a tag field to zero does not change the abstract state of the object, but it is possible for another process to call LL(i) on the object in between lines 32 and 33, creating a newly outstanding LL(i). Thus, L[i].tag can still change from an LL(i) operation’s newly protected tag g to zero. However, if L[i].tag changes to some other tag g′ ∈ / {g, 0} while g is protected, then it cannot change to zero again, because C[i] > 0 while

15

16

Efficient Randomized LL/SC that Preserves History Independence

there is an outstanding LL(i) (from line 2). As such, once a process has an outstanding LL(i) with tag g and later sees L[i].tag = 0, it knows that L[i].tag changed directly from g to zero due to a CL(i) call, without any successful SC(i) linearizing in between. We refer to this additional guarantee as strongly protecting a tag (see Lemma 17b), and it simplifies the way that other methods treat tag zero. If an LL(i) operation reads tag zero from either of its reads in line 3 or 7, then it stores tag zero in d[i].tag, and the operation returns in line 5 or 12. Since tag zero can only be set by CL(i) after confirming that C[i] = 0, it does not need a usage count in R, so the LL() operation simply linearizes as soon as it reads tag zero. In the SC() method, the calling process p attempts two CAS() operations, in lines 20 and 21, because the tag could change from a nonzero value directly to zero. Since p strongly protects the tag read in its preceding LL() call, this is the only possible transition during the SC() call which does not change the abstract state of the object. Thus, the two CAS() operations are sufficient, and the SC() operation linearizes at its last CAS() attempt. Lastly, the VL() method also returns True in the case of tag zero in line 37, which again works due to the calling process strongly protecting the tag read in its preceding LL() call.

4

Analysis

4.1

Complexity

We begin the analysis by showing, in Theorem 7, that the expected step complexity of the implementation is constant under the weak adaptive adversary. We prove complexity first because the statements used to prove Theorem 7 are reused later to prove history independence (Theorem 15) and linearizability (Theorem 22). ▶ Lemma 1. When a process responds from a CL(i) or SC(i, ·) call, its value of d[i] is ⊥. Proof. For CL(i), if the calling process p returns in line 24, then the lemma is satisfied by the if-condition in that line. Otherwise, p sets d[i] to ⊥ in line 26 and does not change it again until its response. For SC(i, ·), if the calling process p returns in line 15, then the lemma is satisfied by the if-condition in that line. Otherwise, p calls CL(i) in line 22, which by the above ensures d[i] = ⊥ by its response, and then immediately returns. ◀ ▶ Lemma 2. At point t, if d[i] ̸= ⊥ for process p, then p has an outstanding LL(i). Proof. Only LL(i) can set d[i] to a non-⊥ value. By Lemma 1, the CL(i) and SC(i, ·) methods ensure d[i] = ⊥ by their respective responses. If a VL(i) call returns False, then either d[i] = ⊥ in line 36, or it calls CL(i) in line 38, so in both cases d[i] = ⊥ by the point it returns False. Thus, if d[i] ̸= ⊥ while p is idle, then p has called LL(i) and not subsequently called SC(i, ·), CL(i), or a VL(i) call which returns False. Hence, p has an outstanding LL(i). If d[i] ̸= ⊥ while p has a pending method call, then we also have that p has invoked LL(i) and not yet responded from a subsequent SC(i, ·) or CL(i) call, or a VL(i) call which returns False. Thus, also in this case p has an outstanding LL(i). ◀ ▶ Definition 3 (Contribution). Given a point t, a process p, and an element of C or R, p contributes j to that element’s value, if j is the number of FAI() minus FAD() operations that p has executed to that element before t. We next prove upper limits on p’s contribution to C and R, given that k is the upper bound on the total number of outstanding LL() operations across all processes.

D. Bencivenga, H. Habashi, and P. Woelfel

▶ Lemma 4. When a process p invokes or responds from a method call, (a) if d[i] = ⊥, then p contributes zero to C[i], and otherwise p contributes one to C[i], and (b) the total contribution to R by p equals the number of values in p’s dictionary d which have nonzero tags. While process p has a pending method call, (c) process p contributes at most one to each individual element of C, and (d) p’s total contribution to R is no larger than the maximum number of non-⊥ values in p’s dictionary d in the interval starting immediately before and ending immediately after the method call. At all points in the execution, (e) the total contribution from all processes to elements of R is at most k. Proof. Note that by Definition 3, p’s contributions to R and C, as well as its dictionary d, do not change while p is idle. Thus, if a to d hold when p responds from a method call and becomes idle, then they also hold until the point when p next invokes a method. From Lemma 2, p’s number of outstanding LL() operations is at least as large as the number of non-⊥ values in p’s dictionary d. In the case of a pending method call, p’s number of outstanding LL() operations is at least as large as the maximum number of non-⊥ values in d in the interval starting immediately before and ending immediately after the method call. Therefore, b and d imply that p’s total contribution to R never exceeds its number of outstanding LL() operations. Together with the global bound of k on outstanding LL() operations, e follows. As such, it suffices to prove a and b for a process p by induction over its method calls, while proving that d and c hold at all points within each of p’s method calls. Initially, p contributes zero to elements of C and R, and its dictionary d is empty (all values are ⊥), so a to d hold before p’s first method call. Suppose that a to d hold for p immediately before the invocation of a given method: we will prove that d and c hold throughout the method call, and that a and b hold immediately after the call’s response. If the method call is Read(i), then a to d hold because Read() does not affect p’s contributions or its dictionary d. We next consider the CL(i) method. If the call returns immediately in line 24, then neither p’s contributions nor d change, so a to d remain true. Otherwise, d[i] ̸= ⊥ at CL(i)’s invocation, so by a, p’s contribution to C[i] is one at invocation. Then, p resets d[i] to ⊥ in line 26 and decrements C[i] in line 27, making its contribution to C[i] become zero and satisfying a at all the remaining response points. If d[i].tag ̸= 0 at invocation, then p decrements R[d[i].tag] in line 25, satisfying b after line 26 and before line 30, in particular including p’s possible response in either line 27 or 29. Since this possible decrement to R[d[i].tag] occurs only if p sets d[i] to ⊥ in the call, d remains true from invocation until at least p executes line 30. Since p does not increase its contribution to C throughout the method call, c remains satisfied throughout the call. If p responds in line 34, then it increments and later decrements some element of R (in lines 30 and 34). Since the two counteract each other’s effect, and since b holds immediately before line 30, b holds immediately after p’s response in line 34, in addition to the other possible response points as proven above. Since b implies d, it also follows that d holds immediately after p’s response, and it only remains to show that d holds while p has a pending next step, in particular after executing line 30. If d[i].tag ̸= 0 at invocation, then p’s contribution to R decrements, increments, then decrements again in lines 25, 30, and 34, so d holds throughout the call. Otherwise, d[i].tag = 0 at invocation, and the number of values in

17

18

Efficient Randomized LL/SC that Preserves History Independence

p’s dictionary which have nonzero tags at invocation is strictly smaller than the number of values which are non-⊥ at invocation. There is therefore room for at least one increment of p’s contribution to R while the method call is pending, and therefore the temporary increment in line 30 still satisfies d. Thus, d holds throughout a CL(i) call. Since the SC() and VL() methods do not change p’s contribution to C or R or its dictionary d except via their internal CL() calls, a to d hold for SC() and VL() by the above arguments for CL(). It remains to show a to d for an LL(i) call by p. Since they each remain true after internal CL() calls by the above arguments, they each remain true immediately before the LL(i) call executes line 2. By Lemma 1, the CL(i) call in line 1 also ensures that d[i] = ⊥ immediately before line 2. It follows from a that p’s contribution to C[i] immediately before line 2 is zero, and hence its contribution immediately after the FAI() is one. In particular, at no point is p’s contribution to C[i] greater than one, satisfying c throughout the call. After executing line 4, a becomes true again, and remains true until p’s possible invocation of CL(i) in line 13, then remains true at its response by the above arguments for CL(), and therefore a is true at any possible response from LL(i). (Note that line 11, if executed, only changes the value of d[i] from one non-⊥ value to another.) We next verify that b holds at each relevant point, again using that a to d and d[i] = ⊥ hold immediately before line 2. Since only d[i] is modified in the method, it suffices to show that d[i].tag ̸= 0 at the response if and only if p increments its contribution to R by one by its response. At a response in line 5, d[i].tag = 0 and R is untouched by p. At a response in line 8 and immediately before calling CL(i) in line 13, d[i].tag = ̸ 0 and one element of R is incremented. At a response in line 12, d[i].tag = 0 and the increment of R is reversed. Finally, since d and d[i] = ⊥ hold immediately after line 1, it follows that setting d[i] to a non-⊥ value in line 4 allows for one increment to p’s contribution to R while still satisfying d. Since p can increment its contribution to R only in line 6 of the method, d remains satisfied, even if p later reverses this increment. ◀ ▶ Lemma 5. Let p be a process and t a point in the execution. For each i ∈ {1, . . . , m}, the number of FAI() operations on C[i] by p before t is greater than or equal to the number of FAD() operations on C[i] by p before t. Similarly, for each g ∈ {1, . . . , 2k}, the number of FAI() operations on R[g] by p before t is greater than or equal to the number of FAD() operations on R[g] by p before t. Proof. To prove the lemma, it suffices to show that, for each FAD() operation on an element of C or R, there is a one-to-one mapping to a previous FAI() operation by the same process on the same element. We first define the mapping, and then show that it is one-to-one. A FAD() on R in line 10 maps to the process’s previous execution of line 6 in the same LL() method, both of which affect the same element of R. Similarly, a FAD() on R in line 34 maps to the process’s previous execution of line 30 in the same CL() method, both of which affect the same element of R. If a CL(i) call invoked by process p proceeds past line 24, then p confirms that d[i] ̸= ⊥ in that line. Since the dictionary d starts empty and only LL(i) can set d[i] to a non-⊥ value, there is some last LL(i) call invoked by p before the CL(i) call which sets d[i] to that non-⊥ value. Both of the remaining FAD() operations are in the CL(i) method, so we map the decrements to the corresponding increments in this LL(i) call. Specifically, line 25 in CL(i) corresponds to line 6 in the corresponding LL(i) call (which p executes since d[i].tag ̸= 0 when p invokes CL(i)), and line 27 in CL(i) maps to line 2 of the corresponding LL(i) call.

D. Bencivenga, H. Habashi, and P. Woelfel

In both cases, the FAD() and FAI() operations are by the same process on the same object. For lines 25 and 6 in particular, d[i].tag stays the same because only LL(i) can set d[i] to a non-⊥ value, d[i] ̸= ⊥ at CL(i)’s invocation, and the mapped execution of line 6 is from the most recent LL(i) call by p. We now show that each FAI() is mapped to by at most one FAD() on the same object (i.e., the mapping is one-to-one). This is immediate for the mapping from line 34 to line 30, since they involve the same method call and no other FAD() maps to line 30. Next, consider the FAI() on R in line 6 in some LL(i) call by process p. If p executes line 10 in the same call, then it also sets d[i].tag to zero in line 11 before returning from the call. Therefore, p does not execute the FAD() in line 25 of CL(i) until after it invokes another LL(i) which sets d[i] to a non-⊥ value (and specifically sets d[i].tag to a nonzero value). If p does execute a FAD() in line 25 which maps to the FAI() in line 6, then it resets d[i] to ⊥ in line 26 before returning. Therefore, if p invokes CL(i) again before invoking another LL(i) call which sets d[i] to a non-⊥ value, p does not get past line 24, and in particular does not execute line 25. Thus, the FAI() operation in line 6 can only be mapped to by at most one FAD() operation. Finally, consider the FAI() operation on C in line 2 in some LL(i) call by p, which can be mapped to by a FAD() operation in line 27 in a CL(i) call by p. Before executing line 27, p resets d[i] to ⊥ in line 26, so it cannot get past line 24 again until invoking LL(i) and setting d[i] to a non-⊥ value again. ◀ ▶ Lemma 6. The value of each element in C and R equals the sum of the contributions from each process (i.e., no element overflows). Proof. From Definition 3 and Lemma 5, we have that each process contributes a non-negative value to each element of C and R. We also have that only FAI() and FAD() operations can affect that value of elements of C or R. The lemma then follows from Lemma 4c and e, since the n processes can contribute at most n to the value of each element of C, and at most k in total to elements of R, which are their respective maximum values. ◀ ▶ Theorem 7 (Expected Complexity). Each method other than SC() has constant step complexity. The expected step complexity of SC() is constant under a weak adaptive adversary. Proof. The first part is immediate from the fact that the only loop in the entire implementation is lines 17–19 of the SC() method. For the second part, recall that under the weak adaptive adversary, a random choice by process p is immediately followed by its next shared memory step. Thus, when p chooses a random tag g in line 18, it then immediately reads R[g] in line 19 without any other process taking a step in between the two lines. In particular, the value of R[g] does not change in between the two lines, and it stays at zero if it was zero at p’s execution of line 18. Thus, p breaks out of its loop as soon as it chooses a tag g such that R[g] = 0 in line 18. Since this random choice is uniform over {1, . . . , 2k} and independent, it suffices to show that, at any given time, at least a constant fraction of the indices in R have a value of zero. From Lemmas 5 and 6, a given element of R is nonzero at time t exactly if there exists some process that contributes to that element at time t. From Lemma 4e, the total contribution from all process to all elements of R is at most k. Thus, at least k of R’s 2k elements have a value of zero at any given time, which completes the proof. ◀

19

20

Efficient Randomized LL/SC that Preserves History Independence

4.2

History Independence

The goal of this section is to prove Theorem 15, which shows that when the system is in a settled state, then the shared memory depends only on the LL/SC objects’ values, therefore achieving the QHI-preserving property discussed in Section 2.4. In our case, we will prove that in a settled state, L[i].val stores the value of LL/SC object i, and all other shared memory used in the implementation equals zero, like in the initial state. ▶ Lemma 8. If a process has performed a FAI() operation on a given element of C or R before point t, and has not performed a subsequent FAD() operation before point t, then that element’s value is nonzero at point t. Proof. From Lemma 5, for each process and the given element e of C or R, the process’s contribution to e is non-negative at all points. Thus, immediately after process p increments e, p’s contribution as well as the total contribution to e becomes positive, and this remains true until p next decrements e. The lemma then follows from Lemma 6. ◀ ▶ Definition 9 (Protected and Strongly Protected Tags). A tag g becomes protected for LL/SC object i at point t by a process p if either (a) p reads zero from L[i].tag in line 3 or 7 at point t, in which case g = 0, or (b) p reads g from L[i].tag in line 7 or 31 at point t, such that its local variable pair (val, tag) (read from L[i] in line 3 or 28 respectively) equals the value of L[i] at point t. If a tag becomes protected for object i during an LL(i) call, then it is also strongly protected for i by p. In that case, the protection and strong protection by process p end when it next invokes CL(i). Otherwise, the tag becomes protected for object i by p during a CL(i) call, in which case it is not strongly protected by p, and the protection ends when that call responds. If a tag is protected or strongly protected by any process at point t for object i, we also simply refer to it as protected or strongly protected for object i, without referring to the protecting process. We will later show in Lemma 17 that a tag protected for i prevents ABAs on L[i], and a tag strongly protected for i prevents L[i].tag from returning to zero from a different tag. Note that although distinct LL/SC objects’ tag fields can store the same tag, protection and strong protection always refer to a specific object. ▶ Lemma 10. If some tag is strongly protected for object i at point t, then C[i] ̸= 0 at point t. Proof. From Definition 9, a tag can only become strongly protected for i by a process p in an LL(i) call in line 3 or 7, and both lines happen after p increments C[i] in line 2 and before its next invocation of CL(i). Since only CL(i) can decrement C[i] (in line 27), it follows that p’s strong protection of g for i ends before it decrements C[i]. The lemma then follows from Lemma 8. ◀ ▶ Lemma 11. If a process p has no pending method call on object i at point t, then (a) p strongly protects tag g for object i if and only if p’s value of d[i].tag = g at point t, and (b) if p does strongly protect g, then p’s value of d[i] at point t equals the value of L[i] when this strong protection started. Note that Lemma 11 also implies that p can only protect at most one tag per object while idle.

D. Bencivenga, H. Habashi, and P. Woelfel

Proof. We first note that the only case in which p can protect a tag for i while not having a pending method call on object i, by Definition 9, is if it protected the tag as part of an LL(i) call. In particular, this implies that p also strongly protects the tag. Moreover, only LL(i) can set d[i] to a non-⊥ value (in lines 4 and 11) and only CL(i) can reset d[i] to ⊥ (in line 26). An invocation of CL(i) ends p’s (strong) protection of any tag for object i by Definition 9, and, from Lemma 1, d[i] = ⊥ when CL(i) responds. To prove a, it remains to show that an LL(i) call strongly protects tag g for i by its response if and only if d[i].tag = g at that call’s response. To prove b, we need to also show that d[i] is set to the value read from L[i] at the point that g become strongly protected. To show these, we consider the five possible response points from an LL(i) call by process p. Suppose by induction that the lemma is true before the call begins (the base case holds since d[i] = ⊥ and processes protect no tags at t = 0). If p protects some tag g for i just before invocation of the LL(i) call, then d[i].tag = g before invocation, and therefore p invokes CL(i) in line 1. Thus, after line 1, p does not protect any tag for i, and d[i] = ⊥. If p responds in line 5 or 12, then p reads zero from L[i].tag in line 3 or 7 respectively; at the point of that read, by Definition 9a, p strongly protects tag zero for i. In line 4 or 11 respectively, p sets d[i] to the value read from L[i] at the point that it started strongly protected tag zero, then it responds without further changing d[i]. If p responds in line 8, then p re-reads its local variables (val, tag) from L[i] in line 7, after having set d[i] to (val, tag) in line 4 and not changing it afterwards. By Definition 9b, p strongly protects d[i].tag in line 7, at which point L[i] = d[i]. Otherwise, p responds in line 14, it which case the CL(i) call invoked in line 13 resets d[i] to ⊥ and ends any protection of a tag by p for i. ◀ ▶ Lemma 12. Suppose that a successful CAS() takes place on L[i] at point t, such that L[i].tag = g1 immediately before t and L[i].tag = g2 = ̸ 0 immediately after t. At point t, some process p executes line 20 or 21 of an SC(i, ·) call. Process p strongly protects some tag g ⋆ for i from the invocation of its call until at least point t, and g ⋆ = g1 if g1 ̸= 0. Proof. Since only lines 20 and 21 can change L[i].tag to a nonzero value, it follows that point t is the point that some process p executes one of the two lines. Since p does not return in line 15, by Lemma 11a, p strongly protects g ⋆ = d[i].tag for i when it invokes SC(i, ·). Moreover, since p does not invoke CL(i) in between invoking SC(i, ·) and its successful CAS() at point t, by Definition 9 g ⋆ remains strongly protected for i until at least point t. Finally, if g1 ̸= 0, then point t can only be an execution of line 20, in which case g ⋆ = g1 . ◀ ▶ Lemma 13. If at point t no process has a pending method call on object i and no process strongly protects a tag for i, then C[i] = 0. If at point t no process has a pending method call on any object and no process strongly protects any tag, then R[g] = 0 for all g ∈ {1, . . . , 2k}. Proof. Suppose that no process has a pending method call on object i and no process strongly protects any tag for i at point t. If d[i] ̸= ⊥ for some process, then d[i].tag = g for some tag g ∈ {0, . . . , 2k}, and from Lemma 11a p would strongly protect g at point t: thus, d[i] = ⊥ for all processes at point t. Lemma 4a and Lemma 6 then imply that C[i] = 0 at point t. If no process has any pending method call or strongly protects any tag at point t, then Lemma 4b and Lemma 6 imply that R[g] = 0 for all g. ◀ ▶ Lemma 14. If at point t no process has a pending method call for object i and no process strongly protects a tag for i, then L[i].tag = 0 at point t.

21

22

Efficient Randomized LL/SC that Preserves History Independence

Proof. The lemma is true for t = 0, since L[i].tag is initialized to zero for each i ∈ {1, . . . , m}. The Read(i) method does not affect which tags the calling process protects or the value of L[i].tag, so we need not consider it for this lemma. Similarly, by Lemma 11a, we have that method calls which respond in either line 15, 24, or 36 do not affect which tags the calling process strongly protects or the value of L[i].tag. Method calls on objects j ̸= i also do not affect whether the calling process strongly protects a tag for i of the value of L[i].tag. Note that all the method calls mentioned so far are either not for object i, or consist of at most one shared memory step. Therefore, none of them change whether a process has a pending method call for object i. We can therefore assume without loss of generality that point t is the response point of a method not discussed so far. By inspection of the code and by Definition 9 and Lemma 11a, the remaining method calls for which the calling process responds without strongly protecting a tag for i at the response point are exactly (a) an LL(i) call that responds in line 14, (b) an SC(i, ·) call that responds in line 23, (c) a CL(i) call that responds after line 24, and (d) a VL(i) call that responds in line 39. Since the cases of responding in either line 14, 23, or 39 all immediately follow a CL(i) call, we can further assume that point t is the response point of a CL(i) call c. By Lemma 13, C[i] = 0 at point t. Since call c does not respond in line 24, it decrements C[i] in line 27. Therefore, there is a point t′ at which C[i] is last decremented to zero before point t. (Since t is the response of a CL(i) call, and a CL(i) call does not respond in line 27 if it decrements C[i] to zero, it follows that t is not itself a point in which C[i] is decremented to zero.) Since only line 27 decrements C[i], it follows that some CL(i) call c′ (possibly c′ = c) decrements C[i] to zero at point t′ . By definition of t′ , C[i] = 0 throughout (t′ , t], and so by Lemma 10 we have that no tag is strongly protected for i at any point in (t′ , t]. From Lemma 12, no successful CAS() takes place on L[i] in (t′ , t] that sets L[i].tag to a nonzero value. It therefore suffices to show that L[i].tag = 0 at some point in (t′ , t]. Let p be the process executing c′ . Since no process has a pending method call for object i at point t, it follows that c′ responds no later than point t. If c′ responds in line 29, then L[i].tag = 0 when p executes line 28 after point t′ . Otherwise, since L[i].tag does not change to another nonzero value in (t′ , t], when p reads L[i] for the second time in line 31, either L[i].tag = 0, or L[i] is unchanged. If L[i] is unchanged in line 31, then since C[i] = 0 throughout (t′ , t], p executes line 33. If p does execute line 33, then either the CAS() successfully changes L[i].tag to zero, or it fails because L[i].tag is already zero. ◀ ▶ Theorem 15 (QHI-Preserving Property). If every process is idle and has no outstanding LL() operation at point t, then all values of C, R, and all tag fields of L are zero at point t. Proof. From Lemma 2, all values of d are ⊥ for each process at point t. From Lemma 11a, no process strongly protects a tag at point t. The theorem follows from Lemmas 13 and 14. ◀

4.3

Correctness

We conclude the analysis by proving, in Theorem 22, that the implementation is linearizable. We prove this last because the proof relies on several lemmas used to show complexity and history independence, making linearizability the most involved proof overall. ▶ Lemma 16. If tag g ̸= 0 is protected for some object at point t, then R[g] ̸= 0 at point t.

D. Bencivenga, H. Habashi, and P. Woelfel

Proof. Suppose that process p protects tag g = ̸ 0 for some object i at point t⋆ . Observe from Definition 9b that when a nonzero tag g is protected in line 7 or 31, the process p protecting it has incremented R[g] (in line line 6 or 30 respectively) and not yet decremented R[g]. If p protects g in line 7, then g ̸= 0, otherwise p would have returned in line 5. By Definition 9b, L[i] matches p’s variable pair (val, tag) at point t⋆ (so L[i].tag = tag = g); therefore, p returns in line 8. The next time that p decrements R[g] is thus either within a CL(i) call, in which case g ceases to be protected for i at that call’s invocation, or in line 10 of a subsequent invocation of LL(i). However, since only CL(i) can reset d[i] to ⊥ (in line 26), if p invokes LL(i) after point t⋆ without invoking CL(i) in between, then it invokes CL(i) in line 1. This makes g no longer protected for i before p decrements R[g] in line 10. In the case of line 31, p does not decrement R[g] until line 34, at which point p’s protection of g ends. Therefore, p does not decrement R[g] after point t⋆ until after g is no longer protected for i. The lemma then follows from Lemma 8. ◀ ▶ Lemma 17 (Protection Invariant). If tag g is protected for object i at point t, then (a) L[i].tag does not change from a value different from g to g at point t, and (b) if g is strongly protected for i at point t, then L[i].tag also does not change from a value different from g to zero at point t. Proof. We prove this lemma by contradiction. Suppose that the invariant is false, and let t be the first point at which it fails. Thus, at point t, there exists a tag g that is protected for i, and L[i].tag changes from a tag g ′ ̸= g to g, or to zero if g is strongly protected for i. Suppose first that b fails at point t, and therefore that g is strongly protected for i at point t, but that L[i].tag changes from some tag g ′ = ̸ g to zero at that point. Only line 33 can change L[i].tag to zero, since the only other lines which can change L[i].tag, namely lines 20 and 21, choose a tag that is nonzero (from line 18). Thus, there is a process p which executes a successful CAS() in line 33 at point t, changing L[i].tag from g ′ (p’s local value of tag) to zero. The if-conditions that p checks in lines 31 and 32 immediately before its CAS() at point t both return True, since p executes line 33. Therefore, there exist points tL < tC < t, such that L[i].tag = g ′ at point tL , and C[i] = 0 at point tC . From Definition 9b, g ′ becomes protected for i at point tL , and it remains protected until p executes line 34, which is after point t. From Lemma 10, g is not strongly protected for i at point tC . Since by assumption g is strongly protected for i at point t > tC , g becomes strongly protected for i at some point t⋆ ∈ (tC , t). By Definition 9, L[i].tag = g at point t⋆ . Since L[i].tag = g ′ ̸= g just before point t > t⋆ , there is a point t† ∈ (t⋆ , t) at which L[i].tag changes from some value different from g ′ (possibly g) to g ′ . But since g ′ is protected for i throughout (tL , t] (recall that tL < tC < t⋆ < t† < t), point t† violates a, contradicting that t is the first point at which the invariant fails. It remains to derive a contradiction for the case where a fails at point t, and therefore that L[i].tag changes from some tag g ′ = ̸ g to g at point t, while g is protected for i. Note that if g = 0, then it cannot become protected in line 31, as the CL() method would exit in line 29. Thus, if g = 0 is protected then it is protected during an LL() call, and therefore it is also strongly protected, so the contradiction follows from that just derived for b. We can therefore assume without loss of generality that g ̸= 0. From Lemma 12, there is a process p which executes a successful CAS() on L[i] as part of an SC(i, ·) call at point t, while strongly protecting some tag g ⋆ from the call’s invocation until at least point t. Let tR < t be the last point before t when p reads R in line 19, and therefore reads R[g] = 0 and breaks out of the loop. Using Lemma 16, it follows that g

23

24

Efficient Randomized LL/SC that Preserves History Independence

is not protected for i at point tR , and therefore that g = ̸ g ⋆ . Thus, there exists a point ⋆ t ∈ (tR , t) at which g becomes protected for i. By Definition 9, L[i].tag = g at point t⋆ . Since L[i].tag = g ′ ̸= g immediately before t, it follows that there exists another point t† ∈ (t⋆ , t) at which L[i].tag changes from some value different from g ′ (possibly g) to g ′ . (We thus have that tR < t⋆ < t† < t.) Suppose that g ′ ̸= 0. By Lemma 12, g ′ = g ⋆ . In that case, L[i].tag changes from some value different from g ⋆ to g ⋆ at point t† . Since g ⋆ is protected for i throughout [tR , t] ∋ t† , this violates a at point t† < t. Otherwise, g ′ = 0. Thus, at point t† , L[i].tag changes from a nonzero tag g † to zero. If † g = ̸ g ⋆ , then this violates b at point t† < t, since g ⋆ is strongly protected for i at point † t ∈ (tR , t). If g † = g ⋆ , then since L[i].tag = g = ̸ g ⋆ at point t⋆ , there is a point in (t⋆ , t† ) at which L[i].tag changes from some value different from g ⋆ (possibly g) to g ⋆ . Since g ⋆ is protected for i throughout [tR , t] ⊃ (t⋆ , t† ), this violates a before point t† < t. Thus, all possible cases contradict that t is the first point which violates the invariant. ◀ ▶ Lemma 18. If an SC(i, ·) operation has a successful CAS() at point t, then L[i].tag changes from some tag g to a new tag g ′ ∈ / {g, 0} at point t. Proof. The fact that the new tag g ′ = ̸ 0 follows from the fact that line 18 chooses a nonzero value for the new tag. Thus, if the old tag g = 0, then the lemma follows immediately. Suppose instead that g ̸= 0, and therefore that the calling process p executes the successful CAS() in line 20, and g = d[i].tag. To show the lemma, it suffices to prove that g ̸= g ′ . From Lemma 12, since g = ̸ 0, g is protected when p breaks out of its loop in line 19, upon reading R[g ′ ] = 0. By Lemma 16, g ′ is not protected when p executes line 19, so g = ̸ g′ . ◀ ▶ Definition 19 (Function lin). We define a function lin(c) from method calls c in an execution to points in time, and later (in Theorem 22) prove that they are correct linearization points. If c is an LL() call, then lin(c) depends on which line the method responds from. If it responds in line 5 or 14, then lin(c) occurs at line 3. If it responds in line 8 or 12, then lin(c) occurs at line 7. If c is an SC() call, then lin(c) occurs at its invocation if it returns in line 15, and otherwise lin(c) is the point of the last CAS() operation. That is, if the CAS() in line 20 succeeds, then lin(c) occurs at line 20, and if the first CAS() fails then lin(c) occurs at line 21. If c is a CL() call, then lin(c) occurs at its invocation. If c is a Read() call, then lin(c) occurs at line 35 (its only step). Finally, if c is a VL() call, then lin(c) occurs at its invocation if it returns in line 36, and otherwise lin(c) occurs at line 37. For an execution with pending invocations, lin(c) is undefined for pending LL() calls, and for other calls for which the line corresponding to lin(c) has not yet been executed. Note that since lin(c) is defined retroactively for LL() calls, it cannot be a strong linearization point [19]. ▶ Lemma 20. Suppose that c is either an SC(i, u) or VL(i) call by process p. The call returns True, and changes L[i].val to u at point lin(c), in the case of SC(i, u), if and only if (a) some tag becomes strongly protected for i by p at some point t < lin(c), and remains strongly protected by p throughout (t, lin(c)], and (b) no SC(i, ·) call has a successful CAS() in line 20 or 21 in the interval (t, lin(c)). Proof. We first prove the forward direction, so we first assume that c returns True. Since c returns True, it responds in either line 23 or 37. Since in particular it does not return in

D. Bencivenga, H. Habashi, and P. Woelfel

line 15 or 36, it means that d[i] ̸= ⊥ when p invokes c. By Lemma 11a, d[i].tag is strongly protected at c’s invocation, starting from some previous point t < lin(c), and by Definition 9 it remains protected until after lin(c). Thus, a is satisfied for some point t < lin(c). Let g ⋆ be the tag that p strongly protects at point t, i.e., its value of d[i].tag in call c. Suppose for the purpose of proving a contradiction that a successful CAS() from an SC(i, ·) call takes place in (t, lin(c)), and let t′ be the point of the first such CAS(). Note that the only other CAS() which can take place on L[i] happens in line 33, which also sets L[i].tag to zero. Since, by Definition 9, L[i].tag = g ⋆ at point t, it follows that L[i].tag is either g ⋆ or zero immediately before point t′ . By Lemma 18, L[i].tag changes to a different and nonzero value at point t′ , and by Lemma 17, L[i].tag does not change to g ⋆ at point t′ since g ⋆ is protected at that point. Thus, L[i].tag changes to some nonzero tag distinct from g ⋆ at point t′ . Applying Lemma 17 to each successful CAS() on L[i] in (t′ , lin(c)) (if any), we obtain that L[i].tag can only change to other nonzero tags distinct from g ⋆ throughout the interval. But, since we assume that c returns True, and lin(c) occurs at line 20, 21, or 37, it follows from the code that L[i].tag ∈ {g ⋆ , 0} immediately before lin(c), which is a contradiction. Thus, b follows, finishing the proof for the forward direction. It remains to show the reverse direction, so we assume that a and b both hold for c. Like the forward case, let g ⋆ be the tag that p strongly protects throughout (t, lin(c)], and we obtain from Definition 9 that L[i].tag = g ⋆ at point t. From Lemma 11a, p’s value of d[i].tag is g ⋆ at c’s invocation, and in particular p does not return in line 15 or 36. From b, no successful CAS() from an SC(i, ·) call takes place throughout (t, lin(c)). The only other line that can change L[i] is line 33, which changes L[i].tag to zero while keeping L[i].val unchanged. It follows that L[i].tag ∈ {g ⋆ , 0} immediately before point lin(c), and that L[i].val is unchanged throughout (t, lin(c)). From Lemma 11b, p’s value of d[i].val equals L[i].val from c’s invocation until just before lin(c), since c’s invocation is in the interval (t, lin(c)). If c is a VL(i) call, then the call returns True because g ⋆ is p’s value of d[i].tag. If c is an SC(i, ·) call and its CAS() in line 20 succeeds, then the call returns True. Otherwise, the CAS() in line 20 fails, so p performs a second CAS() in line 21, and lin(c) is the point of that second CAS(). Since the only possible transition of L[i].tag in (t, lin(c)) is from g ⋆ to zero, it follows that L[i].tag = 0 when p executes line 20, and therefore remains at zero immediately before lin(c). Since L[i].val = d[i].val just before lin(c), the second CAS() succeeds. ◀ ▶ Lemma 21. Suppose that c is an LL(i) call by process p, such that lin(c) = t and that the call responds at point t′ . If some tag becomes strongly protected for object i by p during the call, then it becomes strongly protected at point t. Otherwise, some process q = ̸ p has a SC(i, ·) call c′ with a successful CAS() at point lin(c′ ), such that t < lin(c′ ) < t′ . Proof. Combining Definitions 9 and 19, an LL() call c that responds in line 5, 8, or 12 causes a tag to become strongly protected at lin(c), and an LL() call that responds in line 14 does not strongly protect any tag, proving the first claim. If c responds in line 14, then p’s local variable tag = ̸ 0 and tag ′ ∈ / {tag, 0}. In particular, at point t⋆ ∈ (t, t′ ), p executes line 7, in ′ which it reads tag from L[i].tag. Thus, there is some point t† ∈ (t, t⋆ ) at which L[i].tag first changes to a value not in {tag, 0}. The only lines which can change L[i].tag to a nonzero value are a successful CAS() in lines 20 and 21, and by Definition 19 such a successful CAS() operation is point lin(c′ ) of an SC(i, ·) call c′ . Hence, t† = lin(c′ ) for some SC(i, ·) call c′ with a successful CAS() operation. Moreover, since c′ and c overlap, it follows that c′ ’s calling process q ̸= p. ◀

25

26

Efficient Randomized LL/SC that Preserves History Independence

▶ Theorem 22 (Linearizability). The LL/SC implementation is linearizable according to the sequential specification, with lin(c) as the linearization point for each call c. Proof. Consider an execution of LL/SC objects using this implementation. For each pending call c in the execution such that lin(c) is undefined according to Definition 19, we remove c from the linearization. For each CL() call invoked internally from an LL(), SC() or VL() call, we also remove it from the linearization. We construct the linearization from the remaining calls, sorting them by lin(c). We prove that this linearization is correct, by induction over calls c sorted by lin(c). Specifically, we prove that each call c returns a valid response and correctly affects the interpreted abstract state of the system. We inductively show that the interpreted value of LL/SC object i is L[i].val before and after each linearization point. This is true initially since L[i].val is initialized to ui , the application-dependent initial value for LL/SC object i. Recall from the sequential specification (Section 2.1) that the context bit ℓp of object i equals 1 (i.e., p has an open link to i) immediately before a given point t of a sequential execution if and only if an LL(i) call by process p takes place at some point t′ < t in the sequential execution, no SC(i) call by any process takes place in (t′ , t), and no CL(i) call by p takes place in (t′ , t). It also follows from the sequential specification that the context bit only directly affects the behaviour of SC(i) and VL(i) calls. As such, it suffices to show that SC(i) and VL(i) calls return True (and change L[i].val, in the case of SC()), if and only if the relevant context bit should be 1 immediately before the respective call in the linearization. If c is a Read(i) or LL(i) call, then its correctness follows from the fact that the call returns L[i].val at lin(c). If an SC(i, u) call c returns True, then L[i].val = u immediately after lin(c), since by Definition 19 c has a successful CAS() changing L[i].val to u at point lin(c). It also follows from the code that this is the only situation in which L[i].val can change. Therefore, if c is an SC(i, u) or VL(i) call by process p, we only need to show that it returns True if and only if the interpreted context bit ℓp = 1, based on the three conditions listed earlier. Suppose that an SC(i, u) or VL(i) call c does return True, and we will show that ℓp = 1 according to the three conditions. By Lemma 20a, there is a point t < lin(c) at which some tag g becomes strongly protected for i by c’s calling process p, and it remains strongly protected until at least lin(c). By Definition 9, only an LL(i) call c′ by p can cause p to strongly protect g, and by Lemma 21, g becomes strongly protected at point lin(c′ ). By Lemma 20b, no SC(i, ·) call has a successful CAS() in the interval (lin(c′ ), lin(c)). Since an SC(i, ·) call s with a successful CAS() returns True and has lin(s) at the point of that CAS(), it follows that there is no such call s with lin(c′ ) < lin(s) < lin(c). Since a CL(i) call by p ends its strong protection of any tag for i, and g remains strongly protected from lin(c′ ) until at least lin(c), it follows that p does not call CL(i) in between c′ and c. Therefore, the three points are satisfied and the interpreted context bit ℓp = 1 immediately before lin(c), as required. Now suppose that the interpreted context bit ℓp = 1 immediately before call lin(c) for an SC(i, u) or VL(i) call c by process p. Then there is an LL(i) call c′ by p with lin(c′ ) < lin(c), such that no SC(i, ·) call returns True in between calls c′ and c, and p does not directly call CL(i) in between c′ and c. In particular, no successful CAS() from an SC(i, ·) call s such that lin(c′ ) < lin(s) < lin(c). Suppose without loss of generality that c′ is the last LL(i) call by p before c in the linearization (if the three conditions hold for an earlier LL(i) call, then they also hold for

D. Bencivenga, H. Habashi, and P. Woelfel

c′ ). From Lemma 21, some tag g becomes strongly protected by p at point lin(c′ ) (since p responds from c′ before it invokes c). In order to use Lemma 20, we need to show that this strong protection lasts until at least lin(c), and in particular that p does not indirectly call CL(i) in between lin(c′ ) and lin(c). (Recall that indirect calls of CL() are removed from the linearization). The possible indirect calls of CL(i) are in line 1, 13, 22, and 38, so we will show that p does not execute any of these lines in between lin(c′ ) and lin(c) by deriving contradictions for each case. For line 1, since the line occurs before any possible line mapped to by lin for LL(), it would have to be part of an LL(i) call after c′ , which contradicts that c′ is the last LL(i) call by p before c. For line 13, by the above arguments it should be part of call c′ , but by Definition 9 and inspection of the code, no tag becomes strongly protected during c′ , which contradicts that some tag does become strongly protected at point lin(c′ ). Line 22 would be part of an SC(i, ·) call, so we will show that p does not make any such call in between c′ and c. If such a call were to return True, this contradicts the assumption there is no SC(i, ·) call which returns True in the linearization in between calls c′ and c. If such a call were to return False, then by the inductive hypothesis there is another SC(i, ·) call s which returns True with lin(c′ ) < lin(s) < lin(c), and this also contradicts our assumption. This last argument also applies if p executes line 38 in between lin(c′ ) and lin(c), since that line is only executed in a VL(i) call which returns False. We therefore have that a tag becomes strongly protected by p for i at point lin(c′ ) and remains so until at least point lin(c), and that no CAS() from an SC(i, ·) call succeeds in between lin(c′ ) and lin(c). Thus, from Lemma 20, c does return True. Since CL() only affects ℓp , which itself only becomes visible via SC() and VL() calls which we have already covered, the proof is complete. ◀

5

Conclusion

In this paper we presented a new randomized implementation of multiple LL/SC objects from FAID and CAS that advances the state of the art in two ways: First, it is the most space-efficient solution that achieves expected constant step complexity without relying on unbounded sequence numbers. Second, it is the first wait-free algorithm that preserves quiescent history independence in concurrent data structures. It is perhaps surprising that QHI-preserving LL/SC can be achieved not only through inefficient constructions, but also via an algorithm that achieves the best known asymptotic bounds in both step and space complexity. We believe that the improvement on space complexity is an important complexity theoretical contribution, and that the algorithm is useful in real applications. In particular, our algorithm renders the history-independent hash table of [8] practically implementable on hardware (as it relies on LL/SC, which is not available in hardware) without an impact on its asymptotic efficiency. While there are not yet many QHI algorithms that use LL/SC, we believe it is applicable to many future algorithms, because non-QHI algorithms typically do not need method calls of some operations to rely on LL()’s from other operations. Our work complements, rather than replaces, the algorithms of Blelloch and Wei [14] and Jayanti and Petrovic [32]. In contrast to their approaches, our construction requires augmenting LL/SC values with small bounded tags stored in CAS objects and, unlike the algorithm of Blelloch and Wei, does not support multi-word LL/SC. Achieving these properties simultaneously with our space bounds remains an important open problem. Other open problems include finding lower bounds on space complexity for deterministic

27

28

Efficient Randomized LL/SC that Preserves History Independence

or even randomized algorithms, as well as a general construction for inserting CL() operations into implementations using LL/SC while preserving their asymptotic space complexity. Another direction would be to determine whether our space complexity and/or QHI-preserving property is achievable with a strongly linearizable implementation, with a randomized algorithm under the strong adaptive adversary, with a deterministic algorithm, or under different attack models.

References 1

Umut A. Acar, Guy E. Blelloch, Robert Harper, Jorge L. Vittes, and Shan Leung Maverick Woo. Dynamizing static algorithms, with applications to dynamic trees and history independence. In Proceedings of the 15th ACM-SIAM Symposium on Discrete Algorithms (SODA), pages 531–540, 2004. URL: http://dl.acm.org/citation.cfm?id=982792.982871.

2

Yehuda Afek, Dalia Dauber, and Dan Touitou. Wait-free made fast. In Proceedings of the 27th Annual ACM Symposium on Theory of Computing (STOC), pages 538–547, 1995. doi:10.1145/225058.225271.

3

Zahra Aghazadeh and Philipp Woelfel. On the time and space complexity of ABA prevention and detection. In Proceedings of the 34th ACM Symposium on Principles of Distributed Computing (PODC), pages 193–202, 2015. doi:10.1145/2767386.2767403.

4

Zahra Aghazadeh and Philipp Woelfel. Upper bounds for boundless tagging with bounded objects. In Proceedings of the 30th International Symposium on Distributed Computing (DISC), pages 442–457, 2016. doi:10.1007/978-3-662-53426-7_32.

5

James H. Anderson and Mark Moir. Universal constructions for large objects. In Proceedings of the 9th International Workshop on Distributed Algorithms (WDAG), volume 972, pages 168–182, 1995. doi:10.1007/BFB0022146.

6

James H. Anderson and Mark Moir. Universal constructions for multi-object operations. In Proceedings of the 14th ACM Symposium on Principles of Distributed Computing (PODC), pages 184–193, 1995. doi:10.1145/224964.224985.

7

Hagit Attiya, Michael A. Bender, Martín Farach-Colton, Rotem Oshman, and Noa Schiller. History-independent concurrent objects. In Ran Gelles, Dennis Olivetti, and Petr Kuznetsov, editors, Proceedings of the 43rd ACM Symposium on Principles of Distributed Computing (PODC), pages 14–24, 2024. doi:10.1145/3662158.3662814.

8

Hagit Attiya, Michael A. Bender, Martín Farach-Colton, Rotem Oshman, and Noa Schiller. History-independent concurrent hash tables. In Proceedings of the 57th Annual ACM Symposium on Theory of Computing (STOC), pages 1283–1294, 2025. doi:10.1145/3717823. 3718283.

9

Greg Barnes. A method for implementing lock-free shared-data structures. In Proceedings of the 5th ACM Symposium on Parallelism in Algorithms and Architectures (SPAA), pages 261–270, 1993. doi:10.1145/165231.165265.

10

Benyamin Bashari and Philipp Woelfel. An efficient adaptive partial snapshot implementation. In Proceedings of the 40th ACM Symposium on Principles of Distributed Computing (PODC), pages 545–555, 2021. doi:10.1145/3465084.3467939.

11

Naama Ben-David, David Yu Cheng Chan, Vassos Hadzilacos, and Sam Toueg. k-abortable objects: Progress under high contention. In Proceedings of the 30th International Symposium on Distributed Computing (DISC), pages 298–312, 2016. doi:10.1007/978-3-662-53426-7_22.

12

Michael A. Bender, Jon Berry, Rob Johnson, Thomas M. Kroeger, Samuel McCauley, Cynthia A. Phillips, Bertrand Simon, Shikha Singh, and David Zage. Anti-persistence on persistent storage: History-independent sparse tables and dictionaries. In Proceedings of the 35th ACM SIGACT-SIGMOD Symposium on Principles of Database Systems, pages 289–302, June 2016. doi:10.1145/2902251.2902276.

D. Bencivenga, H. Habashi, and P. Woelfel

13

Guy E. Blelloch and Daniel Golovin. Strongly history-independent hashing with applications. In Proceedings of the 48th Annual IEEE Symposium on Foundations of Computer Science (FOCS), pages 272–282, 2007. doi:10.1109/FOCS.2007.36.

14

Guy E. Blelloch and Yuanhao Wei. LL/SC and Atomic Copy: Constant Time, Space Efficient Implementations Using Only Pointer-Width CAS. In Proceedings of the 34th International Symposium on Distributed Computing (DISC), pages 5:1–5:17, 2020. doi:10.4230/LIPIcs. DISC.2020.5.

15

Niv Buchbinder and Erez Petrank. Lower and upper bounds on obtaining history independence. Information and Computation, 204(2):291–337, 2006. doi:10.1016/J.IC.2005.11.001.

16

Tushar Deepak Chandra, Prasad Jayanti, and King Tan. A polylog time wait-free construction for closed objects. In Proceedings of the 17th ACM Symposium on Principles of Distributed Computing (PODC), pages 287–296, 1998. doi:10.1145/277697.277753.

17

David L. Detlefs, Paul A. Martin, Mark Moir, and Guy L. Steele Jr. Lock-free reference counting. Distributed Computing, 15(4):255–271, December 2002. doi:10.1007/S00446-002-0079-Z.

18

Simon Doherty, Maurice Herlihy, Victor Luchangco, and Mark Moir. Bringing practical lock-free synchronization to 64-bit applications. In Proceedings of the 23rd ACM Symposium on Principles of Distributed Computing (PODC), pages 31–39, 2004. doi:10.1145/1011767. 1011773.

19

Wojciech Golab, Lisa Higham, and Philipp Woelfel. Linearizable implementations do not suffice for randomized distributed computation. In Proceedings of the 43rd Annual ACM Symposium on Theory of Computing (STOC), pages 373–382, 2011. doi:10.1145/1993636.1993687.

20

Daniel Golovin. B-treaps: A uniquely represented alternative to b-trees. In Proceedings of the 36th International Colloquium on Automata, Languages, and Programming (ICALP), pages 487–499, 2009. doi:10.1007/978-3-642-02927-1_41.

21

Daniel Golovin. The b-skip-list: A simpler uniquely represented alternative to b-trees. arXiv preprint, 2010. arXiv:1005.0662.

22

Michael B. Greenwald. Non-blocking synchronization and system design. PhD thesis, Stanford University, 1999. URL: https://searchworks.stanford.edu/view/4772015.

23

Jason D. Hartline, Edwin S. Hong, Alexander E. Mohr, William R. Pentney, and Emily Rocke. Characterizing history independent data structures. In Proceedings of the 13th Annual International Symposium on Algorithms and Computation (ISAAC), pages 229–240, November 2002. doi:10.1007/3-540-36136-7_21.

24

Jason D. Hartline, Edwin S. Hong, Alexander E. Mohr, William R. Pentney, and Emily C. Rocke. Characterizing history independent data structures. Algorithmica, 42(1):57–74, 2005. doi:10.1007/S00453-004-1140-Z.

25

Maurice Herlihy. A methodology for implementing highly concurrent objects. ACM Transactions on Programming Languages and Systems, 15(5):745–770, 1993. doi:10.1145/161468. 161469.

26

Maurice P. Herlihy and Jeannette M. Wing. Linearizability: A correctness condition for concurrent objects. ACM Transactions on Programming Languages and Systems, 12(3):463– 492, 1990. doi:10.1145/78969.78972.

27

Amos Israeli and Lihu Rappoport. Disjoint-access-parallel implementations of strong shared memory primitives. In Proceedings of the 13th ACM Symposium on Principles of Distributed Computing (PODC), pages 151–160, 1994. doi:10.1145/197917.198079.

28

Prasad Jayanti. f -arrays: implementation and applications. In Proceedings of the 21st ACM Symposium on Principles of Distributed Computing (PODC), pages 270–279, 2002. doi:10.1145/571825.571875.

29

Prasad Jayanti. Adaptive and efficient abortable mutual exclusion. In Proceedings of the 22nd ACM Symposium on Principles of Distributed Computing (PODC), pages 295–304, 2003. doi:10.1145/872035.872079.

29

30

Efficient Randomized LL/SC that Preserves History Independence

30

31

32

33

34

35

36 37

38

39

40

41

42 43

44

45

46

Prasad Jayanti. An optimal multi-writer snapshot algorithm. In Proceedings of the 37th Annual ACM Symposium on Theory of Computing (STOC), pages 723–732, 2005. doi: 10.1145/1060590.1060697. Prasad Jayanti, Siddhartha Jayanti, and Sucharita Jayanti. Durable algorithms for writable LL/SC and CAS with dynamic joining. In Proceedings of the 27th International Symposium on Distributed Computing (DISC), volume 281 of LIPIcs, pages 25:1–25:20, 2023. doi: 10.4230/LIPICS.DISC.2023.25. Prasad Jayanti and Srdjan Petrovic. Efficient and practical constructions of LL/SC variables. In Proceedings of the 22nd ACM Symposium on Principles of Distributed Computing (PODC), PODC ’03, pages 285–294, New York, NY, USA, 2003. Association for Computing Machinery. doi:10.1145/872035.872078. Prasad Jayanti and Srdjan Petrovic. Efficient wait-free implementation of multiword LL/SC variables. In Proceedings of the 25th International Conference on Distributed Computing Systems (ICDCS), pages 59–68, 2005. doi:10.1109/ICDCS.2005.29. Prasad Jayanti and Srdjan Petrovic. Efficiently implementing a large number of LL/SC objects. In Proceedings of 9th International Conference On Principles Of Distributed Systems (OPODIS), pages 17–31, 2005. doi:10.1007/11795490_4. Prasad Jayanti and Srdjan Petrovic. Efficiently implementing LL/SC objects shared by an unknown number of processes. In International Workshop on Distributed Computing (IWDC 2005), pages 45–56, 2005. doi:10.1007/11603771_5. Chaitanya Koparkar. A primer on pointer tagging. XRDS, 29(1):66–68, 2022. doi:10.1145/ 3558200. Victor Luchangco, Mark Moir, and Nir Shavit. Nonblocking k-compare-single-swap. In Proceedings of the 25th ACM Symposium on Parallelism in Algorithms and Architectures (SPAA), pages 314–323, 2003. doi:10.1145/777412.777468. Daniele Micciancio. Oblivious data structures: applications to cryptography. In Proceedings of the 29th Annual ACM Symposium on Theory of Computing (STOC), pages 456–464, 1997. doi:10.1145/258533.258638. Maged M. Michael. Practical lock-free and wait-free LL/SC/VL implementations using 64-bit CAS. In Proceedings of the 18th International Symposium on Distributed Computing (DISC), pages 144–158, 2004. doi:10.1007/978-3-540-30186-8_11. Mark Moir. Practical implementations of non-blocking synchronization primitives. In Proceedings of the 16th ACM Symposium on Principles of Distributed Computing (PODC), PODC ’97, pages 219–228, New York, NY, USA, 1997. Association for Computing Machinery. doi:10.1145/259380.259442. Mark Moir. Transparent support for wait-free transactions. In Proceedings of the 11th International Workshop on Distributed Algorithms (WDAG), pages 305–319, 1997. doi: 10.1007/BFb0030692. Mark Moir. Laziness pays! Using lazy synchronization mechanisms to improve non-blocking constructions. Distributed Computing, 14(4):193–204, 2001. doi:10.1007/s004460100063. Fatemeh Naderi-Semiromi and Philipp Woelfel. Strongly linearizable LL/SC from CAS. In Proceedings of the 43rd ACM Symposium on Principles of Distributed Computing (PODC), pages 443–453, 2024. doi:10.1145/3662158.3662800. Moni Naor, Gil Segev, and Udi Wieder. History-independent cuckoo hashing. In Proceedings of the 35th International Colloquium on Automata, Languages, and Programming (ICALP), pages 631–642, 2008. doi:10.1007/978-3-540-70583-3_51. Moni Naor and Vanessa Teague. Anti-persistence: history independent data structures. In Proceedings of the 33 Annual ACM Symposium on Theory of Computing (STOC), pages 492–501, 2001. doi:10.1145/380752.380844. Nir Shavit and Dan Touitou. Software transactional memory. In Proceedings of the 14th ACM Symposium on Principles of Distributed Computing (PODC), pages 204–213, 1995. doi:10.1145/224964.224987.

D. Bencivenga, H. Habashi, and P. Woelfel

47

48

Julian Shun and Guy E Blelloch. Phase-concurrent hash tables for determinism. In Proceedings of the 26th ACM Symposium on Parallelism in Algorithms and Architectures (SPAA), pages 96–107. ACM, 2014. doi:10.1145/2612669.2612687. John D. Valois. Lock-free linked lists using compare-and-swap. In Proceedings of the 14th ACM Symposium on Principles of Distributed Computing (PODC), pages 214–222, 1995. doi:10.1145/224964.224988.

31

Related documents

• Bayesian Efficient Coding#10030
• Continuity and completeness of strongly independent preorders#752029
• The Art of the Probable: Literature and Probability#67132
• KLOD: Locality-Preserving Knowledge Editing via Non-Target Distribution Preservation#781125
• KLOD: Locality-Preserving Knowledge Editing via Non-Target Distribution Preservation#779750