Concurrent reading and writing

Subscribe (Full Service)


	Search: The ACM Digital Library The Guide

	Feedback

Concurrent reading and writing

Full text

Pdf (629 KB)

Source

Communications of the ACM archive
Volume 20 , Issue 11 (November 1977) table of contents

Pages: 806 - 811

Year of Publication: 1977

ISSN:0001-0782

Author

Leslie Lamport

Massachusetts Computer Associates, Wakefield

Publisher

ACM New York, NY, USA

Bibliometrics

Downloads (6 Weeks): 12, Downloads (12 Months): 105, Citation Count: 62

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

ABSTRACT

The problem of sharing data among asynchronous processes is considered. It is assumed that only one process at a time can modify the data, but concurrent reading and writing is permitted. Two general theorems are proved, and some algorithms are presented to illustrate their use. These include a solution to the general problem in which a read is repeated if it might have obtained an incorrect result, and two techniques for transmitting messages between processes. These solutions do not assume any synchronizing mechanism other than data which can be written by one process and read by other processes.

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	Brinch Hansen, P. A comparison of two synchronizing concepts. Acta lnformatica 1, 3 (1972), 190-199.
	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	William B. Easton, Process synchronization without long-term interlock, Proceedings of the third ACM symposium on Operating systems principles, p.95-100, October 18-20, 1971, Palo Alto, California, United States [doi>10.1145/800212.806505]
	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	Lamport, L. Proving the correctness of multiprocess programs. 1EEE Trans. on Software Engineering SE-3 , 2 (Mar. 1977), 125- 143.
	7	Schaefer, M. Quasi-synchronization of readers and writers in a secure multi-level environment. TM-5407/003, System Development Corp., Santa Monica, Calif., Sept. 1974.
	8	White, J.C.C. Design of a secure file management system. MTR-2931, The Mitre Corp., Bedford, Mass., June 1974.

CITED BY 62

	H. T. Kung , Philip L. Lehman, Concurrent manipulation of binary search trees, ACM Transactions on Database Systems (TODS), v.5 n.3, p.354-382, Sept. 1980
	Prasad Jayanti , Tushar Deepak Chandra , Sam Toueg, Fault-tolerant wait-free shared objects, Journal of the ACM (JACM), v.45 n.3, p.451-500, May 1998
	Cynthia Dwork , Orli Waarts, Simple and efficient bounded concurrent timestamping and the traceable use abstraction, Journal of the ACM (JACM), v.46 n.5, p.633-666, Sept. 1999
	James H. Anderson , Srikanth Ramamurthy , Kevin Jeffay, Real-time computing with lock-free shared objects, ACM Transactions on Computer Systems (TOCS), v.15 n.2, p.134-165, May 1997
	J. Misra, Axioms for memory access in asynchronous hardware systems, ACM Transactions on Programming Languages and Systems (TOPLAS), v.8 n.1, p.142-153, Jan. 1986
	Prasad Jayanti, On the robustness of Herlihy's hierarchy, Proceedings of the twelfth annual ACM symposium on Principles of distributed computing, p.145-157, August 15-18, 1993, Ithaca, New York, United States
	M. Herlihy, A methodology for implementing highly concurrent data structures, ACM SIGPLAN Notices, v.25 n.3, p.197-206, Mar. 1990
	David P. Reed , Rajendra K. Kanodia, Synchronization with eventcounts and sequencers, Communications of the ACM, v.22 n.2, p.115-123, Feb. 1979
	Philip L. Lehman , s. Bing Yao, Efficient locking for concurrent operations on B-trees, ACM Transactions on Database Systems (TODS), v.6 n.4, p.650-670, Dec. 1981
	M. Wein , Wm Cowan , W. M. Gentleman, Visual support for version management, Proceedings of the 1992 ACM/SIGAPP symposium on Applied computing: technological challenges of the 1990's, p.1217-1223, March 1992, Kansas City, Missouri, United States
	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
	Khawar M. Zuberi , Padmanabhan Pillai , Kang G. Shin, EMERALDS: a small-memory real-time microkernel, ACM SIGOPS Operating Systems Review, v.33 n.5, p.277-299, Dec. 1999
	Juan Alemany , Edward W. Felten, Performance issues in non-blocking synchronization on shared-memory multiprocessors, Proceedings of the eleventh annual ACM symposium on Principles of distributed computing, p.125-134, August 10-12, 1992, Vancouver, British Columbia, Canada
	J. E. Burns , G. L. Peterson, The ambiguity of choosing, Proceedings of the eighth annual ACM Symposium on Principles of distributed computing, p.145-157, June 1989, Edmonton, Alberta, Canada
	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
	Maurice P. Herlihy, Impossibility and universality results for wait-free synchronization, Proceedings of the seventh annual ACM Symposium on Principles of distributed computing, p.276-290, August 15-17, 1988, Toronto, Ontario, Canada
	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
	J. Aspnes , M. Herlihy, Wait-free data structures in the asynchronous PRAM model, Proceedings of the second annual ACM symposium on Parallel algorithms and architectures, p.340-349, July 02-06, 1990, Island of Crete, Greece
	Maurice Herlihy, Wait-free synchronization, ACM Transactions on Programming Languages and Systems (TOPLAS), v.13 n.1, p.124-149, Jan. 1991
	John D. Valois, Lock-free linked lists using compare-and-swap, Proceedings of the fourteenth annual ACM symposium on Principles of distributed computing, p.214-222, August 20-23, 1995, Ottowa, Ontario, Canada
	W. Morven Gentleman , Marceli Wein, Mass market computers for software development, Proceedings of the 1991 ACM SIGSMALL/PC symposium on Small systems, p.93-99, June 12-14, 1991, Toronto, Ontario, Canada
	N. Nishimura, Asynchronous shared memory parallel computation, Proceedings of the second annual ACM symposium on Parallel algorithms and architectures, p.76-84, July 02-06, 1990, Island of Crete, Greece
	Leslie Lamport, Specifying Concurrent Program Modules, ACM Transactions on Programming Languages and Systems (TOPLAS), v.5 n.2, p.190-222, April 1983
	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 , Gary L. Peterson, Constructing multi-reader atomic values from non-atomic values, Proceedings of the sixth annual ACM Symposium on Principles of distributed computing, p.222-231, August 10-12, 1987, Vancouver, British Columbia, Canada
	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, Concurrent Reading While Writing, ACM Transactions on Programming Languages and Systems (TOPLAS), v.5 n.1, p.46-55, Jan. 1983
	Maurice Herlihy, Impossibility results for asynchronous PRAM (extended abstract), Proceedings of the third annual ACM symposium on Parallel algorithms and architectures, p.327-336, July 21-24, 1991, Hilton Head, South Carolina, United States
	Shlomo Moran , Gadi Taubenfeld , Irit Yadin, Concurrent counting, Proceedings of the eleventh annual ACM symposium on Principles of distributed computing, p.59-70, August 10-12, 1992, Vancouver, British Columbia, Canada
	Roberto Segala, Verification of randomized distributed algorithms, Lectures on formal methods and performance analysis: first EEF/Euro summer school on trends in computer science, Springer-Verlag New York, Inc., New York, NY, 2002
	Ashis Tarafdar , Vijay K. Garg, Predicate control: synchronization in distributed computations with look-ahead, Journal of Parallel and Distributed Computing, v.64 n.2, p.219-237, February 2004
	Leslie Lamport, Concurrent reading and writing of clocks, ACM Transactions on Computer Systems (TOCS), v.8 n.4, p.305-310, Nov. 1990
	Ravi Rajwar , James R. Goodman, Transactional lock-free execution of lock-based programs, ACM SIGOPS Operating Systems Review, v.36 n.5, December 2002
	Maurice Herlihy, Randomized wait-free concurrent objects (extended abstract), Proceedings of the tenth annual ACM symposium on Principles of distributed computing, p.11-21, August 19-21, 1991, Montreal, Quebec, Canada
	B. Bloom, Constructing Two-Writer Atomic Registers, IEEE Transactions on Computers, v.37 n.12, p.1506-1514, December 1988
	W. Morven Gentleman , Marceli Wein, Mass market computer for software development, ACM SIGSMALL/PC Notes, v.17 n.3-4, p.22-28, Fall/Winter 1991
	J. Strother Moore, A Mechanically Checked Proof of a Multiprocessor Result via a Uniprocessor View, Formal Methods in System Design, v.14 n.2, p.213-228, March 1999
	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
	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
	Maged M. Michael, Scalable lock-free dynamic memory allocation, ACM SIGPLAN Notices, v.39 n.6, May 2004
	Anna Pogosyants , Roberto Segala , Nancy Lynch, Verification of the randomized consensus algorithm of Aspnes and Herlihy: a case study, Distributed Computing, v.13 n.3, p.155-186, July 2000
	Mohamed F. Younis , Mohamed Aboutabl , Daeyoung Kim, Software environment for integrating critical real-time control systems, Journal of Systems Architecture: the EUROMICRO Journal, v.50 n.11, p.649-674, November 2004
	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
	James H. Anderson, Composite registers, Distributed Computing, v.6 n.3, p.141-154, April 1993
	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
	Michel Raynal, Wait-free computing: an introductory lecture, Future Generation Computer Systems, v.21 n.5, p.655-663, May 2005
	Lidong Zhou , Fred B. Schneider , Robbert Van Renesse, APSS: proactive secret sharing in asynchronous systems, ACM Transactions on Information and System Security (TISSEC), v.8 n.3, p.259-286, August 2005
	James H. Anderson, Multi-writer composite registers, Distributed Computing, v.7 n.4, p.175-195, May 1994
	Ravi Rajwar , James R. Goodman, Speculative lock elision: enabling highly concurrent multithreaded execution, Proceedings of the 34th annual ACM/IEEE international symposium on Microarchitecture, December 01-05, 2001, Austin, Texas
	Guojing Cong , David A. Bader, Designing irregular parallel algorithms with mutual exclusion and lock-free protocols, Journal of Parallel and Distributed Computing, v.66 n.6, p.854-866, June 2006
	Naomi Nishimura, Asynchronous shared memory parallel computation (preliminary version), ACM SIGARCH Computer Architecture News, v.19 n.1, p.97-105, March 1991
	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
	Phuong Hoai Ha , Philippas Tsigas , Otto J. Anshus, Non-blocking programming on multi-core graphics processors: (extended asbtract), ACM SIGARCH Computer Architecture News, v.36 n.5, December 2008
	Hai Huang , Padmanabhan Pillai , Kang G. Shin, Improving Wait-Free Algorithms for Interprocess Communication in Embedded Real-Time Systems, Proceedings of the General Track: 2002 USENIX Annual Technical Conference, p.303-316, June 10-15, 2002
	Walid Rjaibi , Paul Bird, A multi-purpose implementation of mandatory access control in relational database management systems, Proceedings of the Thirtieth international conference on Very large data bases, p.1010-1020, August 31-September 03, 2004, Toronto, Canada
	Hany E. Ramadan , Christopher J. Rossbach , Donald E. Porter , Owen S. Hofmann , Aditya Bhandari , Emmett Witchel, MetaTM/TxLinux: transactional memory for an operating system, ACM SIGARCH Computer Architecture News, v.35 n.2, May 2007
	V. W. Setzer , Andrea Zisman, New Concurrency Control Algorithms for Accessing and Compacting B-Trees, Proceedings of the 20th International Conference on Very Large Data Bases, p.238-248, September 12-15, 1994
	Ravi Rajwar , Maurice Herlihy , Konrad Lai, Virtualizing Transactional Memory, ACM SIGARCH Computer Architecture News, v.33 n.2, p.494-505, May 2005
	Christopher J. Rossbach , Owen S. Hofmann , Donald E. Porter , Hany E. Ramadan , Bhandari Aditya , Emmett Witchel, TxLinux: using and managing hardware transactional memory in an operating system, ACM SIGOPS Operating Systems Review, v.41 n.6, December 2007
	Shaohua Xie , Eileen Kraemer , R. E. K. Stirewalt , Laura K. Dillon , Scott D. Fleming, Assessing the benefits of synchronization-adorned sequence diagrams: two controlled experiments, Proceedings of the 4th ACM symposium on Software visuallization, September 16-17, 2008, Ammersee, Germany
	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

INDEX TERMS

Keywords:
asynchronous multiprocessing, multiprocess synchronization, readers/writers problem, shared data

Collaborative Colleagues:

Leslie Lamport: colleagues

Adobe Acrobat

QuickTime

Windows Media Player

Real Player