Synchronization with eventcounts and sequencers

Subscribe (Full Service)


	Search: The ACM Digital Library The Guide

	Feedback

Synchronization with eventcounts and sequencers

Full text

Pdf (1.02 MB)

Source

Communications of the ACM archive
Volume 22 , Issue 2 (February 1979) table of contents

Pages: 115 - 123

Year of Publication: 1979

ISSN:0001-0782

Authors

David P. Reed	Massachusetts Institute of Technology, Cambridge, MA
Rajendra K. Kanodia	Massachusetts Institute of Technology, Cambridge, MA

Publisher

ACM New York, NY, USA

Bibliometrics

Downloads (6 Weeks): 23, Downloads (12 Months): 96, Citation Count: 44

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

ABSTRACT

Synchronization of concurrent processes requires controlling the relative ordering of events in the processes. A new synchronization mechanism is proposed, using abstract objects called eventcounts and sequencers, that allows processes to control the ordering of events directly, rather than using mutual exclusion to protect manipulations of shared variables that control ordering of events. Direct control of ordering seems to simplify correctness arguments and also simplifies implementation in distributed systems. The mechanism is defined formally, and then several examples of its use are given. The relationship of the mechanism to protection mechanisms in the system is explained; in particular, eventcounts are shown to be applicable to situations where confinement of information matters. An implementation of eventcounts and sequencers in a system with shared memory is described.

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	Bell, D.E., and LaPadula, L.J. Secure computer systems: A mathematical model. Air Force Electr. Systs. Div. Rcp. ESD-TR-73- 278, Vol. II, Nov. 1973.
	2	Per Brinch Hansen, Concurrent Programming Concepts, ACM Computing Surveys (CSUR), v.5 n.4, p.223-245, Dec. 1973 [doi>10.1145/356622.356624]
	3	P. J. Courtois , F. Heymans , D. L. Parnas, Concurrent control with “readers” and “writers”, Communications of the ACM, v.14 n.10, p.667-668, Oct. 1971 [doi>10.1145/362759.362813]
	4	Dorothy E. Denning, A lattice model of secure information flow, Communications of the ACM, v.19 n.5, p.236-243, May 1976 [doi>10.1145/360051.360056]
	5	Dijkstra, E. W. Cooperating sequential processes. In Programming Languages, F. Genuys, Ed., Academic Press, New York, 1968.
	6	Dijkstra, E. W. Hierarchical ordering of sequential processes. Acta Informatica 1 (1970, 115-138.
	7	William B. Easton, Process synchronization without long-term interlock, ACM SIGOPS Operating Systems Review, v.6 n.1/2, June 1972 [doi>10.1145/850614.850632]
	8	Greff, I. Semantics of communicating parallel processes. M.I.T. Proj. MAC TR-154, Sept. 1975.
	9	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]
	10	C. A. R. Hoare, Monitors: an operating system structuring concept, Communications of the ACM, v.17 n.10, p.549-557, Oct. 1974 [doi>10.1145/355620.361161]
	11	John H. Howard, Proving monitors, Communications of the ACM, v.19 n.5, p.273-279, May 1976 [doi>10.1145/360051.360079]
	12	Kanodia, R. K., and Reed, D. P. Synchronization in distributed systems. In Preparation.
	13	Zvi Kohavi , Richard W. Hamming , Edward A. Feigenbaum, Switching and Finite Automata Theory: Computer Science Series, McGraw-Hill Higher Education, 1990
	14	Leslie Lamport, Time, clocks, and the ordering of events in a distributed system, Communications of the ACM, v.21 n.7, p.558-565, July 1978 [doi>10.1145/359545.359563]
	15	Lamport, L. Synchronization of independent processes. Acta Informatica 7, 1 (1976), 15-34.
	16	Leslie Lamport, Concurrent reading and writing, Communications of the ACM, v.20 n.11, p.806-811, Nov. 1977 [doi>10.1145/359863.359878]
	17	Butler W. Lampson, A note on the confinement problem, Communications of the ACM, v.16 n.10, p.613-615, Oct. 1973 [doi>10.1145/362375.362389]
	18	Susan Owicki , David Gries, Verifying properties of parallel programs: an axiomatic approach, Communications of the ACM, v.19 n.5, p.279-285, May 1976 [doi>10.1145/360051.360224]
	19	Patti, S. S. Limitations and capabilities of Dijkstra's semaphore primitives for coordination among processes. M.I.T. Proj. MAC Computational Structures Group Memo 57, Feb. 1971.
	20	D. P. Reed, PROCESSOR MULTIPLEXING IN A LAYED OPERATING SYSTEM, Massachusetts Institute of Technology, Cambridge, MA, 1976
	21	Schaefer, M. Quasi-synchronization of readers and writers in a secure multi-level environment. Syst. Develop. Corp. TM-5407/003, Sept. 1974.

CITED BY 44

	Robbert van Renesse , Kenneth P. Birman , Silvano Maffeis, Horus: a flexible group communication system, Communications of the ACM, v.39 n.4, p.76-83, April 1996
	Stephen A. Ward , Robert H. Halstead, Jr., A Syntactic Theory of Message Passing, Journal of the ACM (JACM), v.27 n.2, p.365-383, April 1980
	Perry A. Emrath , David A. Padua, Automatic detection of nondeterminacy in parallel programs, ACM SIGPLAN Notices, v.24 n.1, p.89-99, Jan. 1989
	Fred B. Schneider, Synchronization in Distributed Programs, ACM Transactions on Programming Languages and Systems (TOPLAS), v.4 n.2, p.125-148, April 1982
	Gregory R. Andrews , Richard P. Reitman, An Axiomatic Approach to Information Flow in Programs, ACM Transactions on Programming Languages and Systems (TOPLAS), v.2 n.1, p.56-76, Jan. 1980
	Nicolas Vidot , Michelle Cart , Jean Ferrié , Maher Suleiman, Copies convergence in a distributed real-time collaborative environment, Proceedings of the 2000 ACM conference on Computer supported cooperative work, p.171-180, December 2000, Philadelphia, Pennsylvania, United States
	Michael J. Feeley , Henry M. Levy, Distributed shared memory with versioned objects, ACM SIGPLAN Notices, v.27 n.10, p.247-262, Oct. 1992
	Gregory R. Andrews, Synchronizing Resources, ACM Transactions on Programming Languages and Systems (TOPLAS), v.3 n.4, p.405-430, Oct. 1981
	Clarence A. Ellis , Gary J. Nutt, Office Information Systems and Computer Science, ACM Computing Surveys (CSUR), v.12 n.1, p.27-60, March 1980
	Stuart R. Faulk , David L. Parnas, On synchronization in hard-real-time systems, Communications of the ACM, v.31 n.3, p.274-287, March 1988
	Verlynda Dobbs, A comparison of concurrent languages: a class project, ACM SIGCSE Bulletin, v.19 n.1, p.62-66, Feb. 1987
	Kunle Olukotun , Mark Heinrich , David Ofelt, Digital system simulation: methodologies and examples, Proceedings of the 35th annual conference on Design automation, p.658-663, June 15-19, 1998, San Francisco, California, United States
	Walter H. Kohler, A Survey of Techniques for Synchronization and Recovery in Decentralized Computer Systems, ACM Computing Surveys (CSUR), v.13 n.2, p.149-183, June 1981
	John M. Mellor-Crummey , Michael L. Scott, Synchronization without contention, ACM SIGARCH Computer Architecture News, v.19 n.2, p.269-278, Apr. 1991
	Jerome H. Saltzer, Research problems of decentralized systems with largely autonomous nodes, ACM SIGOPS Operating Systems Review, v.12 n.1, p.43-52, January 1978
	Kathryn Heninger Britton , R. Alan Parker , David L. Parnas, A procedure for designing abstract interfaces for device interface modules, Proceedings of the 5th international conference on Software engineering, p.195-204, March 09-12, 1981, San Diego, California, 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
	Mingqi Deng, Distributed asynchronous winner-take-all structures and conflict detection, Proceedings of the 1992 ACM/SIGAPP Symposium on Applied computing: technological challenges of the 1990's, p.629-635, April 1992, Kansas City, Missouri, United States
	Brain A. Rudolph, Self-assessment procedure XXI: a self-assessment procedure on concurrency, Communications of the ACM, v.33 n.5, p.563-576, May 1990
	Vijayalakshmi Atluri , Sushil Jajodia , Elisa Bertino, Transaction Processing in Multilevel Secure Databases with Kernelized Architecture: Challenges and Solutions, IEEE Transactions on Knowledge and Data Engineering, v.9 n.5, p.697-708, September 1997
	James E. Lumpp , Kuppuswamy Sivakumar , Christopher Diaz , James N. Griffioen, Performance visualization for distributed shared memory systems, Virtual shared memory for distributed architectures, Nova Science Publishers, Inc., Commack, NY, 2001
	Ramez Elmasri , Cory Devor , Said Rahimi, Notes on DDTS: an apparatus for experimental research in distributed database management systems, ACM SIGMOD Record, v.11 n.4, p.32-49, July 1981
	Paul Ammann , Sushil Jajodia, Distributed timestamp generation in planar lattice networks, ACM Transactions on Computer Systems (TOCS), v.11 n.3, p.205-225, Aug. 1993
	Boris Kogan , S. Jajodia, Concurrency control in multilevel-secure databases based on replicated architecture, ACM SIGMOD Record, v.19 n.2, p.153-162, Jun. 1990
	Edward E. Balkovich , Colin Whitby-Strevens, On the performance of decentralized software, ACM SIGMETRICS Performance Evaluation Review, v.9 n.2, p.173-180, Summer 1980
	Xiaodong Zhang , Robert Castañeda , Elisa W. Chan, Spin-Lock Synchronization on the Butterfly and KSR1, IEEE Parallel & Distributed Technology: Systems & Technology, v.2 n.1, p.51-63, March 1994
	Lui Sha , E. Douglas Jensen , Richard F. Rashid , J. Duane Northcutt, Distributed co-operating processes and transactions, ACM SIGCOMM Computer Communication Review, v.13 n.2, April 1983
	Elisa Bertino , Sushil Jajodia , Luigi Mancini , Indrajit Ray, Advanced Transaction Processing in Multilevel Secure File Stores, IEEE Transactions on Knowledge and Data Engineering, v.10 n.1, p.120-135, January 1998
	James M. Nead, On the semantics of control statements, ACM SIGPLAN Notices, v.14 n.11, November 1979
	Paul A. Karger , Mary Ellen Zurko , Douglas W. Bonin , Andrew H. Mason , Clifford E. Kahn, A Retrospective on the VAX VMM Security Kernel, IEEE Transactions on Software Engineering, v.17 n.11, p.1147-1165, November 1991
	T. F. Keefe , W. T. Tsai , J. Srivastava, Database Concurrency Control in Multilevel Secure Database Management Systems, IEEE Transactions on Knowledge and Data Engineering, v.5 n.6, p.1039-1055, December 1993
	Vijayalakshmi Atluri , Sushil Jajodia , Elisa Bertino, Alternative Correctness Criteria for Concurrent Execution of Transactions in Multilevel Secure Databases, IEEE Transactions on Knowledge and Data Engineering, v.8 n.5, p.839-854, October 1996
	S. Nishio , K. F. Li , E. G. Manning, A Resilient Mutual Exclusion Algorithm for Computer Networks, IEEE Transactions on Parallel and Distributed Systems, v.1 n.3, p.344-356, July 1990
	H. Neil Singleton , Ronnie G. Ward, Lamport's algorithm reconsidered, Proceedings of the ACM '82 conference, p.182-185, January 1982
	Boris Roussev , Jie Wu, Distributed computing using Java: a comparison of two server designs, Journal of Systems Architecture: the EUROMICRO Journal, v.52 n.7, p.432-440, July 2006
	Ifen Yang , William Moloney, Concurrent reading and writing with replicated data objects, Proceedings of the 1988 ACM sixteenth annual conference on Computer science, p.414-417, February 1988, Atlanta, Georgia, United States
	David L. Sims , Debra A. Hensgen , Lantz Moore, Performance of concurrent servers generated automatically from sequential servers, USENIX Systems on USENIX Experiences with Distributed and Multiprocessor Systems, p.10-10, September 22-23, 1993, San Diego, California
	Bhavani Thuraisingham , Hai-Ping Ko, Concurrency control in trusted database management systems: a survey, ACM SIGMOD Record, v.22 n.4, p.52-59, Dec. 1993
	Ming-Chit Tam , Jonathan M. Smith , David J. Farber, A taxonomy-based comparison of several distributed shared memory systems, ACM SIGOPS Operating Systems Review, v.24 n.3, p.40-67, July 1990
	Deepinder P. Sidhu , Alexander L. Wijesinha, Performance analysis of a constrained resource sharing system, Queueing Systems: Theory and Applications, v.29 n.2-4, p.293-311, 1998
	Ryan Johnson , Ippokratis Pandis , Anastasia Ailamaki, Critical sections: re-emerging scalability concerns for database storage engines, Proceedings of the 4th international workshop on Data management on new hardware, June 13-13, 2008, Vancouver, Canada
	Cynthia E. Irvine , Timothy E. Levin , Paul C. Clark , Thuy D. Nguyen, A security architecture for transient trust, Proceedings of the 2nd ACM workshop on Computer security architectures, October 31-31, 2008, Alexandria, Virginia, USA
	Sin Ming Loo , C. Arlen Planting, Use of discrete and soft processors in introductory microprocessors and embedded systems curriculum, ACM SIGBED Review, v.6 n.1, p.1-10, January 2009
	Michael Monagan , Roman Pearce, Parallel sparse polynomial multiplication using heaps, Proceedings of the 2009 international symposium on Symbolic and algebraic computation, July 28-31, 2009, Seoul, Republic of Korea

INDEX TERMS

Keywords:
distributed systems, interprocess communication, mutual exclusion, process synchronization, security models, semaphores

Collaborative Colleagues:

David P. Reed: colleagues

Rajendra K. Kanodia: colleagues

Adobe Acrobat

QuickTime

Windows Media Player

Real Player