Fast Arrays support initialization of the entire array in just constant time, in addition to supporting constant-time reading and writing of individual elements. Jayanti and Shun introduced concurrent fast arrays, including a generalized fast array which supports constant-time read-modify-write (RMW) operations in addition to reads and writes. Their generalized algorithm, however, assumes mixed-size atomicity—i.e., that 128-bit compare-and-swap and 64-bit read-modify-write operations can be performed concurrently on the same location—which is not available in most programming languages (e.g., C++ and Rust) and not guaranteed on most architectures (e.g., x86 and ARM), as opposed to fixed-size atomicity.

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.

Modern servers are equipped with many tiers of random access memory (RAM), where faster tiers offer greater speed of memory accesses while slower tiers offer greater capacity. In this paper, we model such tiered memory systems and ask the fundamental question of how to simultaneously exploit the computation speed of the fast tiers and the capacity of the slow tiers.

Interplanetary distributed systems, such as the Interplanetary Internet, and the Global Positioning System (GPS) are subject to the effects of Einstein's theory of relativity. In this paper, we study relativistic distributed systems, which are subject to the relativity of simultaneity. We formulate a unified computational model for relativistic and classical distributed systems and study the relationship between properties of distributed algorithms deployed on the two types of systems. Classical executions are totally ordered in time, whereas the steps of a relativistic execution are only partially ordered by the relation of relativistic causality. We relate these two physics-dependent execution types through a third—purely mathematical—notion of a computational execution, which partially orders steps by the relation of computational causality. We relate relativistic, classical, and computational executions of distributed algorithms through a central theorem, which states that the following are equivalent for any distributed algorithm A: (1) A satisfies a property P classically; (2) every relativistic execution of A satisfies P in the reference frame of every observer; and (3) every total ordering of every computational execution of A satisfies P. As a direct consequence, we prove the equivalence of the standard, relativistic, and computational formulations of linearizability. Our results show that a host of algorithms originally designed for classical distributed systems will behave consistently when deployed in relativistic, interplanetary distributed systems.

We design an algorithm that allows processes to click snapshots of the application's state, and store these snapshots in a shared archive for later retrieval. Such an archive of snapshots is useful for debugging complex multi-process applications.

In this work, we present theoretically and practically efficient implementations of Big Atomics, i.e., k-word linearizable registers that support the load, store, and compare-and-swap (CAS) operations. While modern hardware supports k = 1 and sometimes k = 2 (e.g., double-width compare-and-swap in x86), our implementations support arbitrary k. Big Atomics are useful in many applications, including atomic manipulation of tuples, version lists, and implementing load-linked/store-conditional (LL/SC). We design fast, lock-free implementations of big atomics based on a novel fast-path-slow-path approach we develop. We then use them to develop an efficient concurrent hash table, as evidence of their utility.

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.

We define and solve the differential snapshot problem. A differential snapshot object maintains a dynamic set of components and supports two operations: an Update operation by which any process can read or modify a given component, and a ScanDiff operation by which a designated scanner process can snapshot the differential, i.e., the components that changed since the last snapshot. We design a linearizable and wait-free differential snapshot algorithm that allows updates via arbitrary read-modify-write (RMW) operations supported by hardware. We implement Update in O(1) steps and ScanDiff in O(Δ + p) steps, where Δ is the number of components that have been updated since the last ScanDiff operation and p is the number of processes that access the object.

In this work, we consider the MemSnap algorithm [Jayanti et al., PODC 2024]---an efficient, yet extremely intricate solution to the adaptive snapshot problem---and give a formally machine-verified proof of its correctness, i.e., linearizability. An adaptive snapshot object maintains m components and supports operations to read, write, and update individual components (via arbitrary hardware read-modify-write operations), a click operation to take a fast (implicit) snapshot of all of the components, and an operation to observe the value of any component in the latest snapshot. Expressed in just 12 total lines of pseudocode, MemSnap is succinct. Simultaneously, it achieves optimal time and space complexity, implementing each operation in just O(1) steps and requiring only O(m) space to store the entire data structure consisting of m components. Nevertheless, the algorithm is extremely intricate and challenging to prove correct, especially since it is far-future linearizable, meaning that the precise linearization point of an operation may be indeterminate even after the operation returns a response. In our work, we formalize the enhanced version of MemSnap, which enables a very useful parallel primitive, called parallel observation. In particular, if the scanner has access to parallelism, it can scan a complete snapshot of the m components in O(m) work with an O(1) span using MemSnap. We formalize MemSnap in TLA+ (based on Lamport's temporal logic of actions) and develop a complete machine-verified proof of its linearizability. Our proof, consisting of 14,000 lines of TLA+ code, is verified by TLAPS (the TLA+ Proof System), and is the first machine-verified proof of this elegant and complex algorithm.

Shared-memory words in modern multiprocessors support read-modify-write (RMW) primitives, such as compare-and-swap, fetch-and-add, and fetch-and-store, in addition to standard reads and writes. Thus, checkpointing the shared-memory of a modern multicore requires a variant of the snapshot object, which needs to support only a single scanner, but which allows components to be updated via all the RMW operations supported by hardware.

We introduce simple, universal , sound , and complete proof methods for producing machine-verifiable proofs of linearizability and strong linearizability. Universality means that our method works for any object type; soundness means that an algorithm can be proved correct by our method only if it is linearizable (resp. strong linearizable); and completeness means that any linearizable (resp. strong linearizable) implementation can be proved so using our method. We demonstrate the simplicity and power of our method by producing proofs of linearizability for the Herlihy-Wing queue and Jayanti's single-scanner snapshot, as well as a proof of strong linearizability of the Jayanti-Tarjan union-find object. All three of these proofs are machine-verified by TLAPS (the TLA+ Proof System).

We present DuraCAS, a durable, i.e., recoverably linearizable and detectable implementation of the CAS (compare-and-swap) primitive. DuraCAS is writable, meaning it supports a Write() operation along with CAS() and Read(); has constant time complexity per operation; allows for dynamic joining, meaning newly created processes (a.k.a. threads) of arbitrary names can join the protocol and access our implementation; and has adaptive space complexity, meaning the space use scales in the number of processes n that actually use the objects, as opposed to previous protocols whose space complexity depends on N, the maximum number of processes that the protocol is designed for. Furthermore, DuraCAS, requires only O(m + n) space to support m objects that get accessed by n processes, improving on the state-of-the-art O(m + N2). To our knowledge, DuraCAS is the first durable CAS algorithm that allows for dynamic joining, and is the first to exhibit adaptive space complexity.

We design two Recoverable Mutual Exclusion (RME) locks (a.k.a. durable locks) for the system-wide crash model. Our first algorithm requires only O(1) space per process, and achieves O(1) worst-case Remote Memory Reference (RMR) complexity in the Cache-Coherent (CC) model. Our second algorithm enhances the first algorithm to achieve (the same) O(1) space per process and O(1) worst-case RMR complexity in both the CC and Distributed Shared Memory (DSM) models. Furthermore, both algorithms allow dynamically created threads of arbitrary names to join the protocol and access the locks. To our knowledge, these are the only RME locks to achieve worst-case O(1) RMR complexity assuming nothing more than standard hardware support. In light of Chan and Woelfel's Ω(log n / log log n) worst-case RMR lower bound for RME in the individual crash model, our results show a separation between the system-wide crash and individual crash models in worst-case RMR complexity in both the CC and DSM models.

We present durable implementations for two well known universal primitives -- CAS (compare-and-swap), and its ABA-free counter-part LLSC (load-linked, store-conditional). All our implementations are: writable, meaning they support a Write() operation; have constant time complexity per operation; allow for dynamic joining, meaning newly created processes (a.k.a. threads) of arbitrary names can join a protocol and access our implementations; and have adaptive space complexities, meaning the space use scales in the number of processes $n$ that actually use the objects, as opposed to previous protocols which are designed for a maximum number of processes $N$. Our durable Writable-CAS implementation, DuraCAS, requires $O(m + n)$ space to support $m$ objects that get accessed by $n$ processes, improving on the state-of-the-art $O(m + N^2)$. By definition, LLSC objects must store "contexts" in addition to object values. Our Writable-LLSC implementation, DuraLL, requires $O(m + n + C)$ space, where $C$ is the number of "contexts" stored across all the objects. While LLSC has an advantage over CAS due to being ABA-free, the object definition seems to require additional space usage. To address this trade-off, we define an External Context (EC) variant of LLSC. Our EC Writable-LLSC implementation is ABA-free and has a space complexity of just $O(m + n)$. To our knowledge, we are the first to present durable CAS algorithms that allow for dynamic joining, and our algorithms are the first to exhibit adaptive space complexities. To our knowledge, we are the first to implement any type of durable LLSC objects.

In the fillable array problem one must maintain an array A[1..n] of $w$-bit entries subject to random access reads and writes, and also a $\texttt{fill}(Δ)$ operation which sets every entry of to some $Δ\in\{0,\ldots,2^w-1\}$. We show that with just one bit of redundancy, i.e. a data structure using $nw+1$ bits of memory, $\texttt{read}/\texttt{fill}$ can be implemented in worst case constant time, and $\texttt{write}$ can be implemented in either amortized constant time (deterministically) or worst case expected constant (randomized). In the latter case, we need to store an additional $O(\log n)$ random bits to specify a permutation drawn from an $1/n^2$-almost pairwise independent family.

Abstract We develop and analyze concurrent algorithms for the disjoint set union (“union-find” ) problem in the shared memory, asynchronous multiprocessor model of computation, with CAS (compare and swap) or DCAS (double compare and swap) as the synchronization primitive. We give a deterministic bounded wait-free algorithm that uses DCAS and has a total work bound of $$O\biggl ( m \cdot \left( \log {\left( \frac{np}{m} + 1 \right) } + \alpha {\left( n, \frac{m}{np} \right) } \right) \biggr )$$ O ( m · log np m + 1 + α n , m np ) for a problem with n elements and m operations solved by p processes, where $$\alpha $$ α is a functional inverse of Ackermann’s function. We give two randomized algorithms that use only CAS and have the same work bound in expectation. The analysis of the second randomized algorithm is valid even if the scheduler is adversarial. Our DCAS and randomized algorithms take $$O(\log n)$$ O ( log n ) steps per operation, worst-case for the DCAS algorithm, high-probability for the randomized algorithms. Our work and step bounds grow only logarithmically with p, making our algorithms truly scalable. We prove that for a class of symmetric algorithms that includes ours, no better step or work bound is possible. Our work is theoretical, but Alistarh et al (In search of the fastest concurrent union-find algorithm, 2019), Dhulipala et al (A framework for static and incremental parallel graph connectivity algorithms, 2020) and Hong et al (Exploring the design space of static and incremental graph connectivity algorithms on gpus, 2020) have implemented some of our algorithms on CPUs and GPUs and experimented with them. On many realistic data sets, our algorithms run as fast or faster than all others.

We initiate the study of the natural multiplayer generalization of the classic continuous Colonel Blotto game. The two-player Blotto game, introduced by Borel (1953) as a model of resource competition across n simultaneous fronts, has been studied extensively for a century and has seen numerous applications throughout the social sciences. Our work defines the multiplayer Colonel Blotto game and derives Nash equilibria for various settings of k (number of players) and n. We also introduce a “Boolean” version of Blotto that becomes interesting in the multiplayer setting. The main technical difficulty of our work, as in the two-player theoretical literature, is the challenge of coupling various marginal distributions into a joint distribution satisfying a strict sum constraint. In contrast to previous works in the continuous setting, we derive our couplings algorithmically in the form of efficient sampling algorithms.

Statistical learning theory has largely focused on learning and generalization given independent and identically distributed (i.i.d.) samples. Motivated by applications involving time-series data, there has been a growing literature on learning and generalization in settings where data is sampled from an ergodic process. This work has also developed complexity measures, which appropriately extend the notion of Rademacher complexity to bound the generalization error and learning rates of hypothesis classes in this setting. Rather than time-series data, our work is motivated by settings where data is sampled on a network or a spatial domain, and thus do not fit well within the framework of prior work. We provide learning and generalization bounds for data that are complexly dependent, yet their distribution satisfies the standard Dobrushin’s condition. Indeed, we show that the standard complexity measures of Gaussian and Rademacher complexities and VC dimension are sufficient measures of complexity for the purposes of bounding the generalization error and learning rates of hypothesis classes in our setting. Moreover, our generalization bounds only degrade by constant factors compared to their i.i.d. analogs, and our learnability bounds degrade by log factors in the size of the training set.

The Abortable mutual exclusion problem, proposed by Scott and Scherer in response to the needs in real time systems and databases, is a variant of mutual exclusion that allows processes to abort from their attempt to acquire the lock. Worst-case constant remote memory reference (RMR) algorithms for mutual exclusion using hardware instructions such as Fetch&Add or Fetch&Store have long existed for both Cache Coherent (CC) and Distributed Shared Memory (DSM) multiprocessors, but no such algorithms are known for abortable mutual exclusion. Even relaxing the worst-case requirement to amortized, algorithms are only known for the CC model.

In light of recent advances in non-volatile main memory technology, Golab and Ramaraju reformulated the traditional mutex problem into the novel Recoverable Mutual Exclusion (RME) problem. In the best known solution for RME, due to Golab and Hendler from PODC 2017, a process incurs at most O(√ log n log log n) remote memory references (RMRs) per passage on a system with n processes, where a passage is an interval from when a process enters the Try section to when it subsequently returns to Remainder. Their algorithm, however, guarantees this bound only for cache-coherent (CC) multiprocessors, leaving open the question of whether a similar bound is possible for distributed shared memory (DSM) multiprocessors.

We consider the disjoint set union problem in the asynchronous shared memory multiprocessor computation model. We design a randomized algorithm that performs at most O(log n) work per operation (with high probability), and performs at most O(m #8226; (α(n, m/(np)) + log(np/m + 1)) total work in expectation for a problem instance with m operations on n elements solved by p processes. Our algorithm is the first to have work bounds that grow sublinearly with p against an adversarial scheduler.

Asynchronous Gibbs sampling has been recently shown to be fast-mixing and an accurate method for estimating probabilities of events on a small number of variables of a graphical model satisfying Dobrushin's condition~\cite{DeSaOR16}. We investigate whether it can be used to accurately estimate expectations of functions of {\em all the variables} of the model. Under the same condition, we show that the synchronous (sequential) and asynchronous Gibbs samplers can be coupled so that the expected Hamming distance between their (multivariate) samples remains bounded by $O(\tau \log n),$ where $n$ is the number of variables in the graphical model, and $\tau$ is a measure of the asynchronicity. A similar bound holds for any constant power of the Hamming distance. Hence, the expectation of any function that is Lipschitz with respect to a power of the Hamming distance, can be estimated with a bias that grows logarithmically in $n$. Going beyond Lipschitz functions, we consider the bias arising from asynchronicity in estimating the expectation of polynomial functions of all variables in the model. Using recent concentration of measure results~\cite{DaskalakisDK17,GheissariLP17,GotzeSS18}, we show that the bias introduced by the asynchronicity is of smaller order than the standard deviation of the function value already present in the true model. We perform experiments on a multi-processor machine to empirically illustrate our theoretical findings.

Disjoint set union is a basic problem in data structures with a wide variety of applications. We extend a known efficient sequential algorithm for this problem to obtain a simple and efficient concurrent wait-free algorithm running on an asynchronous parallel random access machine (APRAM). Crucial to our result is the use of randomization. Under a certain independence assumption, for a problem instance in which there are n elements, m operations, and l processes, our algorithm does θ(m (α{n, m/nl) + log (nl/m + 1 ))) expected work, where the expectation is over the random choices made by the algorithm and α is a functional inverse of Ackermann's function. In addition, each operation takes O(log n) steps with high probability.