We present tradeoffs between RMR complexity and memory word size for recoverable mutual exclusion (RME) algorithms using arbitrary synchronization primitives. Assuming that each memory location stores w bits, we show that n-process mutual exclusion has an RMR complexity of at least Ω (min{logw n, log n/log log n}) on the DSM and the CC model. For w = (log n)Ω(1), our lower bound asymptotically matches an upper bound by Katzan and Morrison [19], whose RME mutual exclusion algorithm employs w-bit fetch-and-add operations. Our lower bound is the first one that does not restrict the type of atomic operations that can be executed on a memory location.

We present a tight RMR complexity lower bound for the recoverable mutual exclusion (RME) problem, defined by Golab and Ramaraju [9]. In particular, we show that any n-process RME algorithm using only atomic read, write, fetch-and-store, fetch-and-increment, and compare-and-swap operations, has an RMR complexity of Ω(log n/log log n) on the CC and DSM model. This lower bound covers all realistic synchronization primitives that have been used in RME algorithms and matches the best upper bounds of algorithms employing swap objects (e.g.,[6,7,11]).

Motivated by advances in non-volatile memory technology, recent research in mutual exclusion has focused on algorithms for a shared memory model, in which failed processes can recover from crashes. Golab and Ramaraju [9] defined the recoverable mutual exclusion problem, where a process may crash during a mutual exclusion protocol. Upon crashing a process's local memory is erased, and it starts a recovery procedure. The contents of the shared memory survives process failures.

Since the early days of the shared memory model for distributed computing, researchers have sought a simple and precise characterization of an object's ability to implement other objects in a wait-free manner.

The set agreement power of a shared object O describes O's ability to solve set agreement problems: it is the sequence (n_1, n_2, ..., n_k, ...) such that, for every k >= 1, using O and registers one can solve the k-set agreement problem among at most n_k processes. It has been shown that the ability of an object O to implement other objects is not fully characterized by its consensus number the first component of its set agreement power) [1, 3, 14]. This raises the following natural question: is the ability of an object O to implement other objects fully characterized by its set agreement power? We prove that the answer is no: every level n >= 2 of Herlihy's consensus hierarchy has two objects that have the same set agreement power but are not equivalent, i.e., at least one cannot implement the other. We also show that every level n >= 2 of the consensus hierarchy contains a deterministic object O_n with some set agreement power (n_1, n_2, ..., n_k, ...) such that being able to solve the k-set agreement problems among n_k processes, for all k >= 1, is not enough to implement O_n.

We first prove that there are uncountably many objects with distinct computational powers. More precisely, we show that there is an uncountable set of objects such that for any two of them, at least one cannot be implemented from the other (and registers) in a wait-free manner. We then strengthen this result by showing that there are uncountably many linearizable objects with distinct computational powers. To do so, we prove that for all positive integers n and k, there is a linearizable object that is computationally equivalent to the k-set agreement task among n processes. To the best of our knowledge, these are the first linearizable objects proven to be computationally equivalent to set agreement tasks.