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.

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.

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.

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.

The winner of the 2019 Principles of Distributed Computing Doctoral Dissertation Award is Dr. Sepehr Assadi for his dissertation Combinatorial Optimization on Massive Datasets: Streaming, Distributed, and Massively Parallel Computation, written under the supervision of Prof. Sanjeev Khanna at the University of Pennsylvania.

Traditional mutual exclusion locks are not resilient to failures: if there is a power outage, the memory is wiped out. Thus, when the system comes back on, the lock will have to be restored to the initial state, i.e., all processes are rolled back to the Remainder section and all variables are reset to their initial values. Recently, Golab and Ramaraju showed that we can improve this state of the art by exploiting the Non-Volatile RAM (NVRAM). They designed algorithms that, by maintaining shared variables in NVRAM, allow processes to recover from crashes on their own without a need for a global reset, even though a crash can wipe out the local memory of a process. We present a Recoverable Mutual Exclusion algorithm using the commonly supported CAS primitive. The main features of our algorithm are that it satisfies FCFS, it ensures that each process recovers in a wait-free manner, and in the absence of failures, it guarantees a worst-case Remote Memory Reference (RMR) complexity of O(lg n) on both Cache Coherent (CC) and Distributed Shared Memory (DSM) machines, where n is the number of processes for which the algorithm is designed. This bound matches the Omega(lg n) RMR lower bound by Attiya, Hendler, and Woelfel for Mutual Exclusion algorithms that use comparison primitives.

Mutual Exclusion is a fundamental problem in distributed computing, and the problem of proving upper and lower bounds on the RMR complexity of this problem has been extensively studied. Here, we give matching lower and upper bounds on how RMR complexity trades off with space. Two implications of our results are that constant RMR complexity is impossible with subpolynomial space and subpolynomial RMR complexity is impossible with constant space for cache-coherent multiprocessors, regardless of how strong the hardware synchronization operations are.

We study Reader-Writer Exclusion [1], a well-known variant of the Mutual Exclusion problem [2] where processes are divided into two classes - readers and writers - and multiple readers can be in the Critical Section (CS) at the same time, although no process may be in the CS at the same time as a writer. Since readers don't conflict with each other, they should not obstruct each other. Specifically, the concurrent entering property must be satisfied: if all writers are in the Remainder section, each reader should be able to enter the CS in a bounded number of its own steps. Three versions of the Reader-Writer Exclusion problem are commonly studied - one where writers have priority over readers, another where readers have priority, and the last where neither class has priority over the other and no process may starve.

It is well known that the failure detector Ω is necessary and sufficient to solve consensus in asynchronous message passing systems where a majority of processes is guaranteed to be correct [1,2]. But what if the problem were to be solved in an arbitrary environment where any number of processes may fail and at any times? The answer was provided by Delporte et al who showed that a certain quorum failure detector, which they called Σ, is necessary and, together with Ω, sufficient to solve consensus in any environment [4].

Several basic problems that arise in fault-tolerant distributed computing were shown to have a weakest failure detector. We show here that every problem that is solvable with a failure detector has a weakest failure detector.

Since the design of lock-free data structures often poses a formidable intellectual challenge, researchers are constantly in search of abstractions and primitives that simplify this design. The multiword LL/SC object is such a primitive: many existing algorithms are based on this primitive, including the nonblocking and wait-free universal constructions [1], the closed objects construction [4] and the snapshot algorithms [12, 13]. In this paper, we consider the problem of implementing a W-word LL/SC object shared by N processes. The previous best algorithm, due to Anderson and Moir [1], is time optimal (LL and SC operations run in O(W) time), but has a space complexity of O(N²W). We present an algorithm that uses novel buffer management ideas to cut down the space complexity by a factor of N to O(NW), while still being time optimal.

An m-component, n-process snapshot object is an abstraction of shared memory that consists of m words and allows up to n processes to concurrently execute the following two types of operations: write(i,v), which writes v into the ith word, and scan(), which returns the current values of all m locations [1, 3]. The snapshot problem is to design algorithms for the write and scan operations that meet two challenging requirements: (1) operations appear to be atomic, and (2) operations are wait-freeFor any (m-component, n-process) snapshot algorithm, which runs on hardware that supports only word-sized objects, Ω(1) and Ω(m) are trivial lower bounds on the time complexity of write(i,v) and scan(), respectively. But, are these bounds tight?For a restricted version of the snapshot problem, known in the literature as the single-writer snapshot problem, Riany, Shavit and Touitou [18] showed that the answer is yes: they designed an algorithm with O(1) and O(m) running times for the write(i,v) and scan() operations, respectively. (The single-writer snapshot problem assumes that (i) the number m of words of the snapshot object is equal to the number n of processes, and (ii) only the ith process may write into the ith snapshot word.This paper shows that the same (optimal) running times of O(1) for write(i,v) and O(m) for scan() are achievable for the general problem, known in the literature as the multiwriter snapshot problem. Our algorithm requires hardware support for the CAS (compare&swap) operation (in comparison, Riany, Shavit and Touitou's algorithm requires hardware support for CAS, fetch&inc, and fetch&dec operations).

We study the consensus problem, which requires multiple processes with different input values to agree on one of these values, in the context of asynchronous shared memory systems. Prior research focussed either on t-resilient solutions of this problem (which must be correct even if up to t processes crash) or on wait-free solutions (which must be correct despite the crash of any number of processes). In this paper, we show that these two forms of solvability are closely related. Specifically, for all $n > t \ge 2$ and all sets ${\mathcal{S}}$ of shared object types (that include simple read/write registers), there is a t-resilient solution to n-process consensus using objects of types in ${\mathcal{S}}$ if and only if there is a wait-free solution to (t + 1)-process consensus using objects of types in ${\mathcal{S}}$. Our proof of this equivalence uses another result derived in this paper, which is of independent interest. Roughly speaking, this result states that a wait-free solution to (n - 1)-process consensus is never necessary in designing a wait-free solution to n-process consensus, regardless of the types of objects available. More precisely, for all $n \ge 2$ and all sets ${\mathcal{S}}$ of shared object types (that include simple read/write registers), if there is a wait-free solution to n-process consensus that uses a wait-free solution to (n - 1)-process consensus and objects of types in ${\mathcal{S}}$, then there is a wait-free solution to n-process consensus that uses only objects of types in ${\mathcal{S}}$.

Scott and Scherer recently pointed out that existing locking algorithms do not meet a need that arises in practical systems. Specifically, database systems and real time systems need mutual exclusion locks that support the abort capability, which makes it possible for a process that waits "too long" to abort its attempt to acquire the lock. Further, to ensure high performance in cache coherent and NUMA multiprocessors, the locking algorithm should generate as few remote references as possible.To help meet this need, Scott and Scherer in 2001 and Scott in 2002 proposed some local-spin abortable mutual exclusion algorithms, but these algorithms have Shortcomings. Specifically, the algorithm by Scott and Scherer allows an aborting process to be blocked by other processes, which is unacceptable. The subsequent algorithms by Scott overcome this shortcoming, but these have unbounded worst-case time and space complexity.In this paper, we present art efficient local-spin algorithm with the following complexity: in each acquisition and release/abort of the lock, a process makes O(min(k, log n)) remote memory references, where k is the point contention and n is the total number of processes for which the lock is designed. Thus, not only is the algorithm adaptive, but also its worst-case time complexity has a small logarithmic bound. The algorithm has O(n) space complexity. To our knowledge, this is the first abortable mutual exclusion algorithm that has bounded time complexity and requires only a bounded number of memory words.

Over the past decade, a pair of synchronization instructions known as LL/SC has emerged as the most suitable set of instructions to be used in the design of lock-free algorithms. However, no existing multiprocessor system supports these instructions in hardware. Instead, most modern multipro-cessors support instructions such as CAS or RLL/RSC (e.g. POWER4, MIPS, SPARC, IA-64). This paper presents two efficient algorithms that implement 64-bit LL/SC from 64-bit CAS or RLL/RSC. Our re~ults are summarized as fol-lows. We present a practical algorithm for implementing a 64-bit LL/SC object from 64-bit CAS or RLL/RSC objects. Our result shows, for the first time, a practical way of simu-lating a 64-bit LL/SC memory word using 64-bit CAS mem-ory words (or 64-bit RLL/RSC memory words), incurring only a small constant space overhead per process and a small constant factor slowdown. Although our first solution performs correctly in any practical system, its theoretical correctness depends on un-bounded sequence numbers. We present a bounded algo-rithm that implements a 64-bit LL/SC object from 64-bit CAS or RLL/RSC objects, and has the same time and space complexities as the first algorithm. This and the previous algorithm improve on existing im-plementations of LL/SC objects by Anderson and Moir in 1995, and Moir in 1997. 1.

In the group mutual exclusion problem [6], which generalizes mutual exclusion [2], a process chooses a session when it requests entry to the Critical Section. A group mutual exclusion algorithm must ensure that the mutual exclusion property holds: If two processes are in the Critical Section at the same time, then they request the same session. In addition to mutual exclusion, lockout freedom, bounded exit and concurrent entering are basic properties that are desirable in any group mutual exclusion algorithm.Hadzilacos in [4] first introduced a fairness condition, called first-come-first-served (FCFS), for group mutual exclusion. The only known FCFS group mutual exclusion algorithm is due to Hadzilacos [4], and requires Θ(N2) bounded shared registers, where N is the number of processes. We present a FCFS group mutual exclusion algorithm that uses only Θ(N) bounded shared registers. (The existence of such an algorithm was posed as an open problem by Hadzilacos.)Next, we demonstrate that the FCFS property does not fully capture our intuitive notion of fairness. We therefore propose an additional fairness property, called first-in-first-enabled (FIFE). Finally, we present a reduction that transforms any FCFS mutual exclusion algorithm M into a group mutual exclusion algorithm G. Thus, different group mutual exclusion algorithms can be obtained by instantiating M with different abortable FCFS mutual exclusion algorithms. The group mutual exclusion algorithms so obtained satisfy all of the properties mentioned above: mutual exclusion, lockout freedom, bounded exit, concurrent entering, FCFS, and FIFE.

We introduce f-array, a new type of shared object that generalizes the multiwriter snapshot object, and design efficient (linearizable and wait-free) algorithms for implementing it. f-arrays have made possible improved solutions to some important problems, as listed below:• A wait-free implementation of multiwriter snapshot, where the time complexity of scan and update operations is independent of the number of processes accessing the implementation.• A wait-free implementation of counter object whose time complexity has the dual advantage that it is adaptive and guarantees a small worst-case bound: the time complexity is O(1) for read and O(min(k, log n)) for increment, where k is point contention and n is the maximum number of processes that the implementation is designed to handle.• A wait-free implementation of a restricted version of a priority queue with similar time complexity as the counter implementation.• A local spinning mutual exclusion algorithm that admits processes into Critical Section (CS) according to their priorities; processes with the same priority enter the CS in first-come-first-served order. In both cache coherent and NUMA multiprocessors, a process makes at most O(min(k, log n)) remote references to complete the entry and exit sections once. To the best of our knowledge, this is the first mutual exclusion algorithm that supports process priorities and has sublinear worst-case time complexity.All algorithms in this paper require support for LL/SC instructions.

Lamport defined three classes of communication registers: safe, regular, and atomic. Wait-free implementations of one register class from a weaker class abound in the literature. However, results establishing the intrinsic complexity of such implementations are relatively scarce. In this paper, we consider the problem of implementing an n -valued single reader, single writer atomic register A from two regular registers, BUF and R , where BUF is a regular register that only the writer of A can write and R is a regular register that only the reader of A can write. (Lamport proved that there cannot be an implementation without R , so R is at least 2-valued in any implementation.) We present an almost space optimal implementation. Specifically, our results are: (1) An implementation for which BUF is 2 n -valued and R is 2-valued; and (2) A lower bound stating that, in any implementation, regardless of how large R is, BUF must be at least (2 n −1)-valued.

We show the following time and space complexity lower bounds. Let $\cal{I}$ be any randomized nonblocking n-process implementation of any object in set A from any combination of objects in set B, where A = {increment, fetch&add, modulo k counter (for any $k \ge 2n$), LL/SC bit, k-valued compare&swap (for any $k \ge n$), single-writer snapshot}, and B = {resettable consensus} $\cup$ {historyless objects such as registers and swap registers}. The space complexity of $\cal{I}$ is at least n-1. Moreover, if $\cal{I}$ is deterministic, both its time and space complexity are at least n-1. These lower bounds hold even if objects used in the implementation are of unbounded size. This improves on some of the $\Omega(\sqrt{n})$ space complexity lower bounds of Fich, Herlihy, and Shavit [i Proceedings of the 12th Annual ACM Symposium on Principles of Distributed Computing, Ithaca, NY, 1993, pp. 241--249; J. Assoc. Comput. Mach., 45 (1998), pp. 843--862]. It also shows the near optimality of some known wait-free implementations in terms of space complexity.

An implementation of a shared object O is t-tolerant if the object remains correct and wait-free even when up to t base objects (objects used in the implementation of O) fail. The implementation is gracefully degrading if, no matter how many base objects fail, O does not fail more severely than its base objects. For the omission failure mode, we derive a lower bound on the space complexity of a gracefully degrading t-tolerant implementation. This result lets us conclude that, for omission failures, graceful degradation can be achieved only at the cost of increased space complexity.

A (wait-free) universal construction is attractive because, no matter what types of wait-free objects are needed by applications, they can be implemented simply by instantiating the universal construction with the appropriate types. However, the worst-case time complexity of every existing n-process universal construction is # n): that is, in any implementation obtained by instantiating a universal construction, in the worst-case a process performs# n) computation in order to complete a single operation on the implemented object. In fact, a lower bound of # n) has been proved for the worst-case local time complexity of any oblivious universal construction [12]. Since universal constructions with sublinear time complexity do not seem possible, it is natural to explore "semiuniversal " constructions that can e#ciently implement large classes of objects (as opposed to all objects). We present such a construction in this paper. Our construction implements a large class of objects, that ...

Non-blocking and wait-free universal constructions have been a subject of active research in recent years. A universal construction is attractive because, no matter what types of shared objects are needed by applications, they can be implemented simply by instantiating the universal construction with appropriate types. This flexibility, however, comes at a cost: for each universal construction U , we prove that there is a type T such that, if O is an n-process type T object implemented using U , in the worst-case some process must perform# n) local computation in order to complete a single operation on O. A universal construction is oblivious if it does not exploit the semantics of the type that it is instantiated with. Our lower bound implies that if a shared object O is implemented using an oblivious universal construction, then no matter what O's type is, in the worst-case some process must perform# n) local computation in order to complete a single operation on O. Thu...

Many recent wait-free implementations are based on a sharedmemory that supports a pair of synchronization operations, known as LL and SC. In this paper, we establish an intrinsic performance limitation of these operations: even the simple wakeup problem [16], which requires some process to detect that all n processes are up, cannot be solved unless some process performs#for n) shared-memory operations. Using this basic result, we derive a#230 n) lower bound on the worst-case shared-access time complexity of n-process implementations of several types of objects, including fetch&increment, fetch&multiply, fetch&and, queue, and stack. (The worst-case shared-access time complexity of an implementation is the number of shared-memory operations that a process performs, in the worst-case, in order to complete a single operation on the implementation.) Our lower bound is strong in several ways: it holds even if (1) shared-memory has an infinite number of words, each of unbounded size, (2) sh...

Wait-free implementations of shared objects tolerate the failure of processes, but not the failure of base objects from which they are implemented. We consider the problem of implementing shared objects that tolerate the failure of both processes and base objects. We identify two classes of object failures: responsive and nonresponsive . With responsive failures, a faulty object responds to every operation, but its responses may be incorrect. With nonresponsive failures, a faulty object may also “hang” without responding. In each class, we define crash, omission, and arbitrary modes of failure. We show that all responsive failure modes can be tolerated. More precisely, for all responsive failure modes ℱ, object types T , and t ≥ 0, we show how to implement a shared object of type T which is t -tolerant for ℱ. Such an object remains correct and wait-free even if up to t base objects fail according to ℱ. In contrast to responsive failures, we show that even the most benign non-responsive failure mode cannot be tolerated. We also show that randomization can be used to circumvent this impossibility result. Graceful degradation is a desirable property of fault-tolerant implementations: the implemented object never fails more severely than the base objects it is derived from, even if all the base objects fail. For several failure modes, we show wheter this property can be achieved, and, if so, how.

Consensus, which requires processes with different input values to eventually agree on one of these values, is a fundamental problem in fault-tolerant computing. We study this problem in the context of asynchronous shared-memory systems. Prior research on consensus focused on its solvability using shared objects of specific types. In this paper, we investigate the following general question: Let T and T' be any two types. Consider the consensus problem among N processes. Suppose that this problem is unsolvable if processes may use only objects of any one type (T or T') for communication. Does it follow that the problem is unsolvable even if processes may use objects of both types? Recent results imply that the answer is positive if T and T' are both deterministic types. We prove that the answer is negative even if one of T and T' is nondeterministic.

The problem of implementing a shared object of one type from shared objects of other types has been extensively researched. Recent focus has mostly been on wait-free implementations , which permit every process to complete its operations on implemented objects, regardless of the speeds of other processes. It is known that shared objects of different types have differing abilities to support wait-free implementations. It is therefore natural to want to arrange types in a hierarchy that reflects their relative abilities to support wait-free implementations. In this paper, we formally define robustness and other desirable properties of hierarchies. Roughly speaking, a hierarchy is robust if each type is “stronger” than any combination of lower level types. We study two specific hierarchies: one, that we call h r m in which the level of a type is based on the ability of an unbounded number of objects of that type, and another hierarchy, that we call h r 1 , in which a type's level is based on the ability of a fixed number of objects of that type. We prove that resource bounded hierarchies, such as h r 1 and its variants, are not robust. We also establish the unique importance of h r m : every nontrivial robust hierarchy, if one exists, is necessarily a “coarsening” of h r m .

We show the following time and space complexity lower bounds.Let Z be any randomized nonbk, ;ng n-process implementation of any object in 1 from any combination of objects in set 1?, where A = {increment, store-conditional bit, compare@swap, bounded-counter, single-writer atomic snapshot, fetch~add}, and B = { resettable consensus, register, swap register}.The space complexity of ~is at least n -1.Moreover, if ~is deterministic, both its time and space complexit y are at least n -1.These lower bounds hold even if objects used in the implementation are of unbounded size.This improves on some of the C?(@) space com-plexit~lower bounds of Fich, Herlihy & Shavit [FHS93].It also shows the near optimality of Dome known wait-free implementations in terms of space complexity.

We seek two properties in such a hierarchy:(1) If a type T is at level N, then, for all types T',

A wait-free hierarchy maps object types to levels in {1, 2, 3,...} U {co}, and has the following property:if a type 2' is at level N, then, for all types T', there is a wait-free implementation of an object of type T', for N processes, using only registers and objects of type T. The infinite hierarchy defined by Herlihy is an example of a wait -free hierarchy.A wait-free hierarchy is TO bust if it has the following property: if a t ype T is at level N, and S is a finite set of types belonging to levels N -1 or lower, then there is no wait-free implementation of an object of type T, for N processes, using any number and any combination of objects belonging to the types in S. Robustness implies that there are no clever ways of combining weak shared objects to obtain stronger ones.Contrary to what many researchers believe, we prove that Herlihy's hierarchy is not robust.We then define some natural variants of Herlihy's hierarchy, which are also infinite wait-free hierarchies.With the exception of one, which is still open, these are not robust either.We conclude with the open question of whether a non-trivial robust wait-free hierarchies exists.

The authors classify object failures into two broad categories: responsive and non-responsive. They require that wait-free objects subject to responsive failures continue to respond (in finite time) to operation invocations. The responses may be incorrect. In contrast, wait-free objects subject to non-responsive failures are exempt from responding to operation invocations. Such objects may 'hang' on the invoking process. They divide responsive failures into three models: R-crash,R-omission, and R-arbitrary. They divide non-responsive failures into crash, omission, and arbitrary. An object subject to crash failure behaves correctly until it fails, and once it fails, it never responds to operation invocations. An object subject to omission failures may fail to respond to the invocations of an arbitrary subset of processes, but continue to respond to the invocations of the remaining processes (forever).>