Limitations of synchronization primitives with conditional branching and global variables

Subscribe (Full Service)


	Search: The ACM Digital Library The Guide

	Feedback

Limitations of synchronization primitives with conditional branching and global variables

Full text

Pdf (787 KB)

Source

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

Seattle, Washington, United States

Pages: 230 - 241

Year of Publication: 1974

Author

R. J. Lipton

Sponsor

SIGACT: ACM Special Interest Group on Algorithms and Computation Theory

Publisher

ACM New York, NY, USA

Bibliometrics

Downloads (6 Weeks): 2, Downloads (12 Months): 15, Citation Count: 7

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

ABSTRACT

A formal model of the process concept is presented. This model can represent sets of processes that use the synchronization primitive PV or one of the many generalizations of PV. The study of synchronization problems is then reduced to the study of relations between sets of processes. For one relation— “simulate”—it is possible to show that there are differences between several synchronization primitives. These differences show that the relative “power” of these synchronization primitives is not the same.

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. Cooperating sequential processes. Programming Languages, edited by F. Genuys, 43-112, 1968.
	2	P. J. Courtois, F. Heymans, D. L. Parnas. Comments on "a comparison of two synchronizing concepts by P. B. Hansen" Acta Informatica 1:375-376, 1972.
	3	P. B. Hansen. A comparison of two synchronizing concepts. Acta Informatica 1:190-199, 1972.
	4	A. Nico Habermann, Synchronization of communicating processes, Communications of the ACM, v.15 n.3, p.171-176, March 1972 [doi>10.1145/361268.361277]
	5	E. W. Dijkstra. Hierarchical orderings of sequential processes. Acta Informatica 1(2):115-138, 1971.
	6	H. Vantilborgh and A. van Lamsweerde. On an extension of Dijkstra's semaphore primitives. Information Processing Letters 1:18-186, 1972.
	7	S. S. Patil. Limitations and capabilities of Dijkstra's semaphore primitives for coordination among processes. Project MAC Computational Structures Group Memo 57, 1971.
	8	E. W. Dijkstra. Unpublished manuscript.
	9	P. Wodon. Still another tool for controlling cooperating algorithms. Carnegie-Mellon University Report, 1972.
	10	D. L. Parnas. On a solution to the cigarette smokers' problem (without conditional statements). Carnegie-Mellon University Report, 1972.
	11	J. H. Saltzer. Traffic Control in a Multiplexed Computer System, PhD thesis, MIT (Project MAC), 1966.
	12	R. J. Lipton. On synchronization primitive systems. Yale Computer Science Research Report #22, 1973.
	13	Jack B. Dennis , Earl C. Van Horn, Programming semantics for multiprogrammed computations, Communications of the ACM, v.9 n.3, p.143-155, March 1966 [doi>10.1145/365230.365252]
	14	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]
	15	R. J. Lipton. Reduction: a new method for proving properties of systems of processes. In preparation.

CITED BY 7

	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
	Peter B. Henderson , Yechezkel Zalcstein, Synchronization Problems Solvable by Generalized PV Systems, Journal of the ACM (JACM), v.27 n.1, p.60-71, Jan. 1980
	Thomas W. Doeppner, Jr., Parallel program correctness through refinement, Proceedings of the 4th ACM SIGACT-SIGPLAN symposium on Principles of programming languages, p.155-169, January 17-19, 1977, Los Angeles, California
	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
	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
	Takayuki Kimura, An algebraic system for process structuring and interprocess communication, Proceedings of the eighth annual ACM symposium on Theory of computing, p.92-100, May 03-05, 1976, Hershey, Pennsylvania, United States
	Hans W. Barz, Implementing semaphores by binary semaphores, ACM SIGPLAN Notices, v.18 n.2, p.39-45, February 1983