Research Article Open Access

A Token-Based Fair Algorithm for Group Mutual Exclusion in Distributed Systems

Abhishek Swaroop and Awadhesh Kumar Singh

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.

Journal of Computer Science
Volume 3 No. 10, 2007, 829-835

DOI: https://doi.org/10.3844/jcssp.2007.829.835

Submitted On: 19 June 2007 Published On: 31 October 2007

How to Cite: Swaroop, A. & Singh, A. K. (2007). A Token-Based Fair Algorithm for Group Mutual Exclusion in Distributed Systems. Journal of Computer Science, 3(10), 829-835. https://doi.org/10.3844/jcssp.2007.829.835

  • 2,747 Views
  • 2,373 Downloads
  • 5 Citations

Download

Keywords

  • Concurrency
  • critical section
  • request set
  • session