text: We present two algorithms for the Group Mutual Exclusion (GME) Problem that satisfy the properties of Mutual Exclusion, Starvation Freedom, Bounded Exit, Concurrent Entry and First Come First Served. Both our algorithms use only simple read and write instructions, have O(N) Shared Space complexity and O(N) Remote Memory Reference (RMR) complexity in the Cache Coherency (CC) model. Our first algorithm is developed by generalizing the well-known Lamport's Bakery Algorithm for the classical mutual exclusion problem, while preserving its simplicity and elegance. However, it uses unbounded shared registers. Our second algorithm uses only bounded registers and is developed by generalizing Taubenfeld's Black and White Bakery Algorithm to solve the classical mutual exclusion problem using only bounded shared registers. We show that contrary to common perception our algorithms are the first to achieve these properties with these combination of complexities.
  @cite_6: Group mutual exclusion is a natural problem, formulated by Joung in 1998, that generalises the classical mutual exclusion problem. In group mutual exclusion a process requests a “session” before entering its critical section; processes are allowed to be in the critical section simultaneously provided they have requested the same session. To rule out solutions that cause processes to delay each other even when they all request the same session, group mutual exclusion algorithms must satisfy a property called “concurrent entering”. Joung stated this property only informally. Keane and Moir later gave a precise statement of this property and devised a simple group mutual exclusion algorithm that satisfies it. We argue that Keane and Moir's formulation is not quite as strong as the property Joung described informally. We propose a new precise and simple formulation of concurrent entering that is stronger than Keane and Moir's and properly captures Joung's intention. Keane and Moir's algorithm does not satisfy this stronger property, while Joung's original algorithm does. We present another algorithm that satisfies this stronger property and has some advantages over Joung's.
summary: Joung's original algorithm for the GME problem satisfies the four basic properties. It does not satisfy the FCFS property. Moreover, it has unbounded RMR complexity. Hadzilacos (see @cite_6 ) gave the first solution for the GME problem that has the FCFS property. His algorithm can be thought of as a modular composition of two independent algorithms, one, the FCFS algorithm'' provides FCFS property (but not necessarily guarantee mutual exclusion) and the other, the ME algorithm'' provides mutual exclusion property (but not necessarily FCFS). This algorithm has shared space complexity of @math . It was (mistakenly in hindsight) claimed that the algorithm has RMR complexity of @math in the CC model. The algorithm was using only bounded shared variables and simple read and write operations. It was left as an open problem to develop a solution (satisfying P1 through P5) for the GME problem that runs in linear time and space using only bounded shared variables.