A New Extended Group Mutual Exclusion Algorithm with Low Message Complexity in Distributed Systems

The group mutual exclusion (GME) problem is an interesting generalization of the mutual exclusion problem. In the group mutual exclusion, multiple processes can enter a critical section simultaneously if they belong to the same group. In the extended group mutual exclusion, each process is a member of multiple groups at the same time. As a result, after the process by selecting a group enter critical section, other processes can select the same group with its belonging group and can enter critical section at the moment, so that it avoids their unnecessary blocking. This paper presents a quorum-based distributed algorithm for the extended group mutual exclusion problem. The message complexity of our algorithm is O(4Q ) in the best case and O(5Q) in the worst case, where Q is a quorum size.

Authors:

• S. Dehghan
• A.M. Rahmani

Keywords:

• Group Mutual Exclusion (GME)
• Extended GME
• Distributed systems.

References:

[1] Y.-J. Joung, Asynchronous group mutual exclusion, Distributed
Computing, 13,4, pp. 189-206 , 2000.
[2] Y.-J. Joung. Asynchronous group mutual exclusion (extended abstract).
In Proceedings of the 17th Annual ACM Symposium on Principles of
Distributed Computing (PDOC), Puerto Vallarta, Mexico, ACM Press,
pages 51-60, June 28-July 2, 1998.
[3] Y.-J. Joung, Quorum-based algorithm for group mutual exclusion, IEEE
Trans. on Parallel and Distributed Systems, Vol.14, No.5, pages 463-
476, May 2003.
[4] V. Hadzlilacos, A note on group mutual exclusion, Proc. Of 20th
PODC, pp. 100-106, 2001.
[5] P. Jayanti, S. Petrovic, and K. Tan, Fair Group Mutual Exclusion, Proc.
22nd PODC, pp. 275-284, 2003.
[6] P. Keane, M. Moir, A simple local-spin group mutual exclusion
algorithm, IEEE Trans. Parallel and Distributed Systems, 12, 7, pages
673-685, 2001.
[7] K. Vidyasankar, A highly concurrent group mutual l-exclusion
algorithm, Proc. of 21th PODC, 2002.
[8] S. Cantareli, A.K. Datta, F. Petit, V. Villain, Token Based group mutual
exclusion for asynchronous rings, Proc. of 21st ICDCS, pages 691-694,
2001.
[9] S. Cantareli, A.K. Datta, F. Perit, V. Villain, Group Mutual Exclusion in
Token Rings, Proc.of 8thColloquium Structural Information and
Communication Complexity, June 2001.
[10] K.-P. Wu, Y.-J. Joung, Asynchronous Group Mutual Exclusion in Ring
Networks, IEEE Proc. Computers and Digital Techniques, Vol.147,
No.1, pp.1-8, 2000.
[11] Q.E.K. Mamun, H. Nakazato,, A New Token Based Protocol for Group
Mutual Exclusion in Distributed System, Proceedings of The Fifth
International Symposium on Parallel and Distributed Computing
(ISPDC'06), 2006.
[12] R. Atreya, N. Mittel, A Distributed Group Mutual Exclusion Algorithm
using Surrogate-Quorums, Technical Report, The University of Texas at
Dallas, 2003.
[13] M. Toyomura, S. Kamei, and H. Kakugawa, A Quorum based
Distributed Algorithm for Group Mutual Exclusion, Proc. 4th Int. Conf.
on Parallel and Distributed Computing, Applications and Technologies,
pp.74-74, Aug. 2003.
[14] Yoshifumi Manabe, JaeHyrk Park, A quorum-based extended group
mutual exclusion algorithm without unnecessary blocking, Proceedings
of the Tenth International Conference on Parallel and Distributed
Systems (ICPADS-04), pp. 341 - 348, July 2004.
[15] L. Lamport. Time, clocks, and the ordering of events in a distributed
system. Communications of the ACM, 21(7):558-565, July 1978.
[16] M. Maekawa. A N algorithm for mutual exclusion in decentralized
systems. ACM transactions on Computer Systems, 3(2):145-159, March
1985.
[17] H. Garcia-Molina, D. Barbara, How to assign votes in a distributed
system, Journal of the ACM, 32, 4, pp. 841-860, 1985.