Strong Linearizability Without Compare&Swap: The Case of Bags

Concurrent data structures are often built using linearizable implementations of objects as if they were atomic objects. Although linearizability is the usual correctness condition for concurrent algorithms, there are scenarios where composing linearizable implementations does not preserve desired properties. Namely, an algorithm that uses atomic objects may lose some of its properties when these atomic objects are replaced by linearizable implementations. Specifically, linearizability does not preserve hyperproperties (properties of sets of executions), for example, probability distributions of events for randomized programs and security properties such as noninterference [11, 6]. This can be rectified by using strongly-linearizable implementations [11]. They guarantee that the linearization of a prefix of a concurrent execution is a prefix of the linearization of the whole execution. This means that the linearization of operations in an execution prefix cannot depend on later events in the execution.

Attiya, Castaneda, and Enea [3] observed that strongly-linearizable implementations of objects typically use compare&swap objects, which can be used to solve consensus among any number of processes. They provided strongly-linearizable implementations of some objects, such as a wait-free single-writer snapshot object and a wait-free max register from a fetch&add object, and a lock-free, readable, resettable test&set object and a lock-free, readable, fetch&increment object from an infinite array of test&set objects and registers. Both fetch&add and test&set objects are less powerful than a compare&swap object.

In this work, we aim to further explore the power of these well-studied building blocks in the context of strong linearizability. Specifically, we investigate strongly-linearizable implementations of a bag from these primitives. Establishing the existence of such implementations deepens our understanding of the circumstances under which these primitives can be used to achieve strong linearizability.

A bag is a multiset to which processes can insert elements and from which they can take unspecified elements. A concurrent bag is an abstraction of the interaction between producers and consumers and is commonly used to distribute tasks among processes for load balancing and improved scalability.

Queues and stacks have strongly-linearizable implementations from compare&swap objects [15, 21, 19]. A bag has a straightforward implementation from a stack or a queue. Therefore, a bag has a strongly-linearizable implementation from compare&swap objects. Although there is a wait-free, linearizable implementation of a stack from registers, test&set objects, and a readable fetch&increment object [1] and there is a lock-free, linearizable implementation of a queue from the same set of objects [16], neither of these implementations is strongly-linearizable. In fact, Attiya, Castañeda, and Hendler [5] proved that no lock-free, strongly-linearizable implementation of a stack or queue from such objects is possible. Attiya, Castañeda, and Enea [3] claimed that the lock-free linearizable implementation of a queue which appears in Figure 5, is a strongly-linearizable implementation of a bag. We give a counterexample to this claim in Appendix A. This was the starting point for our research.

The challenge when implementing a strongly-linearizable bag is to enable an operation that is trying to take an element from the bag to detect when the bag is empty. If elements can reside in multiple locations, it does not suffice for the operation to simply examine these locations one by one, concluding that the bag is empty if no elements are found. The problem is that new elements may have been added to locations after they were examined. Even if there was a configuration during the operation in which the bag was empty, it might not be possible to linearize the operation at this point while maintaining strong linearizability. For example, after this point, in an alternative execution, a value could be added to a location that the operation had not yet examined and the operation could return that value, instead of EMPTY.

We address this challenge in Section 4, modifying the lock-free, linearizable implementation of a queue by adding an additional readable fetch&increment object. This object is used by operations which are inserting elements into the bag to inform operations which are trying to take elements from the bag that the bag is no longer empty. We prove that the resulting algorithm is a strongly-linearizable implementation of a bag.Interestingly, although our algorithm is still a linearizable implementation of a queue, it is not a strongly-linearizable implementation of a queue.

A bag can grow arbitrarily large, so either the number of objects used to implement it or the size of the objects must be unbounded. An alternative is a $b$-bounded bag, which can simultaneously contain up to $b$ elements. Unfortunately, Attiya, Castaneda, and Enea [3] proved that a $b$-bounded bag shared by more than $2b$ processes has no lock-free, strongly-linearizable implementation from interfering objects [3]. However, we do provide a lock-free, strongly-linearizable implementation of a restricted version of a $b$-bounded bag, into which only one process, the producer, can insert elements. It uses a bounded number of registers, each of bounded size, and readable, resettable test&set objects. Before presenting this implementation, we give two different implementations of a 1-bounded bag with a single producer, which introduce some of the ideas that appear in our $b$-bounded bag implementation.

In Section 5, we present a wait-free, linearizable implementation of a 1-bounded bag. Note that it provides a stronger progress guarantee. To keep the space bounded, when the producer inserts an element into the bag, it may reuse objects previously used for other elements. It has to do this carefully, to avoid reusing objects that other processes may be poised to access. This requires delicate coordination between the producer and the consumers.

In Section 6, we present a lock-free, strongly-linearizable implementation of a 1-bounded bag. It combines the mechanism for detecting an empty bag from our lock-free, strongly-linearizable implementation of a bag and the mechanism for reusing objects from our wait-free, linearizable implementation of a 1-bounded bag.

Our lock-free, strongly-linearizable implementation of a $b$-bounded bag, for any value of $b$, is presented in Section 7. To enable the producer to detect when the bag is full, we use an approach that is similar to detecting when the bag is empty, but we have to ensure that these two mechanisms do not interfere with one another. In our implementation of a 1-bounded bag in Section 6, the producer determines whether the bag is empty or full by inspecting a single object. This makes this implementation both simpler and more efficient than the special case of our implementation of a $b$-bounded bag when $b=1$.

We consider an asynchronous system where processes communicate through operations applied to shared objects. Each type of object supports a fixed set of operations that can be applied to it. For example, a register supports read(), which returns the value of the register, and write($x$), which changes the value of the register to $x$.

Each process can be modelled as a deterministic state machine. A step by a process specifies an operation that the process applies to a shared object and the response, if any, that the operation returns. The process can then perform local computation, perhaps based on the response of the operation, to update its state. A process can crash, after which it takes no more steps.

A configuration consists of the state of every process and the value of every shared object. In an initial configuration, each process is in its initial state and each object has its initial value. An execution is an alternating sequence of configurations and steps, starting with an initial configuration. If an execution is finite, it ends with a configuration. The order in which processes take steps is determined by an adversarial scheduler.

The consensus number of an object is the largest positive integer $n$ such that there is an algorithm solving consensus among $n$ processes using only instances of this object and registers. A register has consensus number 1. Another example of an object with consensus number 1 is an ABA-detecting register [2]. It supports dWrite($x$) and dRead(). When dWrite($x$) is performed, $x$ is stored in the object. When a process $p$ performs dRead(), the value stored in the object is returned, together with an output bit, which is true if and only if process $p$ has previously performed dRead() and some dWrite() has been performed since its last dRead(). We use a restricted version of an ABA-detecting register, where dWrite() does not have an input parameter and dRead() simply returns the output bit.

A test&set object has initial value 0 and supports only one operation, t&s(). If the value of the object was 0, this operation changes its value to 1 and returns 0. If the value of the object was 1, it just returns 1. In the first case, we say that the t&s was successful and, in the second case, we say that it was unsuccessful. A resettable test&set object is like a test&set object, except that it also supports reset(), which changes the value of the object to 0. A fetch&increment object supports f&i(), which increases the value of the object by 1 and returns the previous value of the object. A compare&swap object supports the operation c&s($u,v$), which checks whether the object has value $u$ and, if so, changes its value to $v$. It always returns the value of the object immediately before the operation was performed. For any type of object that does not support read, its readable version supports read in addition to its other operations.

Two operations, $op$ and $o{p}^{\prime }$, commute if, whenever $op$ is applied to the object followed by $o{p}^{\prime }$, the resulting value of the object is the same as when $o{p}^{\prime }$ is applied followed by $op$. Note that the responses to $op$ and $o{p}^{\prime }$ may be different when these operations are applied in the opposite order. The operation $o{p}^{\prime }$ overwrites the operation $op$ if, whenever $op$ is applied to the object followed by $o{p}^{\prime }$, the resulting value of the object is the same as when only $o{p}^{\prime }$ is applied. Note that the response to $o{p}^{\prime }$ may be different depending on whether $op$ was applied. An object is interfering if every two of its operations either commute or one of them overwrites the other. All interfering objects have consensus number at most 2 [13]. Registers are interfering. The test&set, resettable test&set, and fetch&increment objects and their readable versions are all interfering and have consensus number 2.

Both a stack and a queue are examples of non-interfering objects with consensus number 2 [13]. The value of these objects is an unbounded sequence of elements, which is initially empty. A stack supports push($x$) and pop(), whereas a queue supports enqueue($x$) and dequeue().

A bag is a non-interfering object whose value is an initially empty multiset of elements. The number of elements that can be in the multiset is unbounded. The elements are taken from a set of values $V$ that does not include $\perp$. A bag supports two operations, Insert($x$) where $x\in V$ and Take. When Insert($x$) is performed, the element $x$ is added to the multiset. It does not return anything. If the multiset is not empty, a Take operation removes an arbitrary element from the multiset and returns it. In this case, we say that the operation is successful. If the multiset is empty, then Take returns EMPTY and we say that it is unsuccessful. Note that this specification is nondeterministic.

A b-bounded bag object is an object whose value is a multiset of at most $b$ elements. If the multiset contains fewer than $b$ elements when Insert($x$) is performed, the element $x$ is added to the multiset and OK is returned. If the multiset already contains $b$ elements, the value of the bag does not change and FULL is returned. For simplicity, we assume no value repetitions in the bounded bags in our proofs.

An implementation of an object $O$ shared by a set of processes $P$ from a collection of objects $C$ provides a representation of $O$ using objects in $C$ and algorithms for each process in $P$ to perform each operation supported by $O$. In an execution, an operation on an implemented object begins when a process performs the first step of its algorithm for performing this operation and is completed at the step in which the process returns from the algorithm, with the response of the operation, if any.

A bag has a straightforward implementation from a stack or a queue. The multiset is represented by the sequence, Insert($x$) is performed by applying push($x$) or enqueue($x$) and Take() is performed by applying pop() or dequeue(). Thus a bag has consensus number at most 2.

There is a simple algorithm for solving consensus among 2 processes using two single-writer registers and a bag initialized with one element: To propose the value $x$, a process writes $x$ to its single-writer register and then performs a Take() operation on the bag. If the Take() returns an element, the process returns $x$. Otherwise, it reads and returns the value that the other process wrote to its single-writer register. It follows from Borowsky, Gafni, and Afek’s Initial State Lemma [7, Lemma 3.2], that consensus among 2 processes can be solved from registers and two initially empty bags. Thus, a bag has consensus number exactly 2.

For any execution, $\alpha$, consider an ordering of every completed operation and a (possibly empty) subset of the operations that have begun, but have not completed, such that, for every completed operation, $op$, each of these operations that begins after $op$ has completed is ordered after $op$. A way to obtain such an ordering is to first assign a linearization point in $\alpha$ to each of these operations within its operation interval, i.e., no operation is linearized before it begins or after it has completed. Then specify an ordering of the operations that are linearized at the same point. Suppose there is a sequential execution in which the operations in the ordering are performed in order such that every completed operation in $\alpha$ has the same response as it does in this sequential execution. Then we say that the ordering is a linearization of $\alpha$.

An implementation of an object is linearizable [14] if each of its executions has a linearization. An implementation is strongly-linearizable [11] if there is a function $f$ that maps each execution $\alpha$ to a linearization of $\alpha$ such that, for every prefix ${\alpha }^{\prime }$ of $\alpha$, $f({\alpha }^{\prime })$ is a prefix of $f(\alpha )$.

An implementation is wait-free if, in every execution, every operation by a process that does not crash completes within a finite number of steps by that process. An implementation is lock-free if every infinite execution contains an infinite number of completed operations.

Even though there are wait-free, linearizable implementations of registers, max-registers, and single-writer snapshot objects from single-writer registers, Helmi, Higham, and Woelfel [12] proved that there are no lock-free, strongly-linearizable implementations. They also gave a wait-free, strongly-linearizable implementation of a bounded max-register from registers. Denysyuk and Woelfel [9] proved there are no wait-free, strongly-linearizable implementations of max-registers and single-writer snapshot objects from registers, although they gave lock-free strongly-linearizable implementations. Later, Ovens and Woelfel [20] gave lock-free, strongly-linearizable implementations of an ABA-detecting register and a single-writer snapshot object from a bounded number of bounded size registers.

Li [16] gave a lock-free, linearizable implementation of a queue from a fetch&increment object, an infinite array of test&set objects, and an infinite array of registers. He also gave a wait-free, linearizable implementation of a queue in which at most 2 processes may dequeue. It uses a fetch&increment object and infinite arrays of registers and test&set objects. David [8] gave a wait-free, linearizable implementation of a queue in which at most 1 process may enqueue. It uses registers, an infinite array of fetch&increment objects, and a two-dimensional infinite array of swap objects. It is unknown whether there is a wait-free, linearizable implementation of a queue from interfering objects in which any number of processes can enqueue and dequeue.

Afek, Gafni, and Morrison [1] gave a wait-free, linearizable implementation of a stack from interfering objects (specifically, a fetch&add object, registers, and test&set objects). Attiya and Enea [6] showed that this implementation is not strongly-linearizable. Attiya, Castañeda, and Enea [3] later proved that there is no lock-free, strongly-linearizable implementation of a stack or a queue shared by more than 2 processes from interfering objects.

Many universal constructions (for example, from compare&swap objects and registers or from consensus objects and registers) provide strongly-linearizable, wait-free implementations of any shared object [11]. Treiber [21, 19] gave a simple lock-free, strongly-linearizable implementation of a stack from compare&swap objects and registers. Michael and Scott [18] gave a lock-free, linearizable implementation of a queue from compare&swap objects and registers. Assuming nodes are never reused, it is possible to make a small modification to their implementation to make it strongly-linearizable [15].

The first algorithm we present is a strongly-linearizable implementation of an unbounded bag. The challenge in designing such an algorithm from interfering objects lies in identifying when the bag is empty. To address this, we use a readable fetch&increment object, Done, which an Insert operation increments as its last step, to inform Take operations that the bag is not empty. A detailed description of the algorithm follows.

The implementation uses an infinite array of registers, $Items$, in which elements that have been inserted into the bag are stored, together with an infinite array of test&set objects, $TS$. The process that performs a successful t&s() on $TS[i]$ returns the element stored in $Items[i]$ and removes it from the bag.

Each Insert($x$) operation begins by performing f&i() on a readable fetch&increment object, Allocated. This allocates the operation a new location within Items in which it writes $x$. Thus, the value of Allocated is the index of the last allocated location within Items. Finally, the operation performs f&i() on a second readable fetch&increment object, Done, to inform Take() operations about the insertion.

A Take() operation begins by reading Done and Allocated. Then it reads the allocated locations in Items. For each location, i, if Items[i] contains $x\ne \perp$, the operation performs t&s() on the corresponding test&set object, TS[i]. If this is successful, $x$ is returned. After reading all the allocated locations in Items without performing a successful t&s(), the operation rereads Done. If its value has not changed since the operation last read Done, EMPTY is returned. Otherwise, the operation repeats the entire sequence of steps. Note that it begins again starting from the first location, in case an Insert operation that was allocated an early location has recently written to that location. Pseudocode for our implementation of a bag appears in Figure 1.

Our first bounded bag algorithm from interfering objects is a wait-free, linearizable implementation of a bag that can contain at most one element. It is shared by $n$ processes, $P_1,\mathrm{\dots },P_n$, called consumers, that can perform Take() and a single process, called the producer, that can perform Insert($x$). To keep the space bounded, the producer reuses locations in Items to store new elements. The producer announces the most recent location it has allocated by writing it to the shared register Allocated. There is a resettable test&set object, instead of a test&set object, associated with each location in Items. An array, Hazards, of hazard pointers [17] is used to prevent multiple consumers from returning the same element, and to ensure that each element is consumed before being overwritten by a new element. Each consumer announces a location it is about to access and the producer avoids reusing the announced locations. Specifically, the producer avoids resetting the corresponding test&set objects and writing new elements to the corresponding locations in Items.

The producer maintains two persistent local variables, m, which is the last location in Items it allocated, and used, which is a set of locations it has used and will need to reset before they are reallocated. To eliminate the need for a special case to handle the first Insert call (which is the only one not preceded by a previous insertion), the initial state of the data structure is as if location 1 had been allocated to the producer, it had inserted an element into the bag in this location, and then this element had been taken by some consumer. This is simulated by setting the initial values of m, Allocated, and TS[1] to 1.

The producer begins an Insert($x$) operation by checking whether the test&set object, TS[m], in the last allocated location, m, is 0. If so, it returns FULL. Otherwise, it overwrites the element in Items[m] with $\perp$ and adds the index m to used. Afterwards, it collects the set of hazardous locations stored in Hazards. It then allocates an arbitrary location from $\{1,\mathrm{\dots },n+1\}$ that is not hazardous and announces this location by writing it to Allocated. Next, it resets the test&set for each location in used that is not hazardous. Then it removes these locations from used. Finally, it writes $x$ to the newly allocated location in Items and returns OK.

To perform a Take() operation, a consumer reads Allocated. It announces the location it read in Hazards and then reads the value in this location. If it is an element $x\ne \perp$, the consumer performs t&s() on the resettable test&set object for this location. It then clears its announcement. If the t&s() was successful, it returns $x$. If either $x=\perp$ or the t&s() was unsuccessful, it returns EMPTY.

If Items[$a$] contains an element $x\ne \perp$, but this element has already been taken from the bag, it is essential that no consumer can perform a successful t&s() on the associated test&set object, TS[$a$], and take the element again. To ensure this, a consumer, $P_i$ writes $a$ to Hazards[$i$] before reading Items[$a$]. This prevents the producer from resetting TS[$a$] while $P_i$ is poised to access TS[$a$].

After it has set Items[m] to $\perp$, but before resetting any test&set objects, the producer will collect the locations that appear in Hazards and refrain from resetting the test&set objects associated with the hazardous locations it collected. Hence, it will not reset a test&set object which any consumer is poised to access.

Assuming that the universe of elements that can be inserted into the bag is bounded, the registers used in the implementations store bounded values and thus, the amount of space used by the implementation is bounded. Pseudocode for our implementation appears in Figure 2.

Consider any execution consisting of operations on this data structure. We linearize the operations as follows:

• $\mathrm{■}$

  A Take() operation that performs a successful t&s() on Line 44 is linearized at this step. It returns the element it last read on Line 42.

• $\mathrm{■}$

  Consider a Take() operation, $tk$, that returns EMPTY. If Items[$a$] = $\perp$ or TS[$a$] = 1 when $tk$ read $a$ from Allocated on Line 40, then $tk$ is linearized at this step. Otherwise, we can show that some other Take() operation performed a successful t&s() on TS[$a$] after $tk$ performed Line 40, but before $tk$ returned. In this case, $tk$ is linearized immediately after the first such Take() operation.

• $\mathrm{■}$

  An Insert($x$) operation that reads 0 from TS[m] (on Line 28) is linearized at this read. It returns FULL.

• $\mathrm{■}$

  An Insert($x$) operation that writes $x$ on Line 37 is linearized at this write. It returns OK.

Because the code contains no unbounded loops, the implementation is wait-free. Keeping track of hazardous locations enables objects to be safely reused so that bounded space is used. However, this makes the algorithm and its proof of correctness more intricate. In the full version of the paper [10], we prove that Figure 2 is a linearizable implementation of a 1-bounded bag. Appendix C shows that it is not strongly-linearizable.

In this section, we present a lock-free, strongly-linearizable implementation of a bag that can contain at most one element. It is shared by $n$ processes, $P_1,\mathrm{\dots },P_n$, called consumers, that can perform Take() and a single process, called the producer, that can perform Insert($x$). It combines ideas from our lock-free, strongly-linearizable implementation of an unbounded bag in Section 4 and our wait-free, linearizable implementation of a 1-bounded bag in Section 5. To keep the space bounded, we use an ABA-detecting register for Done, instead of a readable fetch&increment object. An ABA-detecting register has a lock-free, strongly-linearizable implementation from registers using bounded space [20].

An Insert($x$) operation by the producer is the same as in the wait-free linearizable implementation presented in the previous section, except the producer writes to the ABA-detecting register Done before it returns OK.

To perform a Take() operation, a consumer, $P_i$, reads Done and Allocated. In Hazards[i], it announces the location, a, that it read from Allocated. Then $P_i$ reads Items[a] and, if it contains an element $x\ne \perp$, then $P_i$ performs t&s() on TS[a]. Next $P_i$ clears its announcement. If the t&s() was successful, $P_i$ returns $x$. If either $x=\perp$ or the t&s() was unsuccessful, $P_i$ rereads Done and, if its value has not changed since $P_i$’s previous read, $P_i$ returns EMPTY. Otherwise, $P_i$ repeats the entire sequence of steps. Pseudocode for our implementation appears in Figure 3.

Our final algorithm is a lock-free, strongly-linearizable implementation of a bag that can contain at most $b$ elements. It is shared by $n$ processes, $P_1,\mathrm{\dots },P_n$, called consumers, that can perform Take() and a single process, called the producer, that can perform Insert($x$). It extends our lock-free, strongly-linearizable implementation of a 1-bounded bag in Section 6. In this algorithm, Allocated is a shared register that stores a subset of at most $b$ locations, and alloc is a local variable the producer uses to update the contents of Allocated. The challenge in designing a strongly-linearizable bag algorithm from interfering objects was for an operation that is trying to take an element from the bag to detect when the bag is empty (and then return EMPTY). This is addressed using an ABA-detecting register, InsertDone, to which each Insert($x$) operation writes after writing $x$ to Items. When designing a strongly-linearizable bounded bag algorithm from interfering objects, an operation that is trying to insert an element into the bag faces a symmetrical challenge, as it needs to detect when the bag is full (and then return FULL). To address this, we use another ABA-detecting register, TakeDone, to which each Take() operation writes after performing a successful t&s(). Unsuccessful Take operations also write to TakeDone before returning, to help them be linearized before the unsuccessful Take.

The producer begins an Insert($x$) operation by reading TakeDone. Then it looks at each of the locations in TS that have been allocated. For each location $m$ that contains 1, it clears the element in that location (setting Items[m] to $\perp$), removes m from alloc, and adds m to used. If alloc contains less than $b$ locations, it adds $x$ to the bag as follows. It first collects the non-$\perp$ values from the Hazards array into the set hazardous. Afterwards, it allocates an arbitrary location, m, from $\{1,\mathrm{\dots },n+b\}$, excluding those in alloc and in hazardous, adds this location to alloc, and announces it by copying alloc into Allocated. Next, for each location in used that is not in hazardous, it resets the associated test&set object and removes the location from used. Then it writes $x$ to the allocated object, Items[m]. Finally, it writes to the ABA-detecting register InsertDone and returns OK. If alloc contained $b$ locations, it rereads TakeDone and, if its value has not changed since its previous read, it returns FULL; otherwise, it repeats the entire sequence of steps.

To perform a Take() operation, a process reads InsertDone and Allocated. For each location $a$ in the set of locations obtained from Allocated, it announces $a$ in Hazards and then reads the element, x from Items[a]. If $x\ne \perp$, it performs t&s() on the associated test&set object, TS[a], and, if successful, it clears its announcement, writes to TakeDone, and returns $x$. If the process completes the for loop, it clears its announcement, and rereads InsertDone. If the value of InsertDone has not changed since its previous read, it writes to TakeDone and returns EMPTY. Otherwise, it repeats the entire sequence of steps. Pseudocode for our implementation appears in Figure 4.

This paper explores strongly-linearizable implementations of bags from interfering objects. We presented the first lock-free, strongly-linearizable implementation of a bag from interfering objects, which is, interestingly, also a linearizable implementation of a queue, but not a strongly-linearizable implementation. We also presented several implementations of bounded bags with a single producer from interfering objects: a wait-free, linearizable implementation of a 1-bounded bag, a lock-free, strongly-linearizable implementation of a 1-bounded bag, and a lock-free, strongly-linearizable implementation of a $b$-bounded bag for any value of $b$.

A direct extension of this work is investigating whether it is possible to extend our bounded bag implementations to support two producers or multiple producers but only one or two consumers. Other open questions are whether there are wait-free, strongly-linearizable implementations of ABA-detecting registers and bags from interfering objects. It would also be interesting to construct a lock-free, strongly-linearizable implementation of a bag from interfering objects, such that, at every point in the execution, the number of interfering objects used is bounded above by a function of the number of processes and the number of elements the bag contains. More broadly, exploring strongly-linearizable implementations of objects beyond bags using interfering objects is a compelling direction for future work.