A note on group mutual exclusion

ABSTRACT

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.

REFERENCES

• 1: K. Alagarsamy and K. Vidyasankar. Elegant solutions for group mutual exclusion problem. Unpublished manuscript, 1999.
• 2: James Edward Burns, Complexity of communication among asynchronous parallel processes, 1981
• 3: E. W. Dijkstra, Solution of a problem in concurrent programming control, Communications of the ACM, v.8 n.9, p.569, Sept. 1965 [doi>10.1145/365559.365617]
• 4: Maurice Herlihy, Wait-free synchronization, ACM Transactions on Programming Languages and Systems (TOPLAS), v.13 n.1, p.124-149, Jan. 1991 [doi>10.1145/114005.102808]
• 5: Yuh-Jzer Joung, Asynchronous group mutual exclusion (extended abstract), Proceedings of the seventeenth annual ACM symposium on Principles of distributed computing, p.51-60, June 28-July 02, 1998, Puerto Vallarta, Mexico [doi>10.1145/277697.277706]
• 6: Patrick Keane , Mark Moir, A simple local-spin group mutual exclusion algorithm, Proceedings of the eighteenth annual ACM symposium on Principles of distributed computing, p.23-32, May 04-06, 1999, Atlanta, Georgia, United States [doi>10.1145/301308.301319]
• 7: Leslie Lamport, A new solution of Dijkstra's concurrent programming problem, Communications of the ACM, v.17 n.8, p.453-455, Aug. 1974 [doi>10.1145/361082.361093]
• 8: Leslie Lamport, The mutual exclusion problem: part I—a theory of interprocess communication, Journal of the ACM (JACM), v.33 n.2, p.313-326, April 1986 [doi>10.1145/5383.5384]
• 9: Leslie Lamport, A fast mutual exclusion algorithm, ACM Transactions on Computer Systems (TOCS), v.5 n.1, p.1-11, Feb. 1987 [doi>10.1145/7351.7352]
• 10: Edward A. Lycklama , Vassos Hadzilacos, A first-come-first-served mutual-exclusion algorithm with small communication variables, ACM Transactions on Programming Languages and Systems (TOPLAS), v.13 n.4, p.558-576, Oct. 1991 [doi>10.1145/115372.115370]
• 11: Jae-Heon Yang and James H. Anderson. A fast, scalable mutual exclusion algorithm. Distributed Computing, 9:51-60, 1995.

INDEX TERMS

Primary Classification:
  D. Software
  D.4 OPERATING SYSTEMS
      D.4.1 Process Management
          Subjects: Mutual exclusion

Additional Classification:
  C. Computer Systems Organization
  C.2 COMPUTER-COMMUNICATION NETWORKS
      C.2.1 Network Architecture and Design
          Subjects: Network communications
      C.2.4 Distributed Systems

General Terms:
Algorithms, Measurement, Theory