Copyright and Licensing
Articles accepted for publication will be licensed under the Creative Commons BY-NC. Authors must sign a non-exclusive distribution agreement after article acceptance.
Group Mutual Exclusion Based on Priorities
Keywords:
Mutual Exclusion, Group Mutual Exclusion, Concurrency, Distributed SystemsAbstract
We propose a distributed solution for the group mutual exclusion problem based on priorities, in a network with no share memory whose members only communicate by messages. The proposed algorithm is composed by two players: groups and processes, groups are passive players while processes are active players. For the coordination access to the resource, each group has assigned a quorum. The groups have associated a base priority in each stage, meanwhile the processes have the same level priority. An important feature is that processes have associated a time to participate in the group in each stage. The message complexity obtain, in the best case, where the group does not yield the permission, is 3l + 3(q - 1) messages, where l denotes the processes linked and q denotes the quorum size. The maximum concurrency of the algorithm is n, which implies that all processes have linked to the same group.
Downloads
Download data is not yet available.
References
[1] D. Barbara and H. Garcı́a-Molina. Mutual exclusion in partitioned distributed systems. Distributed Computing, 1:119–132, 1986.
[2] K. M. Cenci and J. Ardenghi. Modelos dos actores para grupos de procesos. In XIV Congreso Argentino de Ciencias de la Computación (CACIC 2008), 2008.
[3] Y. J. Joung. Asynchronous group mutual exclusion (extended abstract). In Proceedings of the 17th Annual ACM Symposium on Principles of Distributed Computing (PODC’98), pages 51–60, June 1998.
[4] Y. J. Joung. Quorum-based algorithms for group mutual exclusion. IEEE Transactions on Parallel and Distributed Systems, pages 463–476, May 2003.
[5] H. Kakugawa, S. Kamei, and T. Masuzawa. A token-based group distributed group mutual exclusion algorithm with quorums. IEEE Transactions on Parallel and Distributed Systems, 19(9):1153–1166, September 2008.
[6] M. Maekawa. A N algorithm for mutual exclusion in decentralized systems. ACM Transactions on Computer Systems, 3(2):145–159, May 1985.
[7] Y. Manabe and J. Park. A quorum-based extended group mutual exclusion algorithm without unnecessary blocking. In Proceedings of th Tenth International Conference on Parallel and Distributed Systems, pages 341–348, 2004.
[8] J. F. Myoupo, M. Naimi, and O. Thiare. A clustering group mutual exclusion algorithm for mobile ad hoc networks. In IEEE Symposium on Computers and Communications, 2009. ISCC 2009., pages 693–696, 2009.
[9] Gurdip Singh and Ye Su. Efficient synchronization in message passing systems. In 22nd International Conference on Advanced Information Networking and Applicaciones, pages 219–226, 2008.
[10] A. Swaroop and A. K. Singh. A token-based group mutual exclusion algorithm for cellular wireless networks. In Annual IEEE India Conference (INDICON), pages 1–4, 2009.
[11] O. Thiare, M. Gueroui, and M. Naimi. Distributed groups mutual exclusion based on clients/servers model. In Proceedings of the Seventh Internacional Conference on Parallel and Distributed Computing, Applications and Technologies, pages 67–73, 2006.
[12] M. Toyomura, S. Kamei, and H. Kakugawa. A quorum-based distributed algorithm for group mutual exclusion. In Proceedings of the Fourth International Conference on Parallel and Distributed Computing, Applications and Technologies, pages 742–746, 2003.
[13] K. P. Wu and Y. J. Joung. Asynchronous group mutual exclusion in ring networks. In 13th International Parallel Processing Symposium / 10th Symposium on Parallel and Distributed Processing (IPPS / SPDP ’99). Proceedings. IEEE Computer Society, pages 539–543, April 1999.
[2] K. M. Cenci and J. Ardenghi. Modelos dos actores para grupos de procesos. In XIV Congreso Argentino de Ciencias de la Computación (CACIC 2008), 2008.
[3] Y. J. Joung. Asynchronous group mutual exclusion (extended abstract). In Proceedings of the 17th Annual ACM Symposium on Principles of Distributed Computing (PODC’98), pages 51–60, June 1998.
[4] Y. J. Joung. Quorum-based algorithms for group mutual exclusion. IEEE Transactions on Parallel and Distributed Systems, pages 463–476, May 2003.
[5] H. Kakugawa, S. Kamei, and T. Masuzawa. A token-based group distributed group mutual exclusion algorithm with quorums. IEEE Transactions on Parallel and Distributed Systems, 19(9):1153–1166, September 2008.
[6] M. Maekawa. A N algorithm for mutual exclusion in decentralized systems. ACM Transactions on Computer Systems, 3(2):145–159, May 1985.
[7] Y. Manabe and J. Park. A quorum-based extended group mutual exclusion algorithm without unnecessary blocking. In Proceedings of th Tenth International Conference on Parallel and Distributed Systems, pages 341–348, 2004.
[8] J. F. Myoupo, M. Naimi, and O. Thiare. A clustering group mutual exclusion algorithm for mobile ad hoc networks. In IEEE Symposium on Computers and Communications, 2009. ISCC 2009., pages 693–696, 2009.
[9] Gurdip Singh and Ye Su. Efficient synchronization in message passing systems. In 22nd International Conference on Advanced Information Networking and Applicaciones, pages 219–226, 2008.
[10] A. Swaroop and A. K. Singh. A token-based group mutual exclusion algorithm for cellular wireless networks. In Annual IEEE India Conference (INDICON), pages 1–4, 2009.
[11] O. Thiare, M. Gueroui, and M. Naimi. Distributed groups mutual exclusion based on clients/servers model. In Proceedings of the Seventh Internacional Conference on Parallel and Distributed Computing, Applications and Technologies, pages 67–73, 2006.
[12] M. Toyomura, S. Kamei, and H. Kakugawa. A quorum-based distributed algorithm for group mutual exclusion. In Proceedings of the Fourth International Conference on Parallel and Distributed Computing, Applications and Technologies, pages 742–746, 2003.
[13] K. P. Wu and Y. J. Joung. Asynchronous group mutual exclusion in ring networks. In 13th International Parallel Processing Symposium / 10th Symposium on Parallel and Distributed Processing (IPPS / SPDP ’99). Proceedings. IEEE Computer Society, pages 539–543, April 1999.
Downloads
Published
2011-04-01
How to Cite
Cenci, K. M., & Ardenghi, J. R. (2011). Group Mutual Exclusion Based on Priorities. Journal of Computer Science and Technology, 11(01), p. 21–26. Retrieved from https://journal.info.unlp.edu.ar/JCST/article/view/684
Issue
Section
Original Articles
