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 present an algorithm to solve the group mutual exclusion, problem in the cache-coherent (CC) model. For the same problem in the distributed shared memory (DSM) model, Danek and Hadzilacos presented algorithms of O(n) remote memory references (RMR) and proved a matching lower bound, where n is the number of processes. We show that in the CC model, using registers and LL/SC variables, our algorithm achieves O(min(log n,k)) RMR, where k is the point contention, which is so far the best. Moreover, given a recent result of Attiya, Hendler and Woelfel showing that exclusion problems have a Ω(log n) RME lower bound using registers, comparison primitives and LL/SC variables, our algorithm thus achieves the best theoretical bound.

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].