Augmentation makes search trees tremendously more versatile, allowing them to support efficient aggregation queries, order-statistic queries, and range queries in addition to insertion, deletion, and lookup. In this paper, we present the first lock-free augmented balanced search tree supporting generic augmentation functions. Our algorithmic ideas build upon a recent augmented unbalanced search tree presented by Fatourou and Ruppert [DISC, 2024]. We implement both data structures, solving some memory reclamation challenges in the process, and provide an experimental performance analysis of them. We also present optimized versions of our balanced tree that use delegation to achieve better scalability and performance (by more than 2x in most workloads). Our experiments show that our augmented balanced tree completes updates 2.2 to 30 times faster than the unbalanced augmented tree, and outperforms unaugmented trees by up to several orders of magnitude on 120 threads.

Many concurrent algorithms require processes to perform fetch-and-add operations on a single memory location, which can be a hot spot of contention. We present a novel algorithm called Aggregating Funnels that reduces this contention by spreading the fetch-and-add operations across multiple memory locations. It aggregates fetch-and-add operations into batches so that the batch can be performed by a single hardware fetch-and-add instruction on one location and all operations in the batch can efficiently compute their results by performing a fetch-and-add instruction on a different location. We show experimentally that this approach achieves higher throughput than previous combining techniques, such as Combining Funnels, and is substantially more scalable than applying hardware fetch-and-add instructions on a single memory location. We show that replacing the fetch-and-add instructions in the fastest state-of-the-art concurrent queue by our Aggregating Funnels eliminates a bottleneck and greatly improves the queue's overall throughput.

This work provides the first concurrent implementation of a double-ended priority queue (DEPQ). We describe a general way to add an ExtractMax operation to any concurrent priority queue that already supports Insert and ExtractMin.

Augmenting an existing sequential data structure with extra information to support greater functionality is a widely used technique. For example, search trees are augmented to build sequential data structures like order-statistic trees, interval trees, tango trees, link/cut trees and many others. We study how to design concurrent augmented tree data structures. We present a new, general technique that can augment a lock-free tree to add any new fields to each tree node, provided the new fields' values can be computed from information in the node and its children. This enables the design of lock-free, linearizable analogues of a wide variety of classical augmented data structures. As a first example, we give a wait-free trie that stores a set S of elements drawn from {0,…,N-1} and supports linearizable order-statistic queries such as finding the kth smallest element of S. Updates and queries take O(log N) steps. We also apply our technique to a lock-free binary search tree (BST), where changes to the structure of the tree make the linearization argument more challenging. Our augmented BST supports order statistic queries in O(h) steps on a tree of height h. The augmentation does not affect the asymptotic step complexity of the updates. As an added bonus, our technique supports arbitrary multi-point queries (such as range queries) with the same step complexity as they would have in the corresponding sequential data structure. For both our trie and BST, we give an alternative augmentation to improve searches and order-statistic queries to run in O(log |S|) steps (at the cost of increasing step complexity of updates by a factor of O(log|S|)).

We present a novel linearizable wait-free queue implementation using single-word CAS instructions. Previous lock-free queue implementations from CAS all have amortized step complexity of Ω(p) per operation in worst-case executions, where p is the number of processes that access the queue. Our new wait-free queue takes O(log p) steps per enqueue and O(log2 p + log q) steps per dequeue, where q is the size of the queue. A bounded-space version of the implementation has O(log p log(p + q)) amortized step complexity per operation.

Multiversioning is widely used in databases, transactional memory, and concurrent data structures. It can be used to support read-only transactions that appear atomic in the presence of concurrent update operations. Any system that maintains multiple versions of each object needs a way of efficiently reclaiming them. We experimentally compare various existing reclamation techniques by applying them to a multiversion tree and a multiversion hash table.

We study the ability of different shared object types to solve recoverable consensus using non-volatile shared memory in a system with crashes and recoveries. In particular, we compare the difficulty of solving recoverable consensus to the difficulty of solving the standard wait-free consensus problem in a system with halting failures. We focus on the model where individual processes may crash and recover and on the large class of object types that are equipped with a read operation. We characterize the readable object types that can solve recoverable consensus among a given number of processes. Using this characterization, we show that the number of processes that can solve consensus using a readable type can be larger than the number of processes that can solve recoverable consensus using that type, but only slightly larger.

Given a concurrent data structure, we present an approach for efficiently taking snapshots of its constituent CAS objects. More specifically, we support a constant-time operation that returns a snapshot handle. This snapshot handle can later be used to read the value of any base object at the time the snapshot was taken. Reading an earlier version of a base object is wait-free and takes time proportional to the number of successful writes to the object since the snapshot was taken. Importantly, our approach preserves all the time bounds and parallelism of the original data structure.

We present a general technique for garbage collecting old versions for multiversion concurrency control that simultaneously achieves good time and space complexity. Our technique takes only $O(1)$ time on average to reclaim each version and maintains only a constant factor more versions than needed (plus an additive term). It is designed for multiversion schemes using version lists, which are the most common. Our approach uses two components that are of independent interest. First, we define a novel range-tracking data structure which stores a set of old versions and efficiently finds those that are no longer needed. We provide a wait-free implementation in which all operations take amortized constant time. Second, we represent version lists using a new lock-free doubly-linked list algorithm that supports efficient (amortized constant time) removals given a pointer to any node in the list. These two components naturally fit together to solve the multiversion garbage collection problem--the range-tracker identifies which versions to remove and our list algorithm can then be used to remove them from their version lists. We apply our garbage collection technique to generate end-to-end time and space bounds for the multiversioning system of Wei et al. (PPoPP 2021).

This paper presents the first implementation of a search tree data structure in an asynchronous shared-memory system that provides a wait-free algorithm for executing range queries on the tree, in addition to non-blocking algorithms for Insert, Delete and Find, using single-word Compare-and-Swap (CAS). The implementation is linearizable and tolerates any number of crash failures. Insert and Delete operations that operate on different parts of the tree run fully in parallel (without any interference with one another). We employ a lightweight helping mechanism, where each Insert, Delete and Find operation helps only update operations that affect the local neighbourhood of the leaf that the Find arrives at. Similarly, a range query helps only those updates taking place on nodes in the part of the tree it traverses. Our implementation works in a dynamic system where the number of processes may change over time. The implementation builds upon the non-blocking binary search tree of Ellen et al. [PODC 2010] by making the tree persistent. Experimental results show that the persistent tree compares well with other tree data structures that provide range queries. The experimental evaluation also shows that the persistent tree scales well and that the additional cost of persistence is modest, as is the additional cost for achieving wait-free range queries.

Implementing stronger read/write registers from weaker ones is a classical problem in the theory of distributed computing. In some such implementations, implemented read operations have the desirable property of not having to write to the base registers used in the implementation. In other cases, it has been proved that implementations cannot have this property. Here, we describe a novel result of the latter type. Although a lock-free implementation of an unbounded register can be built where reads do not write, we show that in any wait-free implementation of unbounded registers from bounded registers, the implemented read operations must write to shared memory.

The k-set agreement problem is a generalization of the classical consensus problem in which processes are permitted to output up to k different input values. In a system of n processes, an m-obstruction-free solution to the problem requires termination only in executions where the number of processes taking steps is eventually bounded by m. This family of progress conditions generalizes wait-freedom (m = n) and obstruction-freedom (m = 1). In this paper, we prove upper and lower bounds on the number of registers required to solve m-obstruction-free k-set agreement, considering both one-shot and repeated formulations. In particular, we show that repeated k set agreement can be solved using n + 2 m--k registers and establish a nearly matching lower bound of n + 2 m--k.

We improve upon an existing non-blocking implementation of a binary search tree from single-word compare-and-swap instructions. We show that the worst-case amortized step complexity of performing a Find, Insert or Delete operation op on the tree is O(h(op)+c(op)) where h(op) is the height of the tree at the beginning of op and c(op) is the maximum number of operations accessing the tree at any one time during op. This is the first bound on the complexity of a non-blocking implementation of a search tree.

This paper compares, for the first time, the computational power of linearizable objects with that of eventually linearizable ones. We present the following paradox. We show that, unsurprisingly, no set of eventually linearizable objects can (1) implement any non-trivial linearizable object, nor (2) boost the consensus power of simple objects like linearizable registers. We also show, perhaps surprisingly, that any implementation of an eventually linearizable complex object like a fetch&increment counter (from linearizable base objects), can itself be viewed as a fully linearizable implementation of the same fetch&increment counter (using the exact same set of base objects).

We describe a general technique for obtaining provably correct, non-blocking implementations of a large class of tree data structures where pointers are directed from parents to children. Updates are permitted to modify any contiguous portion of the tree atomically. Our non-blocking algorithms make use of the LLX, SCX and VLX primitives, which are multi-word generalizations of the standard LL, SC and VL primitives and have been implemented from single-word CAS. To illustrate our technique, we describe how it can be used in a fairly straightforward way to obtain a non-blocking implementation of a chromatic tree, which is a relaxed variant of a red-black tree. The height of the tree at any time is O(c + log n), where n is the number of keys and c is the number of updates in progress. We provide an experimental performance analysis which demonstrates that our Java implementation of a chromatic tree rivals, and often significantly outperforms, other leading concurrent dictionaries.

We define a new set of primitive operations that greatly simplify the implementation of non-blocking data structures in asynchronous shared-memory systems. The new operations operate on a set of Data-records, each of which contains multiple fields. The operations are generalizations of the well-known load-link (LL) and store-conditional (SC) operations called LLX and SCX. The LLX operation takes a snapshot of one Data-record. An SCX operation by a process p succeeds only if no Data-record in a specified set has been changed since p last performed an LLX on it. If successful, the SCX atomically updates one specific field of a Data-record in the set and prevents any future changes to some specified subset of those Data-records. We provide a provably correct implementation of these new primitives from single-word compare-and-swap. As a simple example, we show how to implement a non-blocking multiset data structure in a straightforward way using LLX and SCX.

International audience

This paper describes the first complete implementation of a non-blocking binary search tree in an asynchronous shared-memory system using single-word compare-and-swap operations. The implementation is linearizable and tolerates any number of crash failures. Insert and Delete operations that modify different parts of the tree do not interfere with one another, so they can run completely concurrently. Find operations only perform reads of shared memory.

We introduce a generalization of the atomic snapshot object, which we call the partial snapshot object. This object stores a vector of values. Processes may write components of the vector individually or atomically scan any subset of the components. We investigate implementations of the latter partial scan operation that are more efficient than the complete scans of traditional snapshot objects. We present an algorithm that is based on a new implementation of the active set abstraction, which may be of independent interest.

A snapshot object is an abstraction of the problem of obtaining a consistent view of the contents of shared memory in a distributed system, despite concurrent changes to the memory. There are implementations of m -component snapshot objects shared by n ≥ m processes using m registers. This is the minimum number of registers possible. We prove a time lower bound for implementations that use this minimum number of registers. It matches the time taken by the fastest such implementation. Our proof yields insight into the structure of any such implementation, showing that processes must access the registers in a very constrained way. We also prove a time lower bound for snapshot implementations using single-writer registers in addition to m historyless objects (such as registers and swap objects).

A snapshot object is an abstraction of the fundamental problem of obtaining a consistent view of the contents of the shared memory in a distributed system while other processes may concurrently update those contents. A snapshot object stores an array of m components and can be accessed by two operations: an UPDATE that changes the value of an individual component and a powerful SCAN that returns the contents of the entire array.This paper proves time-space tradeoffs for fault-tolerant implementations of a snapshot object from registers that support only Read and Write operations. For anonymous implementations (where all processes are programmed identically), we prove that a SCAN requires Ω(n/r) time, where n is the number of processes in the system and r is the number of registers used by the implementation. For the general non-anonymous case, we prove that, for any fixed r, the time required to do a SCAN grows without bound as n increases. These tradeoffs hold even in the case where the snapshot object has just two components.This is the first time a lower bound on the tradeoff between time complexity and the number of registers has been proved for any problem in asynchronous shared-memory systems. We introduce a new tool for proving distributed lower bounds: the notion of a shrinkable execution, from which an adversary can remove portions as necessary.

Lock-free shared data structures implement distributed objects without the use of mutual exclusion, thus providing robustness and reliability. We present a new lock-free implementation of singly-linked lists. We prove that the worst-case amortized cost of the operations on our linked lists is linear in the length of the list plus the contention, which is better than in previous lock-free implementations of this data structure. Our implementation uses backlinks that are set when a node is deleted so that concurrent operations visiting the deleted node can recover. To avoid performance problems that would arise from traversing long chains of backlink pointers, we introduce flag bits, which indicate that a deletion of the next node is underway. We then give a lock-free implementation of a skip list dictionary data structure that uses the new linked list algorithms to implement individual levels. Our algorithms use the single-word C&S synchronization primitive.

A snapshot object consists of a collection of m > 1 components, each capable of storing a value, shared by n processes in an asynchronous shared-memory distributed system. It supports two operations: a process can UPDATE any individual component or atomically SCAN the entire collection to obtain the values of all the components. It is possible to implement a snapshot object using m registers so that each operation takes O(mn) time.

We consider the problem of wait-free implementation of a multi-writer snapshot object with m ≥ 2 components shared by n > m processes. It is known that this can be done using m multi-writer registers. We give a matching lower bound, slightly improving the previous space lower bound. The main focus of the paper, however, is on time complexity. The best known upper bound on the number of steps a process has to take to perform one operation of the snapshot is O(n). When m is much smaller than n, an implementation whose time complexity is a function of m rather than n would be better. We show that this cannot be achieved for any space-optimal implementation: We prove that Ω(n) steps are required to perform a SCAN operation in the worst case, even if m = 2. This significantly improves previous Ω(min(m, n)) lower bounds. Our proof also yields insight into the structure of any space-optimal implementation, showing that processes simulating the snapshot operations must access the registers in a very constrained way.

A data type's consensus number measures its power in asynchronous concurrent models of computation. We characterize the circumstances under which types of high consensus number can be constructed from types with lower consensus numbers, a process called boosting. In settings where boosting is impossible, we can reason about the synchronization power of objects in isolation. We give a new and simple topological condition, called /spl kappa/-solo-connectivity sufficient to ensure that one-shot types cannot be boosted to consensus number /spl kappa/. The booster type need not be one-shot; it can be arbitrary. We also show that, for /spl kappa/>2, any type that is not /spl kappa/-solo-connected can be boosted to consensus number /spl kappa/. For types that can be boosted, we establish an upper bound on the amount the consensus number can be increased. For finite types, these properties and bounds are computable. For deterministic one-shot types, the /spl kappa/-solo-connectivity property also exactly characterizes the types that have consensus number less than /spl kappa/.

Conditions on a shared object type T are given that are both necessary and sufficient for wait-free n-process consensus to be solvable using objects of type T and registers. The conditions apply to two large classes of deterministic shared objects: read-modify-write objects [C. P. Kruskal, L. Rudolph, and M. Snir, { ACM Trans. Prog. Lang. Syst., 10 (1988), pp. 579--601] and readable objects, which have operations that allow processes to read the state of the object. These classes include most objects that are used as the primitives of distributed systems. When the sequential specification of T is finite, the conditions may be checked in a finite amount of time to decide the question "Is the consensus number of T at least n?" The conditions are also used to provide a clear proof of the robustness of the consensus hierarchy for read-modify-write and readable objects.

This paper studies the ability of shared memory distributed systems to solve the wait-free consensus problem if processes are permitted to access more than one shared data object in a single atomic action. Suppose T is any deterministic object type that can be used, with read/write registers, to solve consensus among n processes, with n ? 2. A multiobject of type T m consists of a collection of objects of type T , any m of which can be accessed in a single atomic action. It will be shown that a multi-object of type T m can be used, with registers, to solve consensus among\\Omega\\Gamma n p m) processes. Furthermore, if the type T is equipped with operations that allow processes to read its state without altering the state, then the multi-object can be used with registers to solve consensus among \\Omega\\Gamma nm) processes. Neither of these lower bounds can be improved. 1 Introduction In a shared memory distributed system, processes communicate by accessing shared data objects...

Article Determining consensus numbers Share on Author: Eric Ruppert Department of Computer Science, University of Toronto, Toronto, Ontario, Canada, M5S 3G4 Department of Computer Science, University of Toronto, Toronto, Ontario, Canada, M5S 3G4View Profile Authors Info & Claims PODC '97: Proceedings of the sixteenth annual ACM symposium on Principles of distributed computingAugust 1997 Pages 93–99https://doi.org/10.1145/259380.259427Online:01 August 1997Publication History 10citation267DownloadsMetricsTotal Citations10Total Downloads267Last 12 Months6Last 6 weeks3 Get Citation AlertsNew Citation Alert added!This alert has been successfully added and will be sent to:You will be notified whenever a record that you have chosen has been cited.To manage your alert preferences, click on the button below.Manage my AlertsNew Citation Alert!Please log in to your account Save to BinderSave to BinderCreate a New BinderNameCancelCreateExport CitationPublisher SiteGet Access