ACM SIGMOD Anthology TODS dblp.uni-trier.de

Optimism and Consistency In Partitioned Distributed Database Systems.

Susan B. Davidson: Optimism and Consistency In Partitioned Distributed Database Systems. ACM Trans. Database Syst. 9(3): 456-481(1984)
@article{DBLP:journals/tods/Davidson84,
  author    = {Susan B. Davidson},
  title     = {Optimism and Consistency In Partitioned Distributed Database
               Systems},
  journal   = {ACM Trans. Database Syst.},
  volume    = {9},
  number    = {3},
  year      = {1984},
  pages     = {456-481},
  ee        = {http://doi.acm.org/10.1145/1270.1499, db/journals/tods/Davidson84.html},
  bibsource = {DBLP, http://dblp.uni-trier.de}
}
BibTeX

Abstract

A protocol for transaction processing during partition failures is presented which guarantees mutual consistency between copies of data-items after repair is completed. The protocol is "optimistic" in that transactions are processed without restrictions during failure; conflicts are then detected at repair time using a precedence graph, and are resolved by backing out transactions according to some backout strategy. The resulting database state then corresponds to a serial execution of some subset of transactions run during the failure. Results from simulation and probabilistic modeling show that the optimistic protocol is a reasonable alternative in many cases. Conditions under which the protocol performs well are noted, and suggestions are made as to how performance can be improved. In particular, a backout strategy is presented which takes into account individual transaction costs and attempts to minimize total backout cost. Although the problem of choosing transactions to minimize total backout cost is, in general, NP-complete, the backout strategy is efficient and produces very good results.

Copyright © 1984 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

CDROM Version: Load the CDROM "Volume 3 Issue 1, TODS 1976-1990" and ... DVD Version: Load ACM SIGMOD Anthology DVD 2" and ... BibTeX

References

[1]
Alfred V. Aho, John E. Hopcroft, Jeffrey D. Ullman: The Design and Analysis of Computer Algorithms. Addison-Wesley 1974, ISBN 0-201-00029-6
BibTeX
[2]
Peter Alsberg, J. D. Day: A Principle for Resilient Sharing of Distributed Resources. ICSE 1976: 562-570 BibTeX
[3]
Philip A. Bernstein, James B. Rothnie Jr., Nathan Goodman, Christos H. Papadimitriou: The Concurrency Control Mechanism of SDD-1: A System for Distributed Databases (The Fully Redundant Case). IEEE Trans. Software Eng. 4(3): 154-168(1978) BibTeX
[4]
Philip A. Bernstein, David W. Shipman, Wing S. Wong: Formal Aspects of Serializability in Database Concurrency Control. IEEE Trans. Software Eng. 5(3): 203-216(1979) BibTeX
[5]
...
[6]
...
[7]
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
[8]
M. R. Garey, David S. Johnson: Computers and Intractability: A Guide to the Theory of NP-Completeness. W. H. Freeman 1979, ISBN 0-7167-1044-7
BibTeX
[9]
Hector Garcia-Molina: Elections in a Distributed Computing System. IEEE Trans. Computers 31(1): 48-59(1982) BibTeX
[10]
Hector Garcia-Molina: Using Semantic Knowledge for Transaction Processing in Distributed Database. ACM Trans. Database Syst. 8(2): 186-213(1983) BibTeX
[11]
David K. Gifford: Weighted Voting for Replicated Data. SOSP 1979: 150-162 BibTeX
[12]
Michael Hammer, David W. Shipman: Reliability Mechanisms for SDD-1: A System for Distributed Databases. ACM Trans. Database Syst. 5(4): 431-466(1980) BibTeX
[13]
John E. Hopcroft, Richard M. Karp: An n5/2 Algorithm for Maximum Matchings in Bipartite Graphs. SIAM J. Comput. 2(4): 225-231(1973) BibTeX
[14]
Donald B. Johnson: Finding All the Elementary Circuits of a Directed Graph. SIAM J. Comput. 4(1): 77-84(1975) BibTeX
[15]
...
[16]
...
[17]
Witold Lipski Jr.: On Semantic Issues Connected with Incomplete Information Databases. ACM Trans. Database Syst. 4(3): 262-296(1979) BibTeX
[18]
Nancy A. Lynch: Multilevel Atomicity - A New Correctness Criterion for Database Concurrency Control. ACM Trans. Database Syst. 8(4): 484-502(1983) BibTeX
[19]
Toshimi Minoura, Gio Wiederhold: Resilient Extended True-Copy Token Scheme for a Distributed Database System. IEEE Trans. Software Eng. 8(3): 173-189(1982) BibTeX
[20]
Christos H. Papadimitriou: The serializability of concurrent database updates. J. ACM 26(4): 631-653(1979) BibTeX
[21]
Christos H. Papadimitriou, Kenneth Steiglitz: Combinatorial Optimization: Algorithms and Complexity. Prentice-Hall 1982, ISBN 0-13-152462-3
BibTeX
[22]
Douglas Stott Parker Jr., Gerald J. Popek, Gerard Rudisin, Allen Stoughton, Bruce J. Walker, Evelyn Walton, Johanna M. Chow, David A. Edwards, Stephen Kiser, Charles S. Kline: Detection of Mutual Inconsitency in Distributed Systems. Berkeley Workshop 1981: 172-184 BibTeX
[23]
Douglas Stott Parker Jr., Raimundo A. Ramos: A Distributed File System Architecture Supporting High Availability. Berkeley Workshop 1982: 161-183 BibTeX
[24]
...
[25]
James B. Rothnie Jr., Nathan Goodman: A Survey of Research and Development in Distributed Database Management. VLDB 1977: 48-62 BibTeX
[26]
Richard Edwin Stearns, Philip M. Lewis II, Daniel J. Rosenkrantz: Concurrency Control for Database Systems. FOCS 1976: 19-32 BibTeX
[27]
...
[28]
Irving L. Traiger, Jim Gray, Cesare A. Galtieri, Bruce G. Lindsay: Transactions and Consistency in Distributed Database Systems. ACM Trans. Database Syst. 7(3): 323-342(1982) BibTeX
[29]
...

Referenced by

  1. Shirish Hemant Phatak, B. R. Badrinath: Multiversion Reconciliation for Mobile Databases. ICDE 1999: 582-589
  2. Sanjay Kumar Madria: Timestamps to Detect R-W Conflicts in Mobile Computing. ER Workshops 1998: 242-253
  3. A. B. Stephens, Yelena Yesha, Keith E. Humenik: Optimal Allocation for Partially Replicated Database Systems on Ring Networks. IEEE Trans. Knowl. Data Eng. 6(6): 975-982(1994)
  4. Sushil Jajodia, David Mutchler: Dynamic Voting Algorithms for Maintaining the Consistency of a Replicated Database. ACM Trans. Database Syst. 15(2): 230-280(1990)
  5. Leszek Lilien: Quasi-Partitioning: A New Paradigm for Transaction Execution in Partitioned Distributed Database Systems. ICDE 1989: 546-553
  6. Junguk L. Kim: A Protocol for Consistent Surveillance of a Partitioned Network for Distributed Database Systems. DASFAA 1989: 259-265
  7. Jeffrey D. Ullman: Principles of Database and Knowledge-Base Systems, Volume II. Computer Science Press 1989, ISBN 0-7167-8162-X
    Contents
  8. K. V. S. Ramarao: Commitment in a Partitioned Distributed Database. SIGMOD Conference 1988: 371-378
  9. K. V. S. Ramarao: Transaction Atomicity in the Presence of Network Partitions. ICDE 1988: 512-519
  10. Ching-Liang Huang, Victor O. K. Li: A Quorum-Based Commit and Termination Protocol for Distributed Database Systems. ICDE 1988: 136-143
  11. Maurice Herlihy: Dynamic Quorum Adjustment for Partitioned Data. ACM Trans. Database Syst. 12(2): 170-194(1987)
  12. Sushil Jajodia, David Mutchler: Dynamic Voting. SIGMOD Conference 1987: 227-238
  13. Kazuo Sugihara: Concurrency Control Based on Distributed Cycle Detection. ICDE 1987: 267-274
  14. K. V. S. Ramarao: Detection of Mutual Inconsistency in Distributed Databases. ICDE 1987: 405-411
  15. Sushil Jajodia, Catherine Meadows: Mutual Consistency in Decentralized Distributed Systems. ICDE 1987: 396-404
  16. Sushil Jajodia: Managing Replicated Files in Partitioned Distributed Database Systems. ICDE 1987: 412-418
  17. Hector Garcia-Molina, Boris Kogan: Achieving High Availability in Distributed Databases. ICDE 1987: 430-440
  18. Philip A. Bernstein, Vassos Hadzilacos, Nathan Goodman: Concurrency Control and Recovery in Database Systems. Addison-Wesley 1987, ISBN 0-201-10715-5
    Contents
  19. Amr El Abbadi, Dale Skeen, Flaviu Cristian: An Efficient, Fault-Tolerant Protocol for Replicated Data Management. PODS 1985: 215-229
BibTeX
ACM SIGMOD Anthology - DBLP: [Home | Search: Author, Title | Conferences | Journals]
TODS, ACM SIGMOD Anthology: Copyright © by ACM (info@acm.org), Corrections: anthology@acm.org
DBLP: Copyright © by Michael Ley (ley@uni-trier.de), last change: Tue Jun 24 18:38:55 2008