| ||||||||||||||||||||||||||||||||||||||||||||||||||||
Group Mutual Exclusion in Token Rings
1 LRI/CNRS, Université de Paris-Sud, France, 2 School of Computer Science, University of Nevada Las Vegas, Nevada, 3 LaRIA/CNRS, Université de Picardie Jules Verne, France
The group mutual exclusion (GME) problem was introduced by Joung. The GME solution allows n processes to share m mutually exclusive resources. We present several algorithms to solve the GME problem in token rings. The space requirement and the size of messages of all algorithms are bounded. So, the proposed algorithms solve the problem suggested by Joung, which is to obtain a solution using messages of bounded size. The time and space complexities of the first and second algorithms depend on n and m respectively. The first algorithm is more efficient when n << m, whereas the second one when m << n. The cost of the third algorithm is min(n, m). So, it is suitable for any type of network. However, the third solution is obtained with a message size of log(min(n, m)) extra bits. The third algorithm has an additional desirable property. It serves the requests in a first in first out manner. The fourth algorithm improves the bandwidth usage by avoiding the token circulation when no new requests are made for a different session. This property of the fourth algorithm can be incorporated into the other three algorithms.
Received 8 August 2003. revised 27 September 2004.