ACM Portal
  Subscribe (Full Service)    Register (Limited Service, Free)    Login
  Search:   The ACM Digital Library   The Guide
  
ACM Home Page
Please provide us with feedback. Feedback
Concurrent reading and writing
Full text PdfPdf (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): 13,   Downloads (12 Months): 111,   Citation Count: 60
Additional Information:

abstract   references   cited by   index terms   collaborative colleagues   peer to peer  

Tools and Actions: Request Permissions Request Permissions    Review this Article  
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  60
Leslie Lamport, Concurrent reading and writing of clocks, ACM Transactions on Computer Systems (TOCS), v.8 n.4, p.305-310, Nov. 1990
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
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
 
B. Bloom, Constructing Two-Writer Atomic Registers, IEEE Transactions on Computers, v.37 n.12, p.1506-1514, December 1988
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
Gary L. Peterson, Concurrent Reading While Writing, ACM Transactions on Programming Languages and Systems (TOPLAS), v.5 n.1, p.46-55, Jan. 1983
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
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
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
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
Leslie Lamport, Specifying Concurrent Program Modules, ACM Transactions on Programming Languages and Systems (TOPLAS), v.5 n.2, p.190-222, 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 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
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
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
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
 
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
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
Maged M. Michael, Scalable lock-free dynamic memory allocation, ACM SIGPLAN Notices, v.39 n.6, May 2004
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
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
Naomi Nishimura, Asynchronous shared memory parallel computation (preliminary version), ACM SIGARCH Computer Architecture News, v.19 n.1, p.97-105, March 1991
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
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
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
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
Ravi Rajwar , Maurice Herlihy , Konrad Lai, Virtualizing Transactional Memory, ACM SIGARCH Computer Architecture News, v.33 n.2, p.494-505, May 2005
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
 
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
 
Michel Raynal, Wait-free computing: an introductory lecture, Future Generation Computer Systems, v.21 n.5, p.655-663, May 2005
 
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
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
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
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
David P. Reed , Rajendra K. Kanodia, Synchronization with eventcounts and sequencers, Communications of the ACM, v.22 n.2, p.115-123, Feb. 1979
 
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
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
 
James H. Anderson, Composite registers, Distributed Computing, v.6 n.3, p.141-154, April 1993
 
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
 
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
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
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
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
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
Ravi Rajwar , James R. Goodman, Transactional lock-free execution of lock-based programs, ACM SIGOPS Operating Systems Review, v.36 n.5, December 2002
 
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
M. Herlihy, A methodology for implementing highly concurrent data structures, ACM SIGPLAN Notices, v.25 n.3, p.197-206, Mar. 1990
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
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
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
 
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
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
 
James H. Anderson, Multi-writer composite registers, Distributed Computing, v.7 n.4, p.175-195, May 1994
 
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
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
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
 
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
 
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
 
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

INDEX TERMS

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

Collaborative Colleagues:
Leslie Lamport: colleagues

Peer to Peer - Readers of this Article have also read:

The ACM Portal is published by the Association for Computing Machinery. Copyright © 2009 ACM, Inc.
Terms of Usage   Privacy Policy   Code of Ethics   Contact Us

Useful downloads: Adobe Acrobat    QuickTime    Windows Media Player    Real Player