A first-come-first-served mutual-exclusion algorithm with small communication variables

Subscribe (Full Service)


	Search: The ACM Digital Library The Guide

	Feedback

A first-come-first-served mutual-exclusion algorithm with small communication variables

Full text

Pdf (1.22 MB)

Source

ACM Transactions on Programming Languages and Systems (TOPLAS) archive
Volume 13 , Issue 4 (October 1991) table of contents

Pages: 558 - 576

Year of Publication: 1991

ISSN:0164-0925

Authors

Edward A. Lycklama	Univ. of Toronto, Toronto, Ont., Canada
Vassos Hadzilacos	Univ. of Toronto, Toronto, Ont., Canada

Publisher

ACM New York, NY, USA

Bibliometrics

Downloads (6 Weeks): 9, Downloads (12 Months): 79, Citation Count: 9

Additional Information:

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/115372.115370 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	James Edward Burns, Complexity of communication among asynchronous parallel processes, 1981
	2	BURNS, J. E., AND LYNCH, N. A. Mutual exclusion using indivisible reads and writes. In Proceedings of the 18th Allerton Conference on Communication, Control and Computing (Monticello, Ill., Oct. 8-10, 1980), pp. 833-342.
	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	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, 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]
	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	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]
	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	LAMPORT, L. On inter-process communication--Parts I and II. Distrib. Comput. 1, 2 (1986), 77-101.
	11	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]
	12	LYCKLAMA, E.A. A first-come first-served solution to the critical section problem using rive bits. M.S. thesis, Dept. of Computer Science, Univ. of Toronto, Ontario, Oct. 1987.
	13	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]
	14	TRUUVERT, K. M.S. thesis, Dept. of Computer Science, Univ. of Toronto, Ontario, 1989.

CITED BY 9

	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
	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
	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
	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
	Xiaodong Zhang , Yong Yan , Robert Castañeda, Evaluating and Designing Software Mutual Exclusion Algorithms on Shared-Memory Multiprocessors, IEEE Parallel & Distributed Technology: Systems & Technology, v.4 n.1, p.25-42, March 1996
	Manhoi Choy , Ambuj K. Singh, Adaptive solutions to the mutual exclusion problem, Distributed Computing, v.8 n.1, p.1-17, August 1994
	Srdjan Petrovic, Space-efficient FCFS group mutual exclusion, Information Processing Letters, v.95 n.2, p.343-350, 31 July 2005

INDEX TERMS

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

General Terms:
Algorithms, Design, Theory

Keywords:
critical selection, distributed systems, nonatomic operations

REVIEW

"Charles N. Schroeder : Reviewer"

The algorithm for the mutual-exclusion problem discussed in this paper satisfies the first-come-first-served property. Five shared bits per process are required to implement the algorithm. The authors claim that this algorithm is the first of more...

Collaborative Colleagues:

Edward A. Lycklama: colleagues

Vassos Hadzilacos: colleagues

Adobe Acrobat

QuickTime

Windows Media Player

Real Player