Transactions and Consistency in Distributed Database Systems.

@article{DBLP:journals/tods/TraigerGGL82,
  author    = {Irving L. Traiger and
               Jim Gray and
               Cesare A. Galtieri and
               Bruce G. Lindsay},
  title     = {Transactions and Consistency in Distributed Database Systems},
  journal   = {ACM Trans. Database Syst.},
  volume    = {7},
  number    = {3},
  year      = {1982},
  pages     = {323-342},
  ee        = {http://doi.acm.org/10.1145/319732.319734, db/journals/tods/TraigerGGL82.html},
  bibsource = {DBLP, http://dblp.uni-trier.de}
}

Abstract

The concepts of transaction and of data consistency are defined for a distributed system. The cases of partitioned data, where fragments of a file are stored at multiple nodes, and replicated data, where a file is replicated at several nodes, are discussed. It is argued that the distribution and replication of data should be transparent to the programs which use the data. That is, the programming interface should provide location transparency, replica transparency, concurrency transparency, and failure transparency. Techniques for providing such transparencies are abstracted and discussed.

By extending the notions of system schedule and system clock to handle multiple nodes, it is shown that a distributed system can be modeled as a single sequential execution sequence. This model is then used to discuss simple techniques for implementing the various forms of transparency.

Copyright © 1982 by the ACM, Inc., used by permission. Permission to make digital or hard copies is granted provided that copies are not made or distributed for profit or direct commercial advantage, and that copies show this notice on the first page or initial screen of a display along with the full citation.

Joint ACM SIGMOD / IEEE Computer Society Anthology

• Windows: Click the letter of your CD drive
  A B C D E F G H I J K L M N O P Q R S T U V W X Y Z
• Mac: Click here
• UNIX/LINUX: mount the CD and click on the path of your mount point:
  /Anthology/An3-1 or /cdrom

• Windows: Click the letter of your CD drive
  A B C D E F G H I J K L M N O P Q R S T U V W X Y Z
• Mac: Click here
• UNIX/LINUX: mount the DVD and click on the path of your mount point:
  /Anthology/aDVD2 or /dvd

Report Version

References

[1]

James B. Rothnie Jr., Philip A. Bernstein, Stephen Fox, Nathan Goodman, Michael Hammer, T. A. Landers, Christopher L. Reeve, David W. Shipman, Eugene Wong: Introduction to a System for Distributed Databases (SDD-1). ACM Trans. Database Syst. 5(1): 1-17(1980) BibTeX

[2]

...

[3]

Kapali P. Eswaran, Jim Gray, Raymond A. Lorie, Irving L. Traiger: The Notions of Consistency and Predicate Locks in a Database System. Commun. ACM 19(11): 624-633(1976) BibTeX

[4]

David K. Gifford: Weighted Voting for Replicated Data. SOSP 1979: 150-162 BibTeX

[5]

Jim Gray: Notes on Data Base Operating Systems. Advanced Course: Operating Systems 1978: 393-481 BibTeX

[6]

...

[7]

Leslie Lamport: Time, Clocks, and the Ordering of Events in a Distributed System. Commun. ACM 21(7): 558-565(1978) BibTeX

[8]

...

[9]

Daniel J. Rosenkrantz, Richard Edwin Stearns, Philip M. Lewis II: System Level Concurrency Control for Distributed Database Systems. ACM Trans. Database Syst. 3(2): 178-198(1978) BibTeX

[10]

Richard Edwin Stearns, Philip M. Lewis II, Daniel J. Rosenkrantz: Concurrency Control for Database Systems. FOCS 1976: 19-32 BibTeX

[11]

Michael Stonebraker: Concurrency Control and Consistency of Multiple Copies of Data in Distributed INGRES. IEEE Trans. Software Eng. 5(3): 188-194(1979) BibTeX

[12]

Andrea J. Borr: Transaction Monitoring in ENCOMPASS: Reliable Distributed Transaction Processing. VLDB 1981: 155-165 BibTeX

Referenced by

1. Shailesh Agarwal, Arthur M. Keller, Gio Wiederhold, Krishna Saraswat: Flexible Relation: An Approach for Integrating Data from Multiple, Possibly Inconsistent Databases. ICDE 1995: 495-504
2. Goetz Graefe: Query Evaluation Techniques for Large Databases. ACM Comput. Surv. 25(2): 73-170(1993)
3. Donald D. Chamberlin, Frank B. Schmuck: Dynamic Data Distribution (D³) in a Shared-Nothing Multiprocessor Data Store. VLDB 1992: 163-174
4. Michael J. Carey, Miron Livny: Conflict Detection Tradeoffs for Replicated Data. ACM Trans. Database Syst. 16(4): 703-746(1991)
5. Gomer Thomas, Glenn R. Thompson, Chin-Wan Chung, Edward Barkmeyer, Fred Carter, Marjorie Templeton, Stephen Fox, Berl Hartman: Heterogeneous Distributed Database Systems for Production Use. ACM Comput. Surv. 22(3): 237-266(1990)
6. H. M. Gladney: Data Replicas in Distributed Information Services. ACM Trans. Database Syst. 14(1): 75-97(1989)
7. Michael J. Carey, Miron Livny: Parallelism and Concurrency Control Performance in Distributed Database Machines. SIGMOD Conference 1989: 122-133
8. Abdelsalam Helal, Jagannathan Srinivasan, Bharat K. Bhargava: SETH: A Quorum-Based Database System for Experimentation with Failures. ICDE 1989: 677-684
9. Jeffrey D. Ullman: Principles of Database and Knowledge-Base Systems, Volume II. Computer Science Press 1989, ISBN 0-7167-8162-X
   Contents
10. Jean-François Pons, Jean-François Vilarem: Mixed concurrency control: Dealing with heterogeneity in distributed database systems. VLDB 1988: 445-456
11. Michael J. Carey, Miron Livny: Distributed Concurrency Control Performance: A Study of Algorithms, Distribution, and Replication. VLDB 1988: 13-25
12. H. M. Gladney, D. J. Lorch, R. L. Mattson: A Version Management Method for Distributed Information. ICDE 1987: 570-574
13. Hector Garcia-Molina, Boris Kogan: Achieving High Availability in Distributed Databases. ICDE 1987: 430-440
14. Philip A. Bernstein, Vassos Hadzilacos, Nathan Goodman: Concurrency Control and Recovery in Database Systems. Addison-Wesley 1987, ISBN 0-201-10715-5
    Contents
15. Nick Roussopoulos, Hyunchul Kang: Preliminary Design of ADMS±: A Workstation-Mainframe Integrated Architecture for Database Management Systems. VLDB 1986: 355-364
16. Rakesh Agrawal, David J. DeWitt: Integrated Concurrency Control and Recovery Mechanisms: Design and Performance Evaluation. ACM Trans. Database Syst. 10(4): 529-564(1985)
17. Marco A. Casanova, Arnaldo V. Moura, Luiz Tucherman: On the Correctness of a Local Storage Subsystem. PODS 1985: 123-134
18. Amr El Abbadi, Dale Skeen, Flaviu Cristian: An Efficient, Fault-Tolerant Protocol for Replicated Data Management. PODS 1985: 215-229
19. Susan B. Davidson: Optimism and Consistency In Partitioned Distributed Database Systems. ACM Trans. Database Syst. 9(3): 456-481(1984)
20. Philip A. Bernstein, Nathan Goodman: An Algorithm for Concurrency Control and Recovery in Replicated Distributed Databases. ACM Trans. Database Syst. 9(4): 596-615(1984)
21. Claude Boksenbaum, Michèle Cart, Jean Ferrié, Jean-François Pons: Certification by Intervals of Timestamps in Distributed Database Systems. VLDB 1984: 377-387
22. Hector Garcia-Molina: Using Semantic Knowledge for Transaction Processing in Distributed Database. ACM Trans. Database Syst. 8(2): 186-213(1983)
23. Stefano Ceri, Giuseppe Pelagatti: Correctness of Query Execution Strategies in Distributed Databases. ACM Trans. Database Syst. 8(4): 577-607(1983)
24. Nathan Goodman, Dale Skeen, Arvola Chan, Umeshwar Dayal, Stephen Fox, Daniel R. Ries: A Recovery Algorithm for a Distributed Database System. PODS 1983: 8-15
25. Herbert Kuss: On Totally Ordering Checkpoints in Distributed Data Bases. SIGMOD Conference 1982: 174, 293-302
26. Catriel Beeri, Ron Obermarck: A Resource Class Independent Deadlock Detection Algorithm. VLDB 1981: 166-178
27. Michel E. Adiba: Derived Relations: A Unified Mechanism for Views, Snapshots, and Distributed Data. VLDB 1981: 293-305
28. Bernd Walter: Strategies for Handling Transactions in Distributed Data Base Systems During Recovery. VLDB 1980: 384-389
29. Michel E. Adiba, Bruce G. Lindsay: Database Snapshots. VLDB 1980: 86-91