A Token-Based Fair Algorithm for Group Mutual Exclusion in Distributed Systems
Abstract
The group mutual exclusion (GME) problem is a generalization of the mutual exclusion problem. In group mutual exclusion, a process requests a session before entering its critical section (CS). Processes requesting the same session are allowed to be in their CS simultaneously, however, processes requesting different sessions must execute their CS in mutually exclusive way. The paper presents a token-based distributed algorithm for the GME problem in asynchronous message passing systems. The algorithm uses the concept of dynamic request sets. The algorithm does not use any message to be exchanged in the best case and uses n+1 messages in the worst case, where n is the number of processes in the system. The maximum concurrency of the algorithm is n and synchronization delay under heavy load (worst case) is 2T, where T is the maximum message propagation delay. The algorithm uses first come first serve approach in selecting the next session type and satisfies the concurrent occupancy property. The static performance analysis and correctness proof is also included in the present exposition.
DOI: https://doi.org/10.3844/jcssp.2007.829.835
Copyright: © 2007 Abhishek Swaroop and Awadhesh Kumar Singh. This is an open access article distributed under the terms of the Creative Commons Attribution License, which permits unrestricted use, distribution, and reproduction in any medium, provided the original author and source are credited.
- 3,331 Views
- 2,667 Downloads
- 5 Citations
Download
Keywords
- Concurrency
- critical section
- request set
- session