Herlihy's wait-free consensus hierarchy classifies the power of object types in asynchronous shared memory systems where processes can permanently crash (i.e. stop taking steps). In this hierarchy a type has consensus number n if objects of that type can be used along with (read/write) registers to solve consensus among n processes that can permanently crash, but not among n + 1 or more processes. In systems where processes can recover after crashing, the power of an object type to solve consensus may be different. Golab's recoverable consensus hierarchy classifies the power of object types in such a system. In the recoverable consensus hierarchy, a type has recoverable consensus number n if objects of that type can be used along with registers to solve consensus among n processes that can recover after crashing, but not among n + 1 or more processes. In this paper, we prove that the recoverable consensus hierarchy of deterministic, readable types is robust, i.e., if consensus can be solved among n processes that can recover after crashing using a collection of objects of deterministic, readable types, then one of these types has recoverable consensus number at least n. This is important for comparing the relative computational power of different deterministic, readable types, because it implies that one cannot combine various objects to obtain an algorithm that is better at solving recoverable consensus than any of the individual object types. Our result can be used to show that, for all n ≥ 4, there exists a readable type with consensus number n and recoverable consensus number n − 2. We also show that, for all n > n′ ≥ 1, there exists a non-readable type that has consensus number n and recoverable consensus number n′.

Nearly thirty years ago, it was shown that \(\Omega (\sqrt {n})\) read/write registers are needed to solve randomized wait-free consensus among n processes. This lower bound was improved to n registers in 2018, which exactly matches known algorithms. The \(\Omega (\sqrt {n})\) space complexity lower bound actually applies to a class of objects called historyless objects, which includes registers, test-and-set objects, and readable swap objects. However, every known n -process obstruction-free consensus algorithm from historyless objects uses Ω ( n ) objects. In this paper, we give the first Ω ( n ) space complexity lower bounds on consensus algorithms for two kinds of historyless objects. First, we show that any obstruction-free consensus algorithm from swap objects uses at least n -1 objects. More generally, we prove that any obstruction-free k -set agreement algorithm from swap objects uses at least \(\lceil \frac{n}{k}\rceil - 1\) objects. The k -set agreement problem is a generalization of consensus in which processes agree on no more than k different output values. This is the first non-constant lower bound on the space complexity of solving k -set agreement with swap objects when k > 1. We also present an obstruction-free k -set agreement algorithm from n-k swap objects, which exactly matches our lower bound when k =1. Second, we show that any obstruction-free binary consensus algorithm from readable swap objects with domain size b uses at least \(\frac{n-2}{3b+1}\) objects. When b is a constant, this asymptotically matches the best known obstruction-free consensus algorithms from readable swap objects with unbounded domains. Since any historyless object can be simulated by a readable swap object with the same domain, our results imply that any obstruction-free consensus algorithm from historyless objects with domain size b uses at least \(\frac{n-2}{3b+1}\) objects. For b = 2, we show a slightly better lower bound of n -2. There is an obstruction-free binary consensus algorithm using 2 n -1 readable swap objects with domain size 2, asymptotically matching our lower bound.

Nearly thirty years ago, it was shown that $Ω(\sqrt{n})$ registers are needed to solve obstruction-free consensus among $n$ processes. This lower bound was improved to $n$ registers in 2018, which exactly matches the best upper bound. The $Ω(\sqrt{n})$ space complexity lower bound actually applies to a class of objects called historyless objects, which includes registers, test-and-set objects, and readable swap objects. However, every known $n$-process obstruction-free consensus algorithm from historyless objects uses $Ω(n)$ objects. We give the first $Ω(n)$ space complexity lower bounds on consensus algorithms for two kinds of historyless objects. First, we show that any obstruction-free consensus algorithm from swap objects uses at least $n-1$ objects. More generally, we prove that any obstruction-free $k$-set agreement algorithm from swap objects uses at least $\lceil \frac{n}{k}\rceil - 1$ objects. This is the first non-constant lower bound on the space complexity of solving $k$-set agreement with swap objects when $k > 1$. We also present an obstruction-free $k$-set agreement algorithm from $n-k$ swap objects, exactly matching our lower bound when $k=1$. Second, we show that any obstruction-free binary consensus algorithm from readable swap objects with domain size $b$ uses at least $\frac{n-2}{3b+1}$ objects. Since any historyless object can be simulated by a readable swap object with the same domain, our results imply that any obstruction-free consensus algorithm from historyless objects with domain size $b$ uses at least $\frac{n-2}{3b+1}$ objects. For $b = 2$, we show a slightly better lower bound of $n-2$. The best known obstruction-free binary consensus algorithm from readable swap objects with domain size $2$ uses $2n-1$ objects, asymptotically matching our lower bound.

Nearly thirty years ago, it was shown that Ω(√n ) read/write registers are needed to solve obstruction-free consensus among n processes. This lower bound was improved to n registers in 2018, which exactly matches the best upper bound. The Ømega (√n) space complexity lower bound actually applies to a class of objects called historyless objects, which includes read/write registers, test-and-set objects, and readable swap objects. However, every known n-process obstruction-free consensus algorithm from historyless objects uses Ω(n) objects.

Determining a consistent view of the contents of a shared array while its components are being modified is a fundamental task in distributed algorithm design. Snapshot objects address this problem when read/write registers are components of the array. A natural generalization of a snapshot object is a scannable object, an object with multiple components that each support Read and some other operations. Scannable objects also support the Scan operation, which provides an instantaneous view of all the object's components. This raises the question: How many instances of objects in some set O are required to implement a scannable object whose components are in O

Linearizability is the gold standard of correctness conditions for shared memory algorithms, and historically has been considered the practical equivalent of atomicity. However, it has been shown that replacing atomic objects with linearizable implementations can affect the probability distribution of execution outcomes in randomized algorithms. Thus, linearizable objects are not always suitable replacements for atomic objects. A stricter correctness condition called strong linearizability has been developed and shown to be appropriate for randomized algorithms in a strong adaptive adversary model[16].