An optimal algorithm for mutual exclusion in computer networks

Subscribe (Full Service)


	Search: The ACM Digital Library The Guide

	Feedback

An optimal algorithm for mutual exclusion in computer networks

Full text

Pdf (752 KB)

Source

Communications of the ACM archive
Volume 24 , Issue 1 (January 1981) table of contents

Pages: 9 - 17

Year of Publication: 1981

ISSN:0001-0782

Authors

Glenn Ricart	National Institute of Health, Bethesda, MD
Ashok K. Agrawala	Univ. of Maryland, College Park

Publisher

ACM New York, NY, USA

Bibliometrics

Downloads (6 Weeks): 63, Downloads (12 Months): 288, Citation Count: 96

Additional Information:

references cited by index terms collaborative colleagues

Tools and Actions:	Request Permissions Review this Article Save this Article to a Binder Display Formats: BibTeX EndNote ACM Ref

DOI Bookmark:	Use this link to bookmark this Article: http://doi.acm.org/10.1145/358527.358537 What is a DOI?

REFERENCES

Note: OCR errors may be found in this Reference List extracted from the full text article. ACM has opted to expose the complete List rather than only correct and linked references.

	1	P. J. Courtois , F. Heymans , D. L. Parnas, Concurrent control with “readers” and “writers”, Communications of the ACM, v.14 n.10, p.667-668, Oct. 1971 [doi>10.1145/362759.362813]
	2	N. G. de Bruijn, Additional comments on a problem in concurrent programming control, Communications of the ACM, v.10 n.3, p.137-138, March 1967 [doi>10.1145/363162.363167]
	3	Dijkstra, E.W. Hierarchical ordering of sequential processes. Acta lnformatica 1, 2 (1971), 115-138.
	4	E. W. Dijkstra, Solution of a problem in concurrent programming control, Communications of the ACM, v.8 n.9, p.569, Sept. 1965 [doi>10.1145/365559.365617]
	5	Edsger W. Dijkstra, The structure of the “THE”-multiprogramming system, Communications of the ACM, v.11 n.5, p.341-346, May 1968 [doi>10.1145/363095.363143]
	6	Murray A. Eisenberg , Michael R. McGuire, Further comments on Dijkstra's concurrent programming control problem, Communications of the ACM, v.15 n.11, p.999, Nov. 1972 [doi>10.1145/355606.361895]
	7	J. Carver Hill, Synchronizing processors with memory-content-generated interrupts, Communications of the ACM, v.16 n.6, p.350-351, June 1973 [doi>10.1145/362248.364641]
	8	Donald E. Knuth, Additional comments on a problem in concurrent programming control, Communications of the ACM, v.9 n.5, p.321-322, May 1966 [doi>10.1145/355592.365595]
	9	Leslie Lamport, A new solution of Dijkstra's concurrent programming problem, Communications of the ACM, v.17 n.8, p.453-455, Aug. 1974 [doi>10.1145/361082.361093]
	10	Leslie Lamport, Time, clocks, and the ordering of events in a distributed system, Communications of the ACM, v.21 n.7, p.558-565, July 1978 [doi>10.1145/359545.359563]
	11	Lamport, L. Time, clocks and the ordering of events in a distributed system. Rep. CA-7603-2911, Mass. Comptr. Assoc., Wakefield, Mass. March 1976.
	12	Ricart, G., and Agrawala, A.K. Performance of a distributed network mutual exclusion algorithm. Tech. Rept. TR-774, Dept. Comptr. Sci., Univ. of Maryland, College Park, Md., March 1979.
	13	Ricart, G., and Agrawala, A.K. Using exact timing to implement mutual exclusion in a distributed network. Tech. Rept. TR-742, Dept. Comptr. Sci., Univ. of Maryland, College Park, Md. March 1979.

CITED BY 96

	V. Kumar , J. Place , G. -C. Yang, An Efficient Algorithm for Mutual Exclusion Using Queue Migration in Computer Networks, IEEE Transactions on Knowledge and Data Engineering, v.3 n.3, p.380-384, September 1991
	Fred B. Schneider, Synchronization in Distributed Programs, ACM Transactions on Programming Languages and Systems (TOPLAS), v.4 n.2, p.125-148, April 1982
	Mikhail Nesterenko , Masaaki Mizuno, A quorum-based self-stabilizing distributed mutual exclusion algorithm, Journal of Parallel and Distributed Computing, v.62 n.2, p.284-305, February 2002
	S. H. Son , J. L. Pfaltz, Reliability mechanisms for ADAMS, Proceedings of the third conference on Hypercube concurrent computers and applications, p.1390-1397, January 1989, Pasadena, California, United States
	Ichiro Suzuki , Tadao Kasami, A distributed mutual exclusion algorithm, ACM Transactions on Computer Systems (TOCS), v.3 n.4, p.344-349, Nov. 1985
	Aomar Maddi, Token based solutions to M resources allocation problem, Proceedings of the 1997 ACM symposium on Applied computing, p.340-344, April 1997, San Jose, California, United States
	D. Agrawal , A. El Abbadi, Efficient solution to the distributed mutual exclusion problem, Proceedings of the eighth annual ACM Symposium on Principles of distributed computing, p.193-200, June 1989, Edmonton, Alberta, Canada
	Hatem Sellami , Sudhakar Yalamanchili, Parallelism in sequential multiprocessor simulation models: a case study, ACM Transactions on Modeling and Computer Simulation (TOMACS), v.5 n.2, p.101-128, April 1995
	Ricardo Galli , Yuhua Luo, Mu3D: a causal consistency protocol for a collaborative VRML editor, Proceedings of the fifth symposium on Virtual reality modeling language (Web3D-VRML), p.53-62, February 20-24, 2000, Monterey, California, United States
	Guohong Cao , Mukesh Singhal, A Delay-Optimal Quorum-Based Mutual Exclusion Algorithm for Distributed Systems, IEEE Transactions on Parallel and Distributed Systems, v.12 n.12, p.1256-1268, December 2001
	Rajeev Chawla, A distributed mutual exclusion solution derived from real-life examples, Proceedings of the 30th annual Southeast regional conference, April 08-10, 1992, Raleigh, North Carolina
	W. K. Giloi , P. Behr, An IPC protocol and its hardware realization for a high-speed distributed multicomputer system, Proceedings of the 8th annual symposium on Computer Architecture, p.481-493, May 12-14, 1981, Minneapolis, Minnesota, United States
	Ravi Prakash , Niranjan G. Shivaratri , Mukesh Singhal, Distributed dynamic channel allocation for mobile computing, Proceedings of the fourteenth annual ACM symposium on Principles of distributed computing, p.47-56, August 20-23, 1995, Ottowa, Ontario, Canada
	Jason Gait, Semaphores outside the kernel, ACM SIGPLAN Notices, v.19 n.10, p.12-21, October 1984
	Phil Kearns , Jeffery E. Payne, Time-based performance evaluation of protocols for distributed systems: an alternative to message counting, Proceedings of the 22nd conference on Winter simulation, p.441-445, December 09-12, 1990, New Orleans, Louisiana, United States
	Gregory R. Andrews, Paradigms for process interaction in distributed programs, ACM Computing Surveys (CSUR), v.23 n.1, p.49-90, March 1991
	George S. Avrunin , Jack C. Wileden, Describing and analyzing distributed software system designs, ACM Transactions on Programming Languages and Systems (TOPLAS), v.7 n.3, p.380-403, July 1985
	Divyakant Agrawal , Amr El Abbadi, An efficient and fault-tolerant solution for distributed mutual exclusion, ACM Transactions on Computer Systems (TOCS), v.9 n.1, p.1-20, Feb. 1991
	Ernest Chang, Technical correspondence: on message passes in computer networks., Communications of the ACM, v.24 n.7, p.468, July 1981
	Anish Arora , Sandeep Kulkarni , Murat Demirbas, Resettable vector clocks, Proceedings of the nineteenth annual ACM symposium on Principles of distributed computing, p.269-278, July 16-19, 2000, Portland, Oregon, United States
	Brigitte Plateau, On the stochastic structure of parallelism and synchronization models for distributed algorithms, ACM SIGMETRICS Performance Evaluation Review, v.13 n.2, p.147-154, Aug. 1985
	Mamoru Maekawa, A N algorithm for mutual exclusion in decentralized systems, ACM Transactions on Computer Systems (TOCS), v.3 n.2, p.145-159, May 1985
	Malcolm Yoke Hean Low , David M. Nicol, Consistent modeling of distributed mutual exclusion protocol using optimistic simulation, Proceedings of the fifteenth workshop on Parallel and distributed simulation, p.137-144, May 15-18, 2001, Lake Arrowhead, California, United States
	S. H. Son, An Adaptive Checkpointing Scheme for Distributed Databases with Mixed Types of Transactions, IEEE Transactions on Knowledge and Data Engineering, v.1 n.4, p.450-458, December 1989
	S. Mishra , P. K. Srimani, A robust algorithm for mutual exclusion in a computer network, Proceedings of the 1987 Fall Joint Computer Conference on Exploring technology: today and tomorrow, p.335-342, December 1987, Dallas, Texas, United States
	Beverly A. Sanders, The information structure of distributed mutual exclusion algorithms, ACM Transactions on Computer Systems (TOCS), v.5 n.3, p.284-299, Aug. 1987
	Kerry Raymond, A tree-based algorithm for distributed mutual exclusion, ACM Transactions on Computer Systems (TOCS), v.7 n.1, p.61-77, Feb. 1989
	John M. Mellor-Crummey , Michael L. Scott, Algorithms for scalable synchronization on shared-memory multiprocessors, ACM Transactions on Computer Systems (TOCS), v.9 n.1, p.21-65, Feb. 1991
	Rainer Oechsle , Tim Gottwald, DisASTer (distributed algorithms simulation terrain): a platform for the implementation of distributed algorithms, Proceedings of the 10th annual SIGCSE conference on Innovation and technology in computer science education, June 27-29, 2005, Caparica, Portugal
	K. M. Chandy , J. Misra, The drinking philosophers problem, ACM Transactions on Programming Languages and Systems (TOPLAS), v.6 n.4, p.632-646, Oct. 1984
	C. S. Hsieh , R. A. Mata, Decentralized mutual exclusion in the presence of link failures, Proceedings of the 17th conference on ACM Annual Computer Science Conference, p.195-203, February 21-23, 1989, Louisville, Kentucky
	Boris Koldehofe , Marina Papatriantafilou , Philippas Tsigas, Distributed algorithms visualisation for educational purposes, ACM SIGCSE Bulletin, v.31 n.3, p.103-106, Sept. 1999
	Tai-Kuo Woo , Kenneth Block, A synchronization algorithm for distributed systems, Proceedings of the 19th annual conference on Computer Science, p.358-364, April 1991, San Antonio, Texas, United States
	R. L. N. Reddy , B. Gupta , Pradip K. Srimani, A new fault tolerant distributed mutual exclusion algorithm, Proceedings of the 1992 ACM/SIGAPP symposium on Applied computing: technological challenges of the 1990's, p.831-839, March 1992, Kansas City, Missouri, United States
	M. Singhal, A Dynamic Information-Structure Mutual Exclusion Algorithm for Distributed Systems, IEEE Transactions on Parallel and Distributed Systems, v.3 n.1, p.121-125, January 1992
	P. C. Saxena , J. Rai, A survey of permission-based distributed mutual exclusion algorithms, Computer Standards & Interfaces, v.25 n.2, p.159-181, May 2003
	Zhiming Zhao , Dick Van Albada , Peter Sloot, Agent-Based Flow Control for HLA Components, Simulation, v.81 n.7, p.487-501, July 2005
	Yuh-Jzer Joung, The congenial talking philosophers problem in computer networks, Distributed Computing, v.15 n.3, p.155-175, July 2002
	H. Kakugawa , S. Fujita , M. Yamashita , T. Ae, Availability of k-Coterie, IEEE Transactions on Computers, v.42 n.5, p.553-558, May 1993
	Kurt Schelfthout , Tom Holvoet, Coordination middleware for decentralized applications in dynamic networks, Proceedings of the 2nd international doctoral symposium on Middleware, p.1-5, November 28-December 02, 2005, Grenoble, France
	Dieter Zöbel, The Deadlock problem: a classifying bibliography, ACM SIGOPS Operating Systems Review, v.17 n.4, p.6-15, October 1983
	M. Benchaïba , A. Bouabdallah , N. Badache , M. Ahmed-Nacer, Distributed mutual exclusion algorithms in mobile ad hoc networks: an overview, ACM SIGOPS Operating Systems Review, v.38 n.1, p.74-89, January 2004
	J. Place, An algorithm based on queue migration for mutual exclusion in computer networks, Proceedings of the 17th conference on ACM Annual Computer Science Conference, p.103-108, February 21-23, 1989, Louisville, Kentucky
	Jianping Jiang , Ten-Hwang Lai , Neelam Soundarajan, On Distributed Dynamic Channel Allocation in Mobile Cellular Networks, IEEE Transactions on Parallel and Distributed Systems, v.13 n.10, p.1024-1037, October 2002
	O. S.F. Carvalho , G. Roucairol, On the distribution of an assertion, Proceedings of the first ACM SIGACT-SIGOPS symposium on Principles of distributed computing, p.121-131, August 18-20, 1982, Ottawa, Canada
	Ahmed Housni , Michel Trehel, A new distributed mutual exclusion algorithm for two groups, Proceedings of the 2001 ACM symposium on Applied computing, p.531-538, March 2001, Las Vegas, Nevada, United States
	Daniel A. Menascé , Yelena Yesha , Konstantinos Kalpakis, On a Unified Framework for the Evaluation of Distributed Quorum Attainment Protocols, IEEE Transactions on Software Engineering, v.20 n.11, p.868-884, November 1994
	Sang Hyuk Son , Ashok K. Agrawala, Distributed Checkpointing for Globally Consistent States of Databases, IEEE Transactions on Software Engineering, v.15 n.10, p.1157-1167, October 1989
	George S. Avrunin , Ugo A. Buy , James C. Corbett , Laura K. Dillon , Jack C. Wileden, Automated Analysis of Concurrent Systems with the Constrained Expression Toolset, IEEE Transactions on Software Engineering, v.17 n.11, p.1204-1222, November 1991
	J.-M. Hélary , A. Mostefaoui , M. Raynal, A General Scheme for Token- and Tree-Based Distributed Mutual Exclusion Algorithms, IEEE Transactions on Parallel and Distributed Systems, v.5 n.11, p.1185-1196, November 1994
	Mukesh Singhal, A Heuristically-Aided Algorithm for Mutual Exclusion in Distributed Systems, IEEE Transactions on Computers, v.38 n.5, p.651-662, May 1989
	Sandeep Lodha , Ajay Kshemkalyani, A Fair Distributed Mutual Exclusion Algorithm, IEEE Transactions on Parallel and Distributed Systems, v.11 n.6, p.537-549, June 2000
	G. Bernard , A. Duda , Y. Haddad , G. Harrus, Primitives for Distributed Computing in a Heterogeneous Local Area Network Environment, IEEE Transactions on Software Engineering, v.15 n.12, p.1567-1578, December 1989
	T. Soneoka , T. Ibaraki, Logically Instantaneous Message Passing in Asynchronous Distributed Systems, IEEE Transactions on Computers, v.43 n.5, p.513-527, May 1994
	Bugra Gedik , Ling Liu, A Scalable Peer-to-Peer Architecture for Distributed Information Monitoring Applications, IEEE Transactions on Computers, v.54 n.6, p.767-782, June 2005
	Michel Raynal , Mukesh Singhal, Logical Time: Capturing Causality in Distributed Systems, Computer, v.29 n.2, p.49-56, February 1996
	Divyakant Agrawal , Ömer Eğecioǧlu , Amr El Abbadi, Analysis of Quorum-Based Protocols for Distributed (k + 1)-Exclusion, IEEE Transactions on Parallel and Distributed Systems, v.8 n.5, p.533-537, May 1997
	Ahuva Tikvati , Mordechai Ben-Ari , Yifat Ben-David Kolikant, Virtual trees for the byzantine generals algorithm, ACM SIGCSE Bulletin, v.36 n.1, March 2004
	Min-You Wu , Wei Shu, Note: an efficient distributed token-based mutual exclusion algorithm with central coordinator, Journal of Parallel and Distributed Computing, v.62 n.10, p.1602-1613, October 2002
	Yuh-Jzer Joung, Quorum-Based Algorithms for Group Mutual Exclusion, IEEE Transactions on Parallel and Distributed Systems, v.14 n.5, p.463-476, May 2003
	Roberto Baldoni , Bruno Ciciani, A class of high performance Maekawa-type algorithms for distributed systems under heavy demand, Distributed Computing, v.8 n.4, p.171-180, June 1995
	Sujatha Kashyap , Vijay K. Garg, Exploiting predicate structure for efficient reachability detection, Proceedings of the 20th IEEE/ACM international Conference on Automated software engineering, November 07-11, 2005, Long Beach, CA, USA
	Kurt Schelfthout , Danny Weyns , Tom Holvoet, Middleware for protocol-based coordination in dynamic networks, Proceedings of the 3rd international workshop on Middleware for pervasive and ad-hoc computing, p.1-8, November 28-December 02, 2005, Grenoble, France
	Marin Bertier , Luciana Arantes , Pierre Sens, Distributed mutual exclusion algorithms for grid applications: a hierarchical approach, Journal of Parallel and Distributed Computing, v.66 n.1, p.128-144, January 2006
	Anish Arora , Sandeep S. Kulkarni , Murat Demirbas, Resettable vector clocks, Journal of Parallel and Distributed Computing, v.66 n.2, p.221-237, February 2006
	S. Nishio , K. F. Li , E. G. Manning, A Resilient Mutual Exclusion Algorithm for Computer Networks, IEEE Transactions on Parallel and Distributed Systems, v.1 n.3, p.344-356, July 1990
	Jehn-Ruey Jiang , Shing-Tsaan Huang , Yu-Chen Kuo, Cohorts Structures for Fault-Tolerant k Entries to a Critical Section, IEEE Transactions on Computers, v.46 n.2, p.222-228, February 1997
	Sampath Rangarajan , Sanjeev Setia , Satish K. Tripathi, A Fault-Tolerant Algorithm for Replicated Data Management, IEEE Transactions on Parallel and Distributed Systems, v.6 n.12, p.1271-1282, December 1995
	Anish Arora , Mikhail Nesterenko, Unifying stabilization and termination in message-passing systems, Distributed Computing, v.17 n.3, p.279-290, March 2005
	Kris Luyten , Kristof Verpoorten , Karin Coninx, Ad-hoc co-located collaborative work with mobile devices, Proceedings of the 9th international conference on Human computer interaction with mobile devices and services, p.507-514, September 09-12, 2007, Singapore
	Glenn Ricart, technical correspondence: on message passes in computer networks. author's response, Communications of the ACM, v.24 n.7, p.468-469, July 1981
	Michel Raynal, A simple taxonomy for distributed mutual exclusion algorithms, ACM SIGOPS Operating Systems Review, v.25 n.2, p.47-50, April 1991
	Moharram Challenger , Vahid Khalilpour , Peyman Bayat , Mohammad Reza Meibodi, A new robust centralized DMX algorithm, Proceedings of the 25th conference on Proceedings of the 25th IASTED International Multi-Conference: parallel and distributed computing and networks, p.367-374, February 13-15, 2007, Innsbruck, Austria
	Neeraj Mittal , Prajwal K. Mohan, A priority-based distributed group mutual exclusion algorithm when group access is non-uniform, Journal of Parallel and Distributed Computing, v.67 n.7, p.797-815, July, 2007
	M. Muhammad , A. S. Cheema , I. Gupta, Efficient Mutual Exclusion in Peer-to-Peer Systems, Proceedings of the 6th IEEE/ACM International Workshop on Grid Computing, p.296-299, November 13-14, 2005
	Samuel Grier, Early projects using Ada at the United States Air Force Academy, ACM SIGAda Ada Letters, v.XVIII n.1, p.92-109, Jan./Feb. 1998
	Ye-In Chang , Yao-Jen Chang, A fault-tolerant dynamic triangular mesh protocol for distributed mutual exclusion, ACM SIGOPS Operating Systems Review, v.31 n.3, p.29-44, July 1997
	Peter J. Denning, Technical Correspondence, Communications of the ACM, v.26 n.2, p.146-149, Feb. 1983
	Mohamed Naimi, Distributed mutual exclusion on hypercubes, ACM SIGOPS Operating Systems Review, v.30 n.3, p.46-51, July 1996
	Mohamed Naimi, Distributed algorithm for K-entries to critical section based on the directed graphs, ACM SIGOPS Operating Systems Review, v.27 n.4, p.67-75, Oct. 1993
	Abdelmadjid Bouabdallah, On mutual exclusion in faulty distributed systems, ACM SIGOPS Operating Systems Review, v.28 n.1, p.80-87, Jan. 1994
	Chyi-Ren Dow , Jong-Shin Chen , Yi-Hsung Li, An Adaptive and Fault-Tolerant Channel Set Allocation Algorithm for Microcell/Macrocell Cellular Networks, Wireless Personal Communications: An International Journal, v.33 n.2, p.197-212, April 2005
	N. Plouzeau , M. Raynal, Elements for a course on the design of distributed algorithms, ACM SIGCSE Bulletin, v.24 n.2, p.35-40, June 1992
	Michel Raynal, About logical clocks for distributed systems, ACM SIGOPS Operating Systems Review, v.26 n.1, p.41-48, Jan. 1992
	P. Kearns , M. Freeman, CCAL: an interpreted language for experimentation in concurrent control, ACM SIGPLAN Notices, v.22 n.7, p.283-291, July 1987
	Andrzej Goscinski , Mirion Bearman, Resource management in large distributed systems, ACM SIGOPS Operating Systems Review, v.24 n.4, p.7-25, Oct. 1990
	Yu Lei , Richard H. Carver, Reachability Testing of Concurrent Programs, IEEE Transactions on Software Engineering, v.32 n.6, p.382-403, June 2006
	Anup Kumar Bandyopadhyay, Weakest precondition based verification tool that models spatial ordering, ACM SIGSOFT Software Engineering Notes, v.33 n.2, March 2008
	Weigang Wu , Jiannong Cao , Jin Yang, A fault tolerant mutual exclusion algorithm for mobile ad hoc networks, Pervasive and Mobile Computing, v.4 n.1, p.139-160, February, 2008
	Pranay Chaudhuri , Thomas Edward, An algorithm for k-mutual exclusion in decentralized systems, Computer Communications, v.31 n.14, p.3223-3235, September, 2008
	Min Li , Shuming Gao , J. Y. H. Fuh , Y. F. Zhang, Replicated concurrency control for collaborative feature modelling: A fine granular approach, Computers in Industry, v.59 n.9, p.873-881, December, 2008
	Abdelouahid Derhab , Nadjib Badache, A distributed mutual exclusion algorithm over multi-routing protocol for mobile ad hoc networks, International Journal of Parallel, Emergent and Distributed Systems, v.23 n.3, p.197-218, June 2008
	Ranganath Atreya , Neeraj Mittal , Sathya Peri, A Quorum-Based Group Mutual Exclusion Algorithm for a Distributed System with Dynamic Group Set, IEEE Transactions on Parallel and Distributed Systems, v.18 n.10, p.1345-1360, October 2007
	Julien Sopena , Luciana Arantes , Fabrice Legond-Aubry , Pierre Sens, Building effective mutual exclusion services for grids, The Journal of Supercomputing, v.49 n.1, p.84-107, July 2009
	Chih-Min Chao , Jang-Ping Sheu , I-Cheng Chou, An Adaptive Quorum-Based Energy Conserving Protocol for IEEE 802.11 Ad Hoc Networks, IEEE Transactions on Mobile Computing, v.5 n.5, p.560-570, May 2006
	Mansi Ramakrishnan Thoppian , Ravi Prakash, A Distributed Protocol for Dynamic Address Assignment in Mobile Ad Hoc Networks, IEEE Transactions on Mobile Computing, v.5 n.1, p.4-19, January 2006