Economical solutions for the critical section problem in a distributed system (Extended Abstract)

Subscribe (Full Service)


	Search: The ACM Digital Library The Guide

	Feedback

Economical solutions for the critical section problem in a distributed system (Extended Abstract)

Full text

Pdf (593 KB)

Source

Annual ACM Symposium on Theory of Computing archive
Proceedings of the ninth annual ACM symposium on Theory of computing table of contents

Boulder, Colorado, United States

Pages: 91 - 97

Year of Publication: 1977

Authors

Gary L. Peterson
Michael J. Fischer

Sponsors

ACM: Association for Computing Machinery
SIGACT: ACM Special Interest Group on Algorithms and Computation Theory

Publisher

ACM New York, NY, USA

Bibliometrics

Downloads (6 Weeks): 8, Downloads (12 Months): 35, Citation Count: 45

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

ABSTRACT

A solution to the critical section problem, first posed by Dijkstra [1], is a fundamental requirement for concurrent program control. The problem is to ensure that no two processes are in a specified area of their programs (the critical section) at the same time. Improvements to Dijkstra's solution were made by Knuth [2], deBruijn [3], and Eisenberg and McGuire [4]. The situation, for a distributed system was considered by Lamport [5]. Rivest and Pratt [6] presented a solution for a distributed system where processes may repeatedly fail. The algorithms to be presented will be further improvements, where the comparisons will be made according to three measures: message size—the number of values the variable for interprocess communication can take on; fairness—the sequence in which waiting processes enter their critical sections; and time—the amount of time a process spends attempting to enter its critical section.

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	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]
	2	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]
	3	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]
	4	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]
	5	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]
	6	R. L. Rivest and V. R. Pratt. The mutual exclusion problem for unreliable processes: preliminary report. Proceedings of the 17th Annual Symposium on Foundations of Computer Science (1976), 1&ndash8.

CITED BY 45

	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
	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
	Rajeev Alur , Gadi Taubenfeld, Contention—free complexity of shared memory algorithms, Proceedings of the thirteenth annual ACM symposium on Principles of distributed computing, p.61-70, August 14-17, 1994, Los Angeles, California, United States
	Nancy A. Lynch, Fast allocation of nearby resources in a distributed system, Proceedings of the twelfth annual ACM symposium on Theory of computing, p.70-81, April 28-30, 1980, Los Angeles, California, United States
	Yehuda Afek , David S. Greenberg , Michael Merritt , Gadi Taubenfeld, Computing with faulty shared memory, Proceedings of the eleventh annual ACM symposium on Principles of distributed computing, p.47-58, August 10-12, 1992, Vancouver, British Columbia, Canada
	Jeffrey M. Jaffe, Decentralized Simulation of Resource Managers, Journal of the ACM (JACM), v.30 n.2, p.300-322, April 1983
	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
	Eugene Styer , Gary L. Peterson, Improved algorithms for distributed resource allocation, Proceedings of the seventh annual ACM Symposium on Principles of distributed computing, p.105-116, August 15-17, 1988, Toronto, Ontario, Canada
	Jae-Heon Yang , James H. Anderson, Fast, scalable synchronization with minimal hardware support, Proceedings of the twelfth annual ACM symposium on Principles of distributed computing, p.171-182, August 15-18, 1993, Ithaca, New York, United States
	Yehuda Afek , Eytan Weisberger , Hanan Weisman, A completeness theorem for a class of synchronization objects, Proceedings of the twelfth annual ACM symposium on Principles of distributed computing, p.159-170, August 15-18, 1993, Ithaca, New York, United States
	Manhoi Choy , Ambuj K. Singh, Adaptive solutions to the mutual exclusion problem, Distributed Computing, v.8 n.1, p.1-17, August 1994
	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
	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
	Leslie Lamport, The mutual exclusion problem: partII—statement and solutions, Journal of the ACM (JACM), v.33 n.2, p.327-348, April 1986
	Raymond E. Miller , Chee K. Yap, On formulating simultaneity for studying parallelism and synchronization, Proceedings of the tenth annual ACM symposium on Theory of computing, p.105-113, May 01-03, 1978, San Diego, California, United States
	G. L. Peterson, Time-space trade-offs for asynchronous parallel models (Reducibilities and Equivalences), Proceedings of the eleventh annual ACM symposium on Theory of computing, p.224-230, April 30-May 02, 1979, Atlanta, Georgia, United States
	N. Lynch, A hundred impossibility proofs for distributed computing, Proceedings of the eighth annual ACM Symposium on Principles of distributed computing, p.1-28, June 1989, Edmonton, Alberta, Canada
	Nancy Lynch , Hagit Attiya, Using mappings to prove timing properties, Proceedings of the ninth annual ACM symposium on Principles of distributed computing, p.265-280, August 22-24, 1990, Quebec City, Quebec, Canada
	Injong Rhee , Jennifer L. Welch, The impact of time on the session problem, Proceedings of the eleventh annual ACM symposium on Principles of distributed computing, p.191-202, August 10-12, 1992, Vancouver, British Columbia, Canada
	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
	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
	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
	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
	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
	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
	B. Bloom, Constructing Two-Writer Atomic Registers, IEEE Transactions on Computers, v.37 n.12, p.1506-1514, December 1988
	Hagit Attiya , Nancy Lynch , Nir Shavit, Are wait-free algorithms fast?, Journal of the ACM (JACM), v.41 n.4, p.725-763, July 1994
	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
	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
	Harry Buhrman , Juan A. Garay , Jaap-Henki Hoepman , Mark Moir, Long-lived renaming made fast, Proceedings of the fourteenth annual ACM symposium on Principles of distributed computing, p.194-203, August 20-23, 1995, Ottowa, Ontario, Canada
	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
	Hagit Attiya , Vita Bortnikov, Adaptive and efficient mutual exclusion, Distributed Computing, v.15 n.3, p.177-189, July 2002
	Benton L. Leong , Joel I. Seiferas, New Real-Time Simulations of Multihead Tape Units, Journal of the ACM (JACM), v.28 n.1, p.166-180, Jan. 1981
	Walter Vogler, Faster asynchronous systems, Information and Computation, v.184 n.2, p.311-342, August 01, 2003
	Jerome A. Feldman, High level programming for distributed computing, Communications of the ACM, v.22 n.6, p.353-368, June 1979
	John Tromp , Paul Vitányi, Randomized two-process wait-free test-and-set, Distributed Computing, v.15 n.3, p.127-135, July 2002
	Injong Rhee, A modular algorithm for resource allocation, Distributed Computing, v.11 n.3, p.157-168, August 1998
	Rajeev Alur , Gadi Taubenfeld, Fast timing-based algorithms, Distributed Computing, v.10 n.1, p.1-10, July 1996
	Nancy A. Lynch , Hagit Attiya, Using mappings to prove timing properties, Distributed Computing, v.6 n.2, p.121-139, September 1992
	Jennifer L. Welch , Nancy A. Lynch, A modular drinking philosophers algorithm, Distributed Computing, v.6 n.4, p.233-244, July 1993
	Shlomi Dolev , Amos Israeli , Shlomo Moran, Self-stabilization of dynamic systems assuming only read/write atomicity, Distributed Computing, v.7 n.1, p.3-16, November 1993
	Michael Merritt , Gadi Taubenfeld, Atomic m-register operations, Distributed Computing, v.7 n.4, p.213-221, May 1994
	R. Cole , O. Zajicek, The APRAM: incorporating asynchrony into the PRAM model, Proceedings of the first annual ACM symposium on Parallel algorithms and architectures, p.169-178, June 18-21, 1989, Santa Fe, New Mexico, United States
	Olga Brukman , Shlomi Dolev , Elliot K. Kolodner, A self-stabilizing autonomic recoverer for eventual Byzantine software, Journal of Systems and Software, v.81 n.12, p.2315-2327, December, 2008
	Hagit Attiya , Rachid Guerraoui , Danny Hendler , Petr Kuznetsov, The complexity of obstruction-free implementations, Journal of the ACM (JACM), v.56 n.4, p.1-33, June 2009