A new solution of Dijkstra's concurrent programming problem

Subscribe (Full Service)


	Search: The ACM Digital Library The Guide

	Feedback

A new solution of Dijkstra's concurrent programming problem

Full text

Pdf (312 KB)

Source

Communications of the ACM archive
Volume 17 , Issue 8 (August 1974) table of contents

Pages: 453 - 455

Year of Publication: 1974

ISSN:0001-0782

Author

Leslie Lamport

Massachusetts Computer Associates, Wakefield

Publisher

ACM New York, NY, USA

Bibliometrics

Downloads (6 Weeks): 16, Downloads (12 Months): 145, Citation Count: 97

Additional Information:

abstract 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/361082.361093 What is a DOI?

ABSTRACT

A simple solution to the mutual exclusion problem is presented which allows the system to continue to operate despite the failure of any individual component.

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	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]
	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	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]
	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]

CITED BY 98

	Vassos Hadzilacos, A note on group mutual exclusion, Proceedings of the twentieth annual ACM symposium on Principles of distributed computing, p.100-106, August 2001, Newport, Rhode Island, United States
	Allan Gottlieb , Boris D. Lubachevsky , Larry Rudolph, Basic Techniques for the Efficient Coordination of Very Large Numbers of Cooperating Sequential Processors, ACM Transactions on Programming Languages and Systems (TOPLAS), v.5 n.2, p.164-189, April 1983
	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
	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
	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
	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
	Jeffrey M. Jaffe, Decentralized Simulation of Resource Managers, Journal of the ACM (JACM), v.30 n.2, p.300-322, April 1983
	Leslie Lamport, Concurrent reading and writing, Communications of the ACM, v.20 n.11, p.806-811, Nov. 1977
	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
	Bard Bloom, Constructing two-writer atomic registers, Proceedings of the sixth annual ACM Symposium on Principles of distributed computing, p.249-259, August 10-12, 1987, Vancouver, British Columbia, Canada
	Bob Beck , Bob Kasten , Shreekant Thakkar, VLSI assist for a multiprocessor, ACM SIGARCH Computer Architecture News, v.15 n.5, p.10-20, Oct. 1987
	Guy E. Blelloch , Perry Cheng , Phillip B. Gibbons, Room synchronizations, Proceedings of the thirteenth annual ACM symposium on Parallel algorithms and architectures, p.122-133, July 2001, Crete Island, Greece
	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
	Janice M. Stone, A simple and correct shared-queue algorithm using compare-and-swap, Proceedings of the 1990 conference on Supercomputing, p.495-504, October 1990, New York, New York, United States
	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
	Richard Newman-Wolfe, A protocol for wait-free, atomic, multi-reader shared variables, Proceedings of the sixth annual ACM Symposium on Principles of distributed computing, p.232-248, August 10-12, 1987, Vancouver, British Columbia, Canada
	Sibsankar Haldar , Paul Vitányi, Bounded concurrent timestamp systems using vector clocks, Journal of the ACM (JACM), v.49 n.1, p.101-126, January 2002
	Leslie Lamport, The mutual exclusion problem: partII—statement and solutions, Journal of the ACM (JACM), v.33 n.2, p.327-348, April 1986
	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
	Manhoi Choy , Ambuj K. Singh, Efficient fault-tolerant algorithms for distributed resource allocation, ACM Transactions on Programming Languages and Systems (TOPLAS), v.17 n.3, p.535-559, May 1995
	Leslie Lamport, The mutual exclusion problem has been solved, Communications of the ACM, v.34 n.1, p.110-ff., Jan. 1991
	Yehuda Afek , David S. Greenberg , Michael Merritt , Gadi Taubenfeld, Computing with faulty shared objects, Journal of the ACM (JACM), v.42 n.6, p.1231-1274, Nov. 1995
	Ernst-Rüdiger Olderog , Krzysztof R. Apt, Fairness in parallel programs: the transformational approach, ACM Transactions on Programming Languages and Systems (TOPLAS), v.10 n.3, p.420-455, July 1988
	John M. Mellor-Crummey , Michael L. Scott, Scalable reader-writer synchronization for shared-memory multiprocessors, ACM SIGPLAN Notices, v.26 n.7, p.106-113, July 1991
	John Rushby, Theorem proving for verification, Modeling and verification of parallel processes, Springer-Verlag New York, Inc., New York, NY, 2001
	Hagit Attiya , Vita Bortnikov, Adaptive and efficient mutual exclusion (extended abstract), Proceedings of the nineteenth annual ACM symposium on Principles of distributed computing, p.91-100, July 16-19, 2000, Portland, Oregon, United States
	Leslie Lamport, A New Approach to Proving the Correctness of Multiprocess Programs, ACM Transactions on Programming Languages and Systems (TOPLAS), v.1 n.1, p.84-97, July 1979
	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
	Hagit Attiya , Roy Friedman, Programming DEC-Alpha based multiprocessors the easy way (extended abstract), Proceedings of the sixth annual ACM symposium on Parallel algorithms and architectures, p.157-166, June 27-29, 1994, Cape May, New Jersey, United States
	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
	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
	James Aspnes , Maurice Herlihy , Nir Shavit, Counting networks and multi-processor coordination, Proceedings of the twenty-third annual ACM symposium on Theory of computing, p.348-358, May 05-08, 1991, New Orleans, Louisiana, United States
	Edward A. Lycklama , Vassos Hadzilacos, A first-come-first-served mutual-exclusion algorithm with small communication variables, ACM Transactions on Programming Languages and Systems (TOPLAS), v.13 n.4, p.558-576, Oct. 1991
	C. William Higginbotham , Ralph Morelli, A system for teaching concurrent programming, ACM SIGCSE Bulletin, v.23 n.1, p.309-316, Mar. 1991
	Richard E. Ladner, The complexity of problems in systems of communicating sequential processes (Extended Abstract), Proceedings of the eleventh annual ACM symposium on Theory of computing, p.214-223, April 30-May 02, 1979, Atlanta, Georgia, United States
	Manhoi Choy , Ambuj K. Singh, Adaptive solutions to the mutual exclusion problem, Proceedings of the twelfth annual ACM symposium on Principles of distributed computing, p.183-194, August 15-18, 1993, Ithaca, New York, United States
	Leslie Lamport, win and sin: predicate transformers for concurrency, ACM Transactions on Programming Languages and Systems (TOPLAS), v.12 n.3, p.396-428, July 1990
	Irene Greif, A language for formal problem specification, Communications of the ACM, v.20 n.12, p.931-935, Dec. 1977
	James E. Burns , Paul Jackson , Nancy A. Lynch , Michael J. Fischer , Gary L. Peterson, Data Requirements for Implementation of N-Process Mutual Exclusion Using a Single Shared Variable, Journal of the ACM (JACM), v.29 n.1, p.183-205, Jan. 1982
	Mustaque Ahamad , Rida A. Bazzi , Ranjit John , Prince Kohli , Gil Neiger, The power of processor consistency, Proceedings of the fifth annual ACM symposium on Parallel algorithms and architectures, p.251-260, June 30-July 02, 1993, Velen, Germany
	Hagit Attiya , Vita Bortnikov, Adaptive and efficient mutual exclusion, Distributed Computing, v.15 n.3, p.177-189, July 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
	H. F. Tibbals, A structure for interprocess communication in a data communications handler, Proceedings of the annual conference, p.356-360, October 20-22, 1976, Houston, Texas, United States
	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
	Prasad Jayanti, Adaptive and efficient abortable mutual exclusion, Proceedings of the twenty-second annual symposium on Principles of distributed computing, p.295-304, July 13-16, 2003, Boston, Massachusetts
	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
	Uri Abraham, Self-stabilizing timestamps, Theoretical Computer Science, v.308 n.1-3, p.449-515, 3 November 2003
	Henny B. Sipma , Tomás E. Uribe , Zohar Manna, Deductive Model Checking, Formal Methods in System Design, v.15 n.1, p.49-74, July 1999
	Faith Fich , Eric Ruppert, Hundreds of impossibility results for distributed computing, Distributed Computing, v.16 n.2-3, p.121-163, September 2003
	Marcos K. Aguilera, A pleasant stroll through the land of infinitely many creatures, ACM SIGACT News, v.35 n.2, June 2004
	S. Aggarwal , D. Barbaŕ , K. Z. Meth, A Software Environment for the Specification and Analysis of Problems of Coordination and Concurrency, IEEE Transactions on Software Engineering, v.14 n.3, p.280-290, March 1988
	Saddek Bensalem , Yassine Lakhnech, Automatic Generation of Invariants, Formal Methods in System Design, v.15 n.1, p.75-92, July 1999
	Gerald Belpaire, Synchronization: Is a synthesis of the problems possible?, ACM SIGOPS Operating Systems Review, v.9 n.3, p.3-10, July 1975
	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
	Michel Dubois , Christoph Scheurich, Memory Access Dependencies in Shared-Memory Multiprocessors, IEEE Transactions on Software Engineering, v.16 n.6, p.660-673, June 1990
	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
	Holger Opderbeck, Problems in the design of control procedures for computer networks, ACM SIGCOMM Computer Communication Review, v.5 n.2, p.1-8, April 1975
	Thomas A. Henzinger , Rupak Majumdar , Jean-François Raskin, A classification of symbolic transition systems, ACM Transactions on Computational Logic (TOCL), v.6 n.1, p.1-32, January 2005
	Paul Z. Kolano, Proof assistance for real-time systems using an interactive theorem prover, Theoretical Computer Science, v.282 n.1, p.53-99, June 7, 2002
	Amos Israeli , Ming Li, Bounded time-stamps, Distributed Computing, v.6 n.4, p.205-209, July 1993
	Carole Delporte-Gallet , Hugues Fauconnier , Rachid Guerraoui , Petr Kouznetsov, Mutual exclusion in asynchronous systems with failure detectors, Journal of Parallel and Distributed Computing, v.65 n.4, p.492-505, April 2005
	Prasad Jayanti, f-arrays: implementation and applications, Proceedings of the twenty-first annual symposium on Principles of distributed computing, July 21-24, 2002, Monterey, California
	William N. Scherer, III , Doug Lea , Michael L. Scott, Scalable synchronous queues, Proceedings of the eleventh ACM SIGPLAN symposium on Principles and practice of parallel programming, March 29-31, 2006, New York, New York, USA
	Manhoi Choy , Ambuj K. Singh, Adaptive solutions to the mutual exclusion problem, Distributed Computing, v.8 n.1, p.1-17, August 1994
	Ajoy K. Datta , Maria Gradinariu , Michel Raynal, Stabilizing mobile philosophers, Information Processing Letters, v.95 n.1, p.299-306, 16 July 2005
	Maurice Herlihy , Nir Shavit , Orli Waarts, Linearizable counting networks, Distributed Computing, v.9 n.4, p.193-203, February 1996
	H. Neil Singleton , Ronnie G. Ward, Lamport's algorithm reconsidered, Proceedings of the ACM '82 conference, p.182-185, January 1982
	Paul Z. Kolano , Richard A. Demmerer, Classification schemes to aid in the analysis of real-time systems, ACM SIGSOFT Software Engineering Notes, v.25 n.5, p.86-95, Sept. 2000
	B. K. Szymanski, A simple solution to Lamport's concurrent programming problem with linear wait, Proceedings of the 2nd international conference on Supercomputing, p.621-626, June 1988, St. Malo, France
	Glenn Ricart , Ashok K. Agrawala, An optimal algorithm for mutual exclusion in computer networks, Communications of the ACM, v.24 n.1, p.9-17, Jan. 1981
	R. Janvier , Y. Lakhnech , M. Périn, Certifying cryptographic protocols by abstract model-checking and proof concretization, ACM SIGBED Review, v.3 n.4, p.37-57, October 2006
	Vladan Bozic, Application of finite state automata to the bakery algorithm in critical section modeling, ACM SIGCSE Bulletin, v.38 n.3, September 2006
	Phuong Hoai Ha , Marina Papatriantafilou , Philippas Tsigas, Efficient self-tuning spin-locks using competitive analysis, Journal of Systems and Software, v.80 n.7, p.1077-1090, July, 2007
	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
	Leslie Lamport, What it means for a concurrent program to satisfy a specification: why no one has specified priority, Proceedings of the 12th ACM SIGACT-SIGPLAN symposium on Principles of programming languages, p.78-83, January 14-16, 1985, New Orleans, Louisiana, United States
	Nikolaj S. Bjørner , Anca Browne , Michael A. Colón , Bernd Finkbeiner , Zohar Manna , Henny B. Sipma , Tomás E. Uribe, Verifying Temporal Properties of Reactive Systems: A STeP Tutorial, Formal Methods in System Design, v.16 n.3, p.227-270, June 2000
	Anatol Slissenko, A Logic Framework for Verification of Timed Algorithms, Fundamenta Informaticae, v.62 n.1, p.29-67, January 2004
	Faisel Saeed , K. M. George , M. H. Samadzadeh, Implementation of classical mutual exclusion algorithms in Ada, ACM SIGAda Ada Letters, v.XII n.1, p.73-84, Jan./Feb. 1992
	Tai-Kuo Woo, A note on Lamport's mutual exclusion algorithm, ACM SIGOPS Operating Systems Review, v.24 n.4, p.78-80, Oct. 1990
	Gerald Jay Sussman , Guy L. Steele, Jr., Scheme: A Interpreter for Extended Lambda Calculus, Higher-Order and Symbolic Computation, v.11 n.4, p.405-439, December 1998
	Lisa Higham , Jalal Kawash, Tight Bounds for Critical Sections in Processor Consistent Platforms, IEEE Transactions on Parallel and Distributed Systems, v.17 n.10, p.1072-1083, October 2006
	Tomas Hruby , Kees van Reeuwijk , Herbert Bos, Ruler: high-speed packet matching and rewriting on NPUs, Proceedings of the 3rd ACM/IEEE Symposium on Architecture for networking and communications systems, December 03-04, 2007, Orlando, Florida, USA
	S. M. Ornstein , W. R. Crowther , M. F. Kraley , R. D. Bressler , A. Michel , F. E. Heart, Pluribus: a reliable multiprocessor, Proceedings of the May 19-22, 1975, national computer conference and exposition, May 19-22, 1975, Anaheim, California
	Shuvendu K. Lahiri , Randal E. Bryant, Predicate abstraction with indexed predicates, ACM Transactions on Computational Logic (TOCL), v.9 n.1, p.4-es, December 2007
	Prakash Chandrasekaran , Christopher L. Conway , Joseph M. Joy , Sriram K. Rajamani, Programming asynchronous layers with CLARITY, Proceedings of the the 6th joint meeting of the European software engineering conference and the ACM SIGSOFT symposium on The foundations of software engineering, September 03-07, 2007, Dubrovnik, Croatia
	M. Aater Suleman , Onur Mutlu , Moinuddin K. Qureshi , Yale N. Patt, Accelerating critical section execution with asymmetric multi-core architectures, ACM SIGPLAN Notices, v.44 n.3, March 2009
	Lisa Higham , Jalal Kawash, Implementing sequentially consistent programs on processor consistent platforms, Journal of Parallel and Distributed Computing, v.68 n.4, p.488-500, April, 2008
	José Meseguer , Miguel Palomino , Narciso Martí-Oliet, Equational abstractions, Theoretical Computer Science, v.403 n.2-3, p.239-264, August, 2008
	Ingo Brückner , Klaus Dräger , Bernd Finkbeiner , Heike Wehrheim, Slicing Abstractions, Fundamenta Informaticae, v.89 n.4, p.369-392, January 2009
	Tayfun Elmas , Shaz Qadeer , Serdar Tasiran, A calculus of atomic actions, Proceedings of the 36th annual ACM SIGPLAN-SIGACT symposium on Principles of programming languages, January 21-23, 2009, Savannah, GA, USA
	Yong-Jik Kim , James H. Anderson, Adaptive mutual exclusion with local spinning, Distributed Computing, v.19 n.3, p.197-236, January 2007
	Parosh Aziz Abdulla , Giorgio Delzanno , Ahmed Rezine, Approximated parameterized verification of infinite-state processes with global conditions, Formal Methods in System Design, v.34 n.2, p.126-156, April 2009
	Danny Hendler, Book review of synchronization algorithms and concurrent programming by Gadi Taubenfeld (Pearson/Prentice Hall, 2006), ACM SIGACT News, v.40 n.1, March 2009
	William N. Scherer, III , Doug Lea , Michael L. Scott, Scalable synchronous queues, Communications of the ACM, v.52 n.5, May 2009
	Florian Kluge , Chenglong Yu , Jörg Mische , Sascha Uhrig , Theo Ungerer, Implementing AUTOSAR scheduling and resource management on an embedded SMT processor, Proceedings of th 12th International Workshop on Software and Compilers for Embedded Systems, April 23-24, 2009, Nice, France
	Lamia Youseff , Keith Seymour , Haihang You , Dmitrii Zagorodnov , Jack Dongarra , Rich Wolski, Paravirtualization effect on single- and multi-threaded memory-intensive linear algebra software, Cluster Computing, v.12 n.2, p.101-122, June 2009
	Michal Armoni , Mordechai Ben-Ari, The concept of nondeterminism: its development and implications for teaching, ACM SIGCSE Bulletin, v.41 n.2, June 2009