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

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

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.