The mutual exclusion problem

Subscribe (Full Service)


	Search: The ACM Digital Library The Guide

	Feedback

The mutual exclusion problem: partII—statement and solutions

Full text

Pdf (1.83 MB)

Source

Journal of the ACM (JACM) archive
Volume 33 , Issue 2 (April 1986) table of contents

Pages: 327 - 348

Year of Publication: 1986

ISSN:0004-5411

Author

Leslie Lamport

Digital Equipment Corp., Palo Alto, CA

Publisher

ACM New York, NY, USA

Bibliometrics

Downloads (6 Weeks): 19, Downloads (12 Months): 97, Citation Count: 46

Additional Information:

abstract references cited by index terms review 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/5383.5385 What is a DOI?

ABSTRACT

The theory developed in Part I is used to state the mutual exclusion problem and several additional fairness and failure-tolerance requirements. Four “distributed” N-process solutions are given, ranging from a solution requiring only one communication bit per process that permits individual starvation, to one requiring about N! communication bits per process that satisfies every reasonable fairness and failure-tolerance requirement that we can conceive of.

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	Per Brinch Hansen, Concurrent Programming Concepts, ACM Computing Surveys (CSUR), v.5 n.4, p.223-245, Dec. 1973 [doi>10.1145/356622.356624]
	1a	James E. Burns, Mutual exclusion with linear waiting using binary shared variables, ACM SIGACT News, v.10 n.2, Summer 1978 [doi>10.1145/990524.990527]
	2	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]
	3	Edsger W. Dijkstra, Self-stabilizing systems in spite of distributed control, Communications of the ACM, v.17 n.11, p.643-644, Nov. 1974 [doi>10.1145/361179.361202]
	4	FISCHER, M. J., LYNCH, N., BURNS, J. E., AND BORODIN, A. Resource allocation with immunity to limited processing failure. In Proceedings of the 20th IEEE Symposium on the Foundations of Computer Science (Oct.). IEEE, New York, 1979, pp. 234-254.
	5	Howard P. Katseff, A new solution to the critical section problem, Proceedings of the tenth annual ACM symposium on Theory of computing, p.86-88, May 01-03, 1978, San Diego, California, United States [doi>10.1145/800133.804335]
	6	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]
	7	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]
	8	LAMPORT, L. The synchronization of independent processes. Acta Inf. 7, 1 (1976), 15-34.
	9	LAMPORT, L. Proving the correctness of multiprocess programs. IEEE Trans. Softw. Eng. SE-3, 2 (Mar. 1977), 125-143.
	10	LAMPORT, L. The implementation of reliable distributed multiprocess systems. Comput. Netw. 2 (1978), 95-114.
	11	LAMPORT, L. The 'Hoare logic' of concurrent programs. Acta Inf. 14, l (1980), 21-37.
	12	Leslie Lamport, Reasoning about nonatomic operations, Proceedings of the 10th ACM SIGACT-SIGPLAN symposium on Principles of programming languages, p.28-37, January 24-26, 1983, Austin, Texas [doi>10.1145/567067.567072]
	13	Leslie Lamport, Specifying Concurrent Program Modules, ACM Transactions on Programming Languages and Systems (TOPLAS), v.5 n.2, p.190-222, April 1983 [doi>10.1145/69624.357207]
	14	LAMPORT, L. What good is temporal logic? In Information Processing 83: Proceedings of the IFIP 9th World Congress (Paris, Sept. 19-23). R. E. A. Mason, Ed. North Holland, Amsterdam, 1983.
	15	Leslie Lamport, The mutual exclusion problem: part I—a theory of interprocess communication, Journal of the ACM (JACM), v.33 n.2, p.313-326, April 1986 [doi>10.1145/5383.5384]
	16	Susan Owicki , Leslie Lamport, Proving Liveness Properties of Concurrent Programs, ACM Transactions on Programming Languages and Systems (TOPLAS), v.4 n.3, p.455-495, July 1982 [doi>10.1145/357172.357178]
	17	Gary L. Peterson, A New Solution to Lamport's Concurrent Programming Problem Using Small Shared Variables, ACM Transactions on Programming Languages and Systems (TOPLAS), v.5 n.1, p.56-65, Jan. 1983 [doi>10.1145/357195.357199]
	18	Gary L. Peterson , Michael J. Fischer, Economical solutions for the critical section problem in a distributed system (Extended Abstract), Proceedings of the ninth annual ACM symposium on Theory of computing, p.91-97, May 04-04, 1977, Boulder, Colorado, United States [doi>10.1145/800105.803398]
	19	RAa}N, M. The choice coordination problem. Acta Inf. 17, (1982), 121-134.
	20	RIVEST, R. L., AND PRATT, V. R. The mutual exclusion problem for unreliable processes: Preliminary report. In Proceedings of the IEEE Symposium on the Foundation of Computer Science. IEEE, New York, 1976, pp. 1-8.

CITED BY 46

	Shlomi Dolev , Jennifer L. Welch, Wait-free clock synchronization, Proceedings of the twelfth annual ACM symposium on Principles of distributed computing, p.97-108, August 15-18, 1993, Ithaca, New York, United States
	D. Dolev , N. Shavit, Bounded concurrrent time-stamp systems are constructible, Proceedings of the twenty-first annual ACM symposium on Theory of computing, p.454-466, May 14-17, 1989, Seattle, Washington, United States
	H. Attiya , D. Dolev , N. Shavit, Bounded polynomial randomized consensus, Proceedings of the eighth annual ACM Symposium on Principles of distributed computing, p.281-293, June 1989, Edmonton, Alberta, Canada
	Yehuda Afek , Danny Dolev , Hagit Attiya , Eli Gafni , Michael Merritt , Nir Shavit, Atomic snapshots of shared memory, Proceedings of the ninth annual ACM symposium on Principles of distributed computing, p.1-13, August 22-24, 1990, Quebec City, Quebec, Canada
	Michael J. Fischer , Nancy A. Lynch , James E. Burns , Allan Borodin, Distributed FIFO allocation of identical resources using small shared space, ACM Transactions on Programming Languages and Systems (TOPLAS), v.11 n.1, p.90-114, Jan. 1989
	Marco Schneider, Self-stabilization, ACM Computing Surveys (CSUR), v.25 n.1, p.45-67, March 1993
	James H. Anderson, Lamport on mutual exclusion: 27 years of planting seeds, Proceedings of the twentieth annual ACM symposium on Principles of distributed computing, p.3-12, August 2001, Newport, Rhode Island, United States
	Leslie Lamport, The mutual exclusion problem: part I—a theory of interprocess communication, Journal of the ACM (JACM), v.33 n.2, p.313-326, April 1986
	Patrick Keane , Mark Moir, A simple local-spin group mutual exclusion algorithm, Proceedings of the eighteenth annual ACM symposium on Principles of distributed computing, p.23-32, May 04-06, 1999, Atlanta, Georgia, United States
	M. J. Fischer , S. Moran , R. Rudich , G. Taubenfeld, The wakeup problem, Proceedings of the twenty-second annual ACM symposium on Theory of computing, p.106-116, May 13-17, 1990, Baltimore, Maryland, United States
	Shlomi Dolev , Amos Israeli , Shlomo Moran, Resource bounds for self stabilizing message driven protocols, Proceedings of the tenth annual ACM symposium on Principles of distributed computing, p.281-293, August 19-21, 1991, Montreal, Quebec, Canada
	Ajei S. Gopal , Kenneth J. Perry, Unifying self-stabilization and fault-tolerance, Proceedings of the twelfth annual ACM symposium on Principles of distributed computing, p.195-206, August 15-18, 1993, Ithaca, New York, United States
	Uri Abraham , Shlomi Dolev , Ted Herman , Irit Koll, Self-stabilizing l-exclusion, Theoretical Computer Science, v.266 n.1-2, p.653-692, 09/06/2001
	Hagit Brit , Shlomo Moran, Wait-freedom vs. bounded wait-freedom in public data structures (extended abstract), Proceedings of the thirteenth annual ACM symposium on Principles of distributed computing, p.52-60, August 14-17, 1994, Los Angeles, California, United States
	Walter Vogler, Efficiency of asynchronous systems, read arcs, and the MUTEX-problem, Theoretical Computer Science, v.275 n.1-2, p.589-631, March 28 2002
	Danny Dolev , Eli Gafni , Nir Shavit, Toward a non-atomic era: l-exclusion as a test case, Proceedings of the twentieth annual ACM symposium on Theory of computing, p.78-92, May 02-04, 1988, Chicago, Illinois, United States
	Frank D. Anger, On Lamport's interprocessor communication model, ACM Transactions on Programming Languages and Systems (TOPLAS), v.11 n.3, p.404-417, July 1989
	Mikhail Nesterenko , Anish Arora, Stabilization-preserving atomicity refinement, Journal of Parallel and Distributed Computing, v.62 n.5, p.766-791, May 2002
	Yehuda Afek , Danny Dolev , Eli Gafni , Michael Merritt , Nir Shavit, A bounded first-in, first-enabled solution to the l-exclusion problem, ACM Transactions on Programming Languages and Systems (TOPLAS), v.16 n.3, p.939-953, May 1994
	James H. Anderson , Yong-Jik Kim, Nonatomic mutual exclusion with local spinning, Proceedings of the twenty-first annual symposium on Principles of distributed computing, July 21-24, 2002, Monterey, California
	Patrick Keane , Mark Moir, A Simple Local-Spin Group Mutual Exclusion Algorithm, IEEE Transactions on Parallel and Distributed Systems, v.12 n.7, p.673-685, July 2001
	Shlomi Dolev , Amos Israeli , Shlomo Moran, Uniform Dynamic Self-Stabilizing Leader Election, IEEE Transactions on Parallel and Distributed Systems, v.8 n.4, p.424-440, April 1997
	B. Kao , H. Garcia-Molina , D. Barbará, Aggressive Transmissions of Short Messages Over Redundant Paths, IEEE Transactions on Parallel and Distributed Systems, v.5 n.1, p.102-109, January 1994
	Prasad Jayanti , Srdjan Petrovic , King Tan, Fair group mutual exclusion, Proceedings of the twenty-second annual symposium on Principles of distributed computing, p.275-284, July 13-16, 2003, Boston, Massachusetts
	James H. Anderson , Yong-Jik Kim , Ted Herman, Shared-memory mutual exclusion: major research trends since 1986, Distributed Computing, v.16 n.2-3, p.75-110, September 2003
	Faith Fich , Eric Ruppert, Hundreds of impossibility results for distributed computing, Distributed Computing, v.16 n.2-3, p.121-163, September 2003
	Mohamed G. Gouda , Nicholas J. Multari, Stabilizing Communication Protocols, IEEE Transactions on Computers, v.40 n.4, p.448-458, April 1991
	Shmuel Katz , Kenneth Perry, Self-stabilizing extensions for message-passing systems, Proceedings of the ninth annual ACM symposium on Principles of distributed computing, p.91-101, August 22-24, 1990, Quebec City, Quebec, Canada
	Yehuda Afek , Hagit Attiya , Danny Dolev , Eli Gafni , Michael Merritt , Nir Shavit, Atomic snapshots of shared memory, Journal of the ACM (JACM), v.40 n.4, p.873-890, Sept. 1993
	Takashi Suezawa, Persistent execution state of a Java virtual machine, Proceedings of the ACM 2000 conference on Java Grande, p.160-167, June 03-04, 2000, San Francisco, California, United States
	G. M. Karam , C. M. Stanczyk , G. W. Bond, Critical Races in Ada Programs, IEEE Transactions on Software Engineering, v.15 n.11, p.1471-1480, November 1989
	Shlomi Dolev , Amos Israeli , Shlomo Moran, Analyzing Expected Time by Scheduler-Luck Games, IEEE Transactions on Software Engineering, v.21 n.5, p.429-439, May 1995
	Amos Israeli , Ming Li, Bounded time-stamps, Distributed Computing, v.6 n.4, p.205-209, July 1993
	Shlomi Dolev , Frank Stomp, Safety assurance via on-line monitoring, Distributed Computing, v.16 n.4, p.269-277, December 2003
	Yehuda Afek , Geoffrey M. Brown, Self-stabilization over unreliable communication media, Distributed Computing, v.7 n.1, p.27-34, November 1993
	Srdjan Petrovic, Space-efficient FCFS group mutual exclusion, Information Processing Letters, v.95 n.2, p.343-350, 31 July 2005
	Leslie Lamport, How to Make a Correct Multiprocess Program Execute Correctly on a Multiprocessor, IEEE Transactions on Computers, v.46 n.7, p.779-782, July 1997
	James E. Burns , Mohamed G. Gouda , Raymond E. Miller, Stabilization and pseudo-stabilization, Distributed Computing, v.7 n.1, p.35-42, November 1993
	Shmuel Katz , Kenneth J. Perry, Self-stabilizing extensions for message-passing systems, Distributed Computing, v.7 n.1, p.17-26, November 1993
	Geoffrey M. Brown , Mohamed G. Gouda , Chuan-Lin Wu, Token Systems That Self-Stabilize, IEEE Transactions on Computers, v.38 n.6, p.845-852, June 1989
	Lisa Higham , Lillanne Jackson , Jalal Kawash, Specifying memory consistency of write buffer multiprocessors, ACM Transactions on Computer Systems (TOCS), v.25 n.1, p.1-es, February 2007
	Rohit Khare , Richard N. Taylor, Extending the Representational State Transfer (REST) Architectural Style for Decentralized Systems, Proceedings of the 26th International Conference on Software Engineering, p.428-437, May 23-28, 2004
	Fang-Chang Lin , Jane Yung-Jen Hsu, Cooperation Protocols in Multi-Agent Robotic Systems, Autonomous Robots, v.4 n.2, p.175-198, May 1997
	Alain Bui, On optimization of continuous-time Markov networks in distributed computing, Journal of Global Optimization, v.15 n.4, p.299-314, December 1999
	Rachid Guerraoui , Michal Kapalka, The semantics of progress in lock-based transactional memory, Proceedings of the 36th annual ACM SIGPLAN-SIGACT symposium on Principles of programming languages, January 21-23, 2009, Savannah, GA, USA
	Michal Armoni , Mordechai Ben-Ari, The concept of nondeterminism: its development and implications for teaching, ACM SIGCSE Bulletin, v.41 n.2, June 2009

INDEX TERMS

Primary Classification:
D. Software
D.4 OPERATING SYSTEMS
D.4.1 Process Management
Subjects: Mutual exclusion

General Terms:
Algorithms, Design, Performance, Reliability, Theory, Verification

REVIEW

"Neal Stanley Coulter : Reviewer","M. K. Solomon : Reviewer"

.abstract The theory developed in Part I is used to state the mutual exclusion problem and several additional fairness and failure-tolerance requirements. Four “distributed” N-process solutions are given, ranging from a so more...

Collaborative Colleagues:

Leslie Lamport: colleagues

Adobe Acrobat

QuickTime

Windows Media Player

Real Player