Email this article 
A Study of Token Based Algorithms for Distributed Mutual Exclusion
(*) Corresponding author
DOI's assignment:
the author of the article can submit here a request for assignment of a DOI number to this resource!
Cost of the service: euros 10,00 (for a DOI)
Abstract
The selection of a ‘good’ mutual exclusion algorithm, for the design of distributed systems, is of great importance. A number of mutual exclusion algorithms, with different techniques and varying performance characteristics, are available in the literature. These algorithms can be broadly classified into token based algorithms and non-token based algorithms. A number of survey papers for non-token based mutual exclusion algorithms exist. Although, some of them include discussion on token based mutual exclusion algorithms too, however, none of them include any discussion on the newer variants of classic mutual exclusion, like k-mutual exclusion and group mutual exclusion. The paper presents an exhaustive survey of the token based mutual exclusion algorithms. The variants of mutual exclusion problem, namely k-mutual exclusion and group mutual exclusion, have also been covered.
Copyright © 2017 Praise Worthy Prize - All rights reserved.
Keywords
References
E.W. Dijkastra, Co-operating sequential processes, in F.Geniys (Ed.), Programming Languages, Academic press, pp. 43 –112, 1965.
K.M. Chandy, J. Mishra, The drinking philosopher problem, ACM Transactions on Programming Languages and Systems, vol 6 (4), pp. 632 – 646, 1984.
K. Raymond, A distributed algorithm for multiple entries to a critical section, Information Processing Letters, vol. 30, pp. 189 – 193, 1989.
Y.J. Joung, Asynchronous group mutual exclusion, Distributed Computing vol. 13, no.4, pp. 189-206, 2000.
K.Vidyasankar, A simple group mutual l-exclusion algorithm, Information Processing Letters, vol. 12, pp. 79-85, 1981.
J. Anderson, Y.J. Kim, An improved lower bound for the time complexity of mutual exclusion, In the Proceedings of the 20th annual ACM Symposium on Principles of Distributed Computing, pp. 90 –99, 2001.
L. Lamport, A fast mutual exclusion algorithm, ACM Transactions on Computer Systems, vol. 5, no.1, pp. 1 – 11, 1987.
N. Lynch, N. Shavit , Timing based mutual exclusion, In Proceedings of the 13th IEEE Real Time Systems Symposium pp. 2 – 11, 1992.
E. Styer, Improving fast mutual exclusion, In the Proceedings of 11th annual ACM Symposium on Principles of Distributed Computing, pp. 159 – 168, 1992.
E. Lycklama, V. Hadzilacos, A first–come- first-served mutual exclusion algorithm with small communication variables, ACM Transactions on Programming Languages and Systems vol. 13, no.4, pp. 558 –576, 1991.
D.K. Gifford, Weighted voting for replicated data, Proceedings of 7th Symposium on Operating Systems, ACM, pp. 150 –162, 1979.
T.H. Thomas, A majority consensus approach to concurrency control, ACM Transactions on Database Systems, vol. 4, no.2, pp. 180 – 209, 1979.
Barbara, H. Garcia-Molina, Mutual exclusion in partitioned distributed systems, Distributed Computing vol. 1, pp. 119 – 132, 1986.
H. Garcia-Molina, D. Barbara, How to assign votes in a distributed system, Journal of the Associated Computing Machinery , vol. 2, no. 4, pp. 841– 860, 1985.
M. Maekawa, A Ön algorithm for mutual exclusion in decentralized systems, ACM Transactions on Computer Systems, v ol. 3, no. 2, pp. 145 – 159, 1985.
D. Agrawal, A. El Abbadi, A token based fault tolerant distributed mutual exclusion algorithm, Journal of Parallel and Distributed Computing, 24 , pp. 164 – 176, 1995.
Y.I. Chang, M. Singhal, M.T. Liu, A dynamic token based distributed mutual exclusion algorithm, In the Proceedings of 10th annual Intl. Phoenix Conference on Computers and Communications, pp. 240 – 246, 1991.
I. Suzuki, T. Kasmi, A distributed mutual exclusion algorithm, ACM Transactions on Computer Systems, vol. l3, no. 4, pp. 344 – 349, 1985.
G. Ricart, A.K. Agarwala, An optimal algorithm for mutual exclusion in computer networks, Communications of the ACM, vol. 24, no. 1, pp. 9 – 17, 1981.
S. Nishio, K.F. Li, and E.G. Manning, A resilient mutual exclusion algorithm for computer networks, IEEE Transaction on Parallel and Distributed System, vol. 1, no. 3, pp. 344 –355, 1990.
M. Singhal, A heuristically–aided Algorithm for mutual exclusion in distributed systems, IEEE Transactions on Computers, vol. 38, no.5, pp. 651 – 662, 1989.
Ye-In Chang, M.Singhal , and M.T.Liu, A dynamic token based distributed mutual exclusion algorithm, 10th Annual international phoenix conference on computers and communications, pp. 240-246, 1991.
M. Mizuno, M.L. Neilson, R. Rao, A token based distributed mutual exclusion algorithm based on quorum agreements, In Proceedings of the 11th Inte. Conference on Distributed Computing Systems, pp. 361 – 368, 1991.
Y.Yan, X. Zhang, H.Yang, A fast token chasing mutual exclusion algorithm in arbitrary network topologies, Journal of Parallel and Distributed Computing, 35, pp. 156 – 172, 1996.
P.C. Saxena, S. Gupta, A token based delay optimal algorithm for mutual exclusion in distributed systems, Computer Standards& Interfaces, vol. 21, pp. 33 – 50, 1999.
K. Raymond, A tree based algorithm for distributed mutual exclusion, ACM Transactions on Computer Systems, vol. 7, no.1, pp. 61 – 77, 1989.
M. Naimi, M.Trehel, A. Arnold, A Log (N) distributed mutual exclusion algorithm based on path reversal, Journal of Parallel and Distributed Computing, 34 ,pp. 1 – 13, 1996.
J. Sopena, L. Arantes, M. Bertier, P. Sens, A Fault tolerant token based mutual exclusion algorithm using a dynamic tree, LNCS 3648 (2005) 654 – 663.
M. Naimi, M. Trehel, How to detect a failure and regenerate the token in the log(n) distributed algorithm for mutual exclusion, Lecture Notes in Computer Science LNCS 312 (1987) 155 – 165.
M. Bertier, L. Arantes, P. Sens, Hierarchical token based mutual exclusion algorithms, IEEE International Symposium on Cluster Computing and the Grid, pp. 539 – 546, 2004.
D. Agrawal, A. El Abbadi, A token based fault tolerant distributed mutual exclusion algorithm, Journal of Parallel and Distributed Computing, 24, pp. 164 – 176, 1995.
J. Kiniwa, Request based token passing for self stabilizing mutual exclusion, International Conference on Parallel and Distributed Computing Systems, 2003.
E.W. Felton, M. Rabinovich, A centralized token based algorithm for distributed mutual exclusion, Technical report 92-02-02, department of computer science, university of Washington, 1992.
M.Y. Wu, W. Shu, An efficient distributed token based mutual exclusion algorithm with central coordinator, Journal of Parallel and Distributed Computing, 62 pp. 1602 –1613, 2002.
P.K. Srimani, R.L. Reddy, Another distributed algorithm for multiple entries to critical section, Information processing letters, 30, pp. 189 – 193, 1992.
M. Naimi, Distributed algorithm for k-entries to critical section based on the directed graphs, ACM SIGOPS Operating System Review, vol. 27, no.4, pp. 65 – 75, 1993.
K. Makki, P. Banta, K. Been, N .Pissinou, E.K. Park, A token based distributed k mutual exclusion algorithm, In IEEE Proceedings of the Symposium on Parallel and Distributed Processing, pp. 408 – 411, 1992.
S. Wang, S. D. Lang, A tree based distributed algorithm for the k entry critical section problem, In IEEE International Conference on Distributed Computing Systems, pp. 153 – 160, 1995.
S. Bulgannawar, N.H. Vaidya, A distributed k mutual exclusion algorithm, International Conference on Distributed Computing Systems, pp. 153 – 160, 1995.
Y.J. Joung, The Congenial taking philosopher problem in computer networks, Distributed Computing, vol. 15, pp. 155 – 175, 2000.
V. Hadzilacos, A note on group mutual exclusion, In Proceedings of the 20th ACM Symposium on Principles of Distributed Computing, pp. 100 – 106, 2001.
P. Kean, M. Moir, A simple local spin group mutual exclusion algorithm, In: Proceedings of the 18th annual ACM Symposium on Principles of Distributed Computing, pp. 23 – 32, 1993.
P. Jayanti, S. Petrovic, K. Tan, Fair group mutual exclusion, In the Proceedings of 22nd PODC, pp. 275 – 284, 2003.
Y. Manabe, J. Park, A quorum based extended group mutual exclusion algorithm without unnecessary blocking, In Proceedings of 10th International Conference on Parallel and Distributed Systems (ICPADS’04) pp. 341– 348, 2004.
K.P. Wu, Y.J. Joung, Asynchronous group mutual exclusion in ring networks, In Proceedings of 13th International Parallel Processing Symposium (IPPS ’99), pp. 539 – 543, 1999.
R. Attreya, N. Mittal, A dynamic group mutual exclusion algorithm using surrogate quorums, In the Proceedings of the 25th IEEE Conference on Distributed Computing Systems(ICSDCS’05), 2005.
S. Cantarell, A.K. Dutta, F. Pilit, V. Villain,Token based group mutual exclusion for asynchronous rings, in the Proceedings of the IEEE International Conference on Distributed Computing Systems 691 – 694, 2001.
N. Mittal, P.K. Mohan, An efficient distributed Group mutual exclusion algorithm for non-uniform group access, In the Proceedings of the International Conference on Parallel and Distributed Computing Systems, 2005.
Q.E.K.Mamun, H.Nazakato, A new token based group mutual exclusion in distributed systems, In the proceedings of the Vth international Symposium on Parallel and distributed computing, 2006.
O.Thiare, M. Gueroui, and M.Naimi, Distributed mutual exclusion based on client/server model, In the proceedings of the VIIth international conference on parallel and distributed computing application and technologies (PDCAT 06), 2006.
Refbacks
- There are currently no refbacks.
Please send any question about this web site to info@praiseworthyprize.com
Copyright © 2005-2024 Praise Worthy Prize
