Skip to main content
SpringerLink
Log in

Using Logical Rings to Solve the Distributed Mutual Exclusion Problem with Fault Tolerance Issues

  • Published:
The Journal of Supercomputing Aims and scope Submit manuscript

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.

This is a preview of subscription content, log in via an institution to check access.

Access this article

Log in via an institution

Price excludes VAT (USA)
Tax calculation will be finalised during checkout.

Instant access to the full article PDF.

Institutional subscriptions

Similar content being viewed by others

References

  1. 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.

    Google Scholar 

  2. O. Carvalho and G. Roucairol. On mutual exclusion in computer networks. Communications of the ACM, 26(2): 146–147, February 1983.

    Google Scholar 

  3. 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.

  4. T. Johnson. A performance comparison of fast distributed mutual exclusion algorithms. Proceedings of the 9th International Parallel Processing Symposium, pp. 258–264, April 1995.

  5. L. Lamport. Time clocks and ordering of events in distributed systems. Communications of the ACM, 21(7): 558–565, July 1978.

    Google Scholar 

  6. G. LeLann. Motivation, objective, and characteristics of distributed systems. Springer-Verlag, 1(1): 1–9, October 1978.

    Google Scholar 

  7. M. Maekawa. A √N algorithm for mutual exclusion in decentralized systems. ACM Transactions on Computer Systems, 3(2): 145–149, May 1985.

    Google Scholar 

  8. 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.

    Google Scholar 

  9. 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.

  10. 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.

  11. K. Makki. An efficient token based distributed mutual exclusion algorithm. Journal of Computer and Software Engineering, 2(4): 401–416, December 1994.

    Google Scholar 

  12. 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.

  13. 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.

  14. K. Raymond. A tree based algorithm for distributed mutual exclusion. ACM Transactions on Computer Systems, 7(1): 61–77, Feb. 1989.

    Google Scholar 

  15. 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.

    Google Scholar 

  16. B. Sanders. The information structure of distributed mutual exclusion algorithms. ACM Transactions on Computer Systems, 5(3): 284–289, Aug. 1987.

    Google Scholar 

  17. M. Singhal. A taxonomy of distributed mutual exclusion. Journal of Parallel and Distributed Computing, 18: 94–101, 1993.

    Google Scholar 

  18. I. Suzuki and T. Kasami. A distributed mutual exclusion algorithm. ACM Transactions on Computer Systems, 3(4): 344–349, Nov. 1985.

    Google Scholar 

Download references

Author information

Authors and Affiliations

  1. Center for Telecommunication Studies, University of Louisiana, Lafayette, Lafayette, Louisiana, 70504

    Kia Makki

  2. Center for Telecommunication Studies, University of Louisiana, Lafayette, Lafayette, Louisiana, 70504

    John Dell

  3. Center for Advanced Computer Studies, University of Southwestern Louisiana, Lafayette, Louisiana, 70504

    Niki Pissinou

  4. Dept. of Math. and Computer Science, San Jose State University, San Jose, CA, 95192-0103

    W. Melody Moh

  5. Dept. of Computer Science, City University of Hong Kong, Hong Kong, China

    Xiaohua Jia

Authors
  1. Kia Makki
    View author publications

    You can also search for this author in PubMed Google Scholar

  2. John Dell
    View author publications

    You can also search for this author in PubMed Google Scholar

  3. Niki Pissinou
    View author publications

    You can also search for this author in PubMed Google Scholar

  4. W. Melody Moh
    View author publications

    You can also search for this author in PubMed Google Scholar

  5. Xiaohua Jia
    View author publications

    You can also search for this author in PubMed Google Scholar

Rights and permissions

Reprints 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

Download citation

  • Issue Date:

  • DOI: https://doi.org/10.1023/A:1008137614672

Search

Navigation