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

Authors: S. Dehghan, A.M. Rahmani

Abstract:

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.

Keywords: Group Mutual Exclusion (GME), Extended GME, Distributed systems.

Digital Object Identifier (DOI): doi.org/10.5281/zenodo.1060177

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.