Abstract
In this paper, we investigate distributed mutual exclusion algorithms and delineate the features of a new distributed mutual exclusion algorithm. The basis of the algorithm is the logical ring structure employed in token-based mutual exclusion algorithms. Specifically, there exists dynamic properties of the logical ring that, given certain restrictions regarding message traffic flow, passively give useful information about the location of the token. Effectively, the algorithm demonstrates a type of “intelligent routing” that identifies useful shortcuts in the routing of the token. The result is a reduction in the total number of messages exchanged prior to the execution of the critical section as compared to the algorithm proposed by Fu and Tzeng [3]. Furthermore, the algorithm allows for an increased degree of fairness in a lightly loaded system than that allowed by Fu and Tzeng's algorithm. The paper also addresses failure recovery issues.
Similar content being viewed by others
References
D. Agrawala and A. Abbadi. An efficient and fault tolerant solution for distributed mutual exclusion. ACM Transactions on Computer Systems, 9(1): 1–20, Feb. 1991.
O. Carvalho and G. Roucairol. On mutual exclusion in computer networks. Communications of the ACM, 26(2): 146–147, February 1983.
S. Fu and N. Tzeng. Efficent Token-Based Approach to Mutual Exclusion in Distributed Memory Systems. TR #TR-95–8–1, University of Southwestern Louisiana, pp. 1–18, July 1995.
T. Johnson. A performance comparison of fast distributed mutual exclusion algorithms. Proceedings of the 9th International Parallel Processing Symposium, pp. 258–264, April 1995.
L. Lamport. Time clocks and ordering of events in distributed systems. Communications of the ACM, 21(7): 558–565, July 1978.
G. LeLann. Motivation, objective, and characteristics of distributed systems. Springer-Verlag, 1(1): 1–9, October 1978.
M. Maekawa. A √N algorithm for mutual exclusion in decentralized systems. ACM Transactions on Computer Systems, 3(2): 145–149, May 1985.
K. Makki, K. Been and N. Pissinou. A Simulation Study of Token-Based Mutual Exclusion Algorithms in Distributed Systems. International Journal in Computer Simulation, 4: 65–88, 1994.
K. Makki, P. Banta, K. Been and R. Ogawa. Two algorithms for mutual exclusion in a distributed system. In Proc. Of the International Conference on Parallel Processing, pp. 460–466, Aug. 1991.
K. Makki, N. Pissinou and E. Park. An efficient solution to the critical section problem. Proceedings of the International Conference on Parallel Processing, St. Charles, IL, pp. 77–80, August 1994.
K. Makki. An efficient token based distributed mutual exclusion algorithm. Journal of Computer and Software Engineering, 2(4): 401–416, December 1994.
M. Naimi and M. Trehel. An improvement of the log(n) distributed algorithm for mutual exclusion. In Proc. of the 7th International Conference on Distributed Computing Systems, pp. 371–375, Sept. 1987.
N. Pissinou, K. Makki, E. Park, Z. Hu and W. Wong. An efficient distributed mutual exclusion algorithm. 1996 International Conference on Parallel Processing, pp. 196–203, 1996.
K. Raymond. A tree based algorithm for distributed mutual exclusion. ACM Transactions on Computer Systems, 7(1): 61–77, Feb. 1989.
G. Ricart and A. Agrawala. Authors’ response to “On Mutual exclusion in Computer networks” by Carvalho and Roucairol. Communications of the ACM, 26(2): 147–148, 1983.
B. Sanders. The information structure of distributed mutual exclusion algorithms. ACM Transactions on Computer Systems, 5(3): 284–289, Aug. 1987.
M. Singhal. A taxonomy of distributed mutual exclusion. Journal of Parallel and Distributed Computing, 18: 94–101, 1993.
I. Suzuki and T. Kasami. A distributed mutual exclusion algorithm. ACM Transactions on Computer Systems, 3(4): 344–349, Nov. 1985.
Author information
Authors and Affiliations
Rights and permissions
About this article
Cite this article
Makki, K., Dell, J., Pissinou, N. et al. Using Logical Rings to Solve the Distributed Mutual Exclusion Problem with Fault Tolerance Issues. The Journal of Supercomputing 16, 117–132 (2000). https://doi.org/10.1023/A:1008137614672
Issue Date:
DOI: https://doi.org/10.1023/A:1008137614672