Implementing atomic actions on decentralized data

Subscribe (Full Service)


	Search: The ACM Digital Library The Guide

	Feedback

Implementing atomic actions on decentralized data

Full text

Pdf (1.44 MB)

Source

ACM Transactions on Computer Systems (TOCS) archive
Volume 1 , Issue 1 (February 1983) table of contents

Pages: 3 - 23

Year of Publication: 1983

ISSN:0734-2071

Author

David P. Reed

Laboratory for Computer Science, Massachussetts Institute of Technology, Cambridge, MA

Publisher

ACM New York, NY, USA

Bibliometrics

Downloads (6 Weeks): 15, Downloads (12 Months): 60, Citation Count: 70

Additional Information:

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/357353.357355 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	G. C. Arens, RECOVERY OF THE SWALLOW REPOSITORY, Massachusetts Institute of Technology, Cambridge, MA, 1981
	2	Russell Atkinson , Carl Hewitt, Synchronization in actor systems, Proceedings of the 4th ACM SIGACT-SIGPLAN symposium on Principles of programming languages, p.267-280, January 17-19, 1977, Los Angeles, California [doi>10.1145/512950.512975]
	3	BERNSTEIN, P.A., SHIPMAN, D.W., ROTHNIE, J.B., AND GOODMAN, N. The concurrency control mechanism of SDD-I: A system for distributed databases (the general case). Tech. Rep. CCA-77- 09, Computer Corporation of America, Cambridge, Mass., Dec. 1977.
	4	Daniel G. Bobrow , Jerry D. Burchfiel , Daniel L. Murphy , Raymond S. Tomlinson, TENEX, a paged time sharing system for the PDP - 10, Communications of the ACM, v.15 n.3, p.135-143, March 1972 [doi>10.1145/361268.361271]
	5	Charles T. Davies, Jr., Recovery semantics for a DB/DC system, Proceedings of the annual conference, p.136-141, August 27-29, 1973, Atlanta, Georgia, United States [doi>10.1145/800192.805694]
	6	DAVIES, C.T. Data processing spheres of control. IBM Syst. J. 17 (1978).
	7	DENNIS, J. First version of a data flow procedure language. Tech. Memo TM-61, M.I.T. Laboratory for Computer Science, Cambridge, Mass., May 1975.
	8	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]
	9	DIJKSTRA, E.~vV. Cooperating sequential processes. In Programming Languages, F. Genuys, Ed., Academic Press, New York, 1968.
	10	K. P. Eswaran , J. N. Gray , R. A. Lorie , I. L. Traiger, The notions of consistency and predicate locks in a database system, Communications of the ACM, v.19 n.11, p.624-633, Nov. 1976 [doi>10.1145/360363.360369]
	11	Jim Gray, Notes on Data Base Operating Systems, Operating Systems, An Advanced Course, p.393-481, January 1978
	12	HOARE, C.A.R. Towards a theory of parallel programming. In Operating Systems Techniques C.A.R. Hoare and R.H. Perrott, Eds., Academic Press, New York, 1973.
	13	JOHNSON, P.R., AND THOMAS, R.H. The maintenance of duplicate databases. ARPANET NWG/ RFC 677, DARPANET, Defense Advanced Research Agency, Washington, D.C., Jan. 1975.
	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	LAMPSON, B., AND STURGIS, H. Crash recovery in a distributed data storage system. To appear.
	16	D. B. Lomet, Process structuring, synchronization, and recovery using atomic actions, Proceedings of an ACM conference on Language design for reliable software, p.128-137, March 28-30, 1977, Raleigh, North Carolina
	17	D. L. Parnas, On the criteria to be used in decomposing systems into modules, Communications of the ACM, v.15 n.12, p.1053-1058, Dec. 1972 [doi>10.1145/361598.361623]
	18	RANDELL, B. System structure for software fault tolerance. IEEE Trans. Softw. Eng. SE-1, 2 (June 1975), 220-232.
	19	D. P. Reed, NAMING AND SYNCHRONIZATION IN A DECENTRALIZED COMPUTER SYSTEM, Massachusetts Institute of Technology, Cambridge, MA, 1978
	20	REED, D.P., AND SVOBODOVA, L. SWALLOW: A distributed data storage system for a local network. In Local Networks for Computer Communications, A. West and P. Janson, Eds., North- Holland, Amsterdam, 1981, pp. 355-373.
	21	STEARNS, R., ET AL. Concurrency control for database systems. In Proc. IEEE Symp. Foundations of Computer Science, (October), IEEE, New York, 1976, pp. 19-32.
	22	L. Svobodova, MANAGEMENT OF OBJECT HISTORIES IN THE SWALLOW REPOSITORY, Massachusetts Institute of Technology, Cambridge, MA, 1980
	23	THOMAS, R.H. A solution to the update problem for multiple copy databases which use distributed control. BBN Rep. 3340, Bait, Beranek, Newman, Cambridge,. Mass., July 1976.

CITED BY 70

	Gregory R. Andrews , Fred B. Schneider, Concepts and Notations for Concurrent Programming, ACM Computing Surveys (CSUR), v.15 n.1, p.3-43, March 1983
	A. Witkowski , K. Chandrakumar , G. Macchio, Concurrent I/O system for the hypercube multiprocessor, Proceedings of the third conference on Hypercube concurrent computers and applications, p.1398-1407, January 1989, Pasadena, California, United States
	Panduranga Rao Adusumilli , Lawrence J. Osborne, An integrated solution for managing replicated data in distributed systems, Proceedings of the 1993 ACM/SIGAPP symposium on Applied computing: states of the art and practice, p.351-357, February 14-16, 1993, Indianapolis, Indiana, United States
	J. Walpole , G. S. Blair , J. Malik , J. R. Nicol, A unifying model for consistent distributed software development environments, ACM SIGPLAN Notices, v.24 n.2, p.183-190, Feb. 1989
	Michael J. Carey , Waleed A. Muhanna, The performance of multiversion concurrency control algorithms, ACM Transactions on Computer Systems (TOCS), v.4 n.4, p.338-378, Nov. 1986
	J. H. Saltzer , D. P. Reed , D. D. Clark, End-to-end arguments in system design, ACM Transactions on Computer Systems (TOCS), v.2 n.4, p.277-288, Nov. 1984
	Michael J. Carey , Miron Livny, Parallelism and concurrency control performance in distributed database machines, ACM SIGMOD Record, v.18 n.2, p.122-133, June 1989
	Maurice Herlihy, Dynamic quorum adjustment for partitioned data, ACM Transactions on Database Systems (TODS), v.12 n.2, p.170-194, June 1987
	Amr El Abbadi , Sam Toueg, The group paradigm for concurrency control, ACM SIGMOD Record, v.17 n.3, p.126-134, June 1988
	Maurice Herlihy, A quorum-consensus replication method for abstract data types, ACM Transactions on Computer Systems (TOCS), v.4 n.1, p.32-53, Feb. 1986
	Arif Merchant , Kun-Lung Wu , Philip S. Yu , Ming-Syan Chen, Performance analysis of dynamic finite versioning for concurrent transaction and query processing, ACM SIGMETRICS Performance Evaluation Review, v.20 n.1, p.103-114, June 1992
	R. Sun , G. Thomas, Performance results on multiversion timestamp concurrency control with predeclared writesets, Proceedings of the sixth ACM SIGACT-SIGMOD-SIGART symposium on Principles of database systems, p.177-184, March 23-25, 1987, San Diego, California, United States
	Eric C. Cooper, Replicated procedure call, Proceedings of the third annual ACM symposium on Principles of distributed computing, p.220-232, August 27-29, 1984, Vancouver, British Columbia, Canada
	Hal Berenson , Phil Bernstein , Jim Gray , Jim Melton , Elizabeth O'Neil , Patrick O'Neil, A critique of ANSI SQL isolation levels, ACM SIGMOD Record, v.24 n.2, p.1-10, May 1995
	David Jefferson , Andrew Witkowski, An approach to performance analysis of timestamp-driven synchronization mechanisms, Proceedings of the third annual ACM symposium on Principles of distributed computing, p.243-253, August 27-29, 1984, Vancouver, British Columbia, Canada
	Paul F. Reynolds, Jr. , Craig Williams , Raymond R. Wagner, Jr., Isotach Networks, IEEE Transactions on Parallel and Distributed Systems, v.8 n.4, p.337-348, April 1997
	Richard W. Watson , Sandy A. Mamrak, Gaining efficiency in transport services by appropriate design and implementation choices, ACM Transactions on Computer Systems (TOCS), v.5 n.2, p.97-120, May 1987
	A. El Abbadi , S. Toueg, Maintaining availability in partitioned replicated databases, ACM Transactions on Database Systems (TODS), v.14 n.2, p.264-290, June 1989
	Ivar Jacobson, Language support for changeable large real time systems, ACM SIGPLAN Notices, v.21 n.11, p.377-384, Nov. 1986
	Kenneth Salem , Héctor García-Molina , Jeannie Shands, Altruistic locking, ACM Transactions on Database Systems (TODS), v.19 n.1, p.117-165, March 1994
	Michael J. Carey , Miron Livny, Conflict detection tradeoffs for replicated data, ACM Transactions on Database Systems (TODS), v.16 n.4, p.703-746, Dec. 1991
	Edwin McKenzie , Richard Snodgrass, Extending the relational algebra to support transaction time, ACM SIGMOD Record, v.16 n.3, p.467-478, Dec. 1987
	Henry F. Korth , Greg Speegle, Formal aspects of concurrency control in long-duration transaction systems using the NT/PV model, ACM Transactions on Database Systems (TODS), v.19 n.3, p.492-535, Sept. 1994
	M. Herlihy, Concurrency and availability as dual properties of replicated atomic data, Journal of the ACM (JACM), v.37 n.2, p.257-278, April 1990
	David R. Jefferson, Virtual time, ACM Transactions on Programming Languages and Systems (TOPLAS), v.7 n.3, p.404-425, July 1985
	Calton Pu , Miu K. Tsang , Kun-Lung Wu , Philip S. Yu, Multiversion divergence control of time fuzziness, Proceedings of the third international conference on Information and knowledge management, p.195-202, November 29-December 02, 1994, Gaithersburg, Maryland, United States
	Maurice Herlihy, Comparing how atomicity mechanisms support replication, Proceedings of the fourth annual ACM symposium on Principles of distributed computing, p.102-110, August 1985, Minaki, Ontario, Canada
	Minwen Ji, Affinity-based management of main memory database clusters, ACM Transactions on Internet Technology (TOIT), v.2 n.4, p.307-339, November 2002
	M. Herlihy, Apologizing versus asking permission: optimistic concurrency control for abstract data types, ACM Transactions on Database Systems (TODS), v.15 n.1, p.96-124, March 1990
	Xiaoying Liu , John A. Miller , Nilesh R. Parate, Transaction management for object-oriented databases: performance advantages of using multiple versions, Proceedings of the 25th annual symposium on Simulation, p.222-231, April 1992, Orlando, Florida, United States
	Liba Svobodova, File servers for network-based distributed systems, ACM Computing Surveys (CSUR), v.16 n.4, p.353-398, Dec. 1984
	Maurice P. Herlihy , Jeannette M. Wing, Linearizability: a correctness condition for concurrent objects, ACM Transactions on Programming Languages and Systems (TOPLAS), v.12 n.3, p.463-492, July 1990
	Andrew S. Tanenbaum , Robbert Van Renesse, Distributed operating systems, ACM Computing Surveys (CSUR), v.17 n.4, p.419-470, Dec. 1985
	Kenneth J. Goldman , Nancy Lynch, Quorum consensus in nested-transaction systems, ACM Transactions on Database Systems (TODS), v.19 n.4, p.537-585, Dec. 1994
	Maurice P. Herlihy , William E. Weihl, Hybrid concurrency control for abstract data types, Proceedings of the seventh ACM SIGACT-SIGMOD-SIGART symposium on Principles of database systems, p.201-210, March 1988, Austin, Texas, United States
	Jean-Pierre Banâtre , Michel Banâtre , Guy Lapalme , Florimond Ployette, The design and building of Enchère, a distributed electronic marketing system, Communications of the ACM, v.29 n.1, p.19-29, Jan. 1986
	Maurice Herlihy, Optimistic concurrency control for abstract data types, Proceedings of the fifth annual ACM symposium on Principles of distributed computing, p.206-217, August 11-13, 1986, Calgary, Alberta, Canada
	Dimitrios Georgakopoulos , Marek Rusinkiewicz , Witold Litwin, Chronological scheduling of transactions with temporal dependencies, The VLDB Journal — The International Journal on Very Large Data Bases, v.3 n.1, p.1-28, January 1994
	Paul M. Bober , Michael J. Carey, Indexing for Multiversion Locking: Alternatives and Performance Evaluation, IEEE Transactions on Knowledge and Data Engineering, v.9 n.1, p.68-84, January 1997
	George T. Heineman, A transaction manager component for cooperative transaction models, Proceedings of the 1993 conference of the Centre for Advanced Studies on Collaborative research: distributed computing, October 24-28, 1993, Toronto, Ontario, Canada
	Ming-Ling Lo , C. V. Ravishankar, A concurrency control protocol for nested transactions, Proceedings of the 1992 conference of the Centre for Advanced Studies on Collaborative research, November 09-12, 1992, Toronto, Ontario, Canada
	Albert Burger , Vijay Kumar, Performance of multiversion concurrency control mechanism in partitioned and partially replicated databases, Proceedings of the 1992 ACM annual conference on Communications, p.189-195, March 03-05, 1992, Kansas City, Missouri, United States
	Kenneth J. Goldman , Nancy A. Lynch, Quorum consensus in nested transaction systems, Proceedings of the sixth annual ACM Symposium on Principles of distributed computing, p.27-41, August 10-12, 1987, Vancouver, British Columbia, Canada
	Linda M. Null , Johnny Wong, The DIAMOND security policy for object-oriented databases, Proceedings of the 1992 ACM/SIGAPP symposium on Applied computing: technological challenges of the 1990's, p.683-690, March 1992, Kansas City, Missouri, United States
	David K. Garnick , A. Toni Cohen, Locality in distributed computations, Proceedings of the 1988 ACM sixteenth annual conference on Computer science, p.335-344, February 1988, Atlanta, Georgia, United States
	L. Chiu , M. T. Liu, High level specification of concurrency control in distributed database systems, Proceedings of the 10th international conference on Software engineering, p.309-317, April 11-15, 1988, Singapore
	Arif Merchant , Kun-Lung Wu , Philip S. Yu , Ming-Syan Chen, Performance Analysis of Dynamic Finite Versioning Schemes: Storage Cost vs. Obsolescence, IEEE Transactions on Knowledge and Data Engineering, v.8 n.6, p.985-1001, December 1996
	David J DeWitt , Randy H Katz , Frank Olken , Leonard D Shapiro , Michael R Stonebraker , David Wood, Implementation techniques for main memory database systems, ACM SIGMOD Record, v.14 n.2, June 1984
	Toshimi Minoura , S. Sitharama Iyengar, Data and Time Abstraction Techniques for Analyzing Multilevel Concurrent Systems, IEEE Transactions on Software Engineering, v.15 n.1, p.47-59, January 1989
	B. Bhargava , J. Riedl, A Model for Adaptable Systems for Transaction Processing, IEEE Transactions on Knowledge and Data Engineering, v.1 n.4, p.433-449, December 1989
	M. Herlihy , M. S. McKendry, Timestamp-Based Orphan Elimination, IEEE Transactions on Software Engineering, v.15 n.7, p.825-831, July 1989
	A. El Abbadi , S. Toueg, The Group Paradigm for Concurrency Control Protocols, IEEE Transactions on Knowledge and Data Engineering, v.1 n.3, p.376-386, September 1989
	Maurice Herlihy, Comparing how atomicity mechanisms support replication, ACM SIGOPS Operating Systems Review, v.20 n.3, p.31-39, July, 1986
	Avigdor Gal , John Mylopoulos, Toward Web-Based Application Management Systems, IEEE Transactions on Knowledge and Data Engineering, v.13 n.4, p.683-702, July 2001
	W. J. Lin , B. Veeravalli, A dynamic object allocation and replication algorithm for distributed systems with centralized control, International Journal of Computers and Applications, v.28 n.1, p.26-34, January 2006
	Jan Pečiva, Active transaction approach for collaborative virtual environments, Proceedings of the 2006 ACM international conference on Virtual reality continuum and its applications, June 14-April 17, 2006, Hong Kong, China
	João Cachopo , António Rito-Silva, Versioned boxes as the basis for memory transactions, Science of Computer Programming, v.63 n.2, p.172-185, 1 December 2006
	Jacob Matthews , Robert Bruce Findler , Paul Graunke , Shriram Krishnamurthi , Matthias Felleisen, Automatically Restructuring Programs for the Web, Automated Software Engineering, v.11 n.4, p.337-364, October 2004
	Sam S. Stone , Kevin M. Woley , Matthew I. Frank, Address-Indexed Memory Disambiguation and Store-to-Load Forwarding, Proceedings of the 38th annual IEEE/ACM International Symposium on Microarchitecture, p.171-182, November 12-16, 2005, Barcelona, Spain
	Michael J. Carey , Miron Livny, Distributed Concurrency Control Performance: A Study of Algorithms, Distribution, and Replication, Proceedings of the 14th International Conference on Very Large Data Bases, p.13-25, August 29-September 01, 1988
	François Llirbat , Eric Simon , Dimitri Tombroff, Using Versions in Update Transactions: Application to Integrity Checking, Proceedings of the 23rd International Conference on Very Large Data Bases, p.96-105, August 25-29, 1997
	David B. Lomet , Betty Salzberg, Exploiting A History Database for Backup, Proceedings of the 19th International Conference on Very Large Data Bases, p.380-390, August 24-27, 1993
	Michael J. Carey , David J. DeWitt , Joel E. Richardson , Eugene J. Shekita, Object and File Management in the EXODUS Extensible Database System, Proceedings of the 12th International Conference on Very Large Data Bases, p.91-100, August 25-28, 1986
	James Aspnes , Alan Fekete , Nancy A. Lynch , Michael Merritt , William E. Weihl, A Theory of Timestamp-Based Concurrency Control for Nested Transactions, Proceedings of the 14th International Conference on Very Large Data Bases, p.431-444, August 29-September 01, 1988
	Henry F. Korth, The Double Life of the Transaction Abstraction: Fundamental Principle and Evolving System Concept, Proceedings of the 21th International Conference on Very Large Data Bases, p.2-6, September 11-15, 1995
	Maurice Herlihy, Optimistic concurrency control for abstract data types, ACM SIGOPS Operating Systems Review, v.21 n.2, p.33-44, April 1987
	Robert L. Bocchino , Vikram S. Adve , Bradford L. Chamberlain, Software transactional memory for large scale clusters, Proceedings of the 13th ACM SIGPLAN Symposium on Principles and practice of parallel programming, February 20-23, 2008, Salt Lake City, UT, USA
	Lin Wujuan , Bharadwaj Veeravalli, Design and analysis of an adaptive object replication algorithm in distributed network systems, Computer Communications, v.31 n.10, p.2005-2015, June, 2008
	Hany E. Ramadan , Indrajit Roy , Maurice Herlihy , Emmett Witchel, Committing conflicting transactions in an STM, Proceedings of the 14th ACM SIGPLAN symposium on Principles and practice of parallel programming, February 14-18, 2009, Raleigh, NC, USA
	Hany E. Ramadan , Christopher J. Rossbach , Emmett Witchel, Dependence-aware transactional memory for increased concurrency, Proceedings of the 2008 41st IEEE/ACM International Symposium on Microarchitecture, p.246-257, November 08-12, 2008