Improved Asynchronous Group Mutual Exclusion in Token-Passing Networks

D. Lin, T.-S. Moh, and M. Moh (USA)


Distributed algorithm, group mutual exclusion, message passing, token passing.


: Group mutual exclusion (GME) was first introduced by Joung [5] as a generalization of the n-process mutual exclusion problem, and subsequently modeled as the Congenial Talking Philosophers problem. GME allows processes requesting for the same resource to concurrently access the shared resource. However, a process requesting a resource that is different from the one currently being used will not be able to access the requested resource at the same time. Two solutions to the GME problem for a ring network exist. One by Wu and Joung had an unbounded message size problem [11, 12], the second one by Cantarell, et. al. provided a bound for message size, but could potentially generate an unbounded number of messages [2, 3]. This work presents a GME algorithm for a token-passing network that solves both problems by providing a bound both to the number of messages and to message size. Analysis results of time and message complexities and of correctness are presented. Performance is evaluated by simulation experiments, which further validate complexity analyses.

Important Links:

Go Back