ACM SIGMOD Anthology ACM SIGMOD dblp.uni-trier.de

Bounded Ignorance in Replicated Systems.

Narayanan Krishnakumar, Arthur J. Bernstein: Bounded Ignorance in Replicated Systems. PODS 1991: 63-74
@inproceedings{DBLP:conf/pods/KrishnakumarB91,
  author    = {Narayanan Krishnakumar and
               Arthur J. Bernstein},
  title     = {Bounded Ignorance in Replicated Systems},
  booktitle = {Proceedings of the Tenth ACM SIGACT-SIGMOD-SIGART Symposium on
               Principles of Database Systems, May 29-31, 1991, Denver, Colorado},
  publisher = {ACM Press},
  year      = {1991},
  isbn      = {0-89791-430-9},
  pages     = {63-74},
  ee        = {http://doi.acm.org/10.1145/113413.113419, db/conf/pods/KrishnakumarB91.html},
  crossref  = {DBLP:conf/pods/91},
  bibsource = {DBLP, http://dblp.uni-trier.de}
}
BibTeX

Abstract

Databases are replicated to improve performance and the availability of data. The notion of correctness that has commonly been adopted for concurrent access by transactions to shared, possibly replicated, data is serializability. However, serializability may be impractical in high performance applications since it imposes too stringent a restriction on concurrency. When serializability is relaxed, the integrity constraints describing the data may be violated. By allowing bounded violations of the integrity constraints, however, we are able to increase the concurrency of transactions that execute in a replicated environment. In this paper, we introduce the notion of an N-ignorant transaction, which is a transaction that may be ignorant of the results of at most N prior transactions. A system in which all transactions are N-ignorant can have an N+1-fold increase in concurrency over serializable systems, at the expense of bounded violations of its integrity constraints. We present algorithms for implementing N-ignorant replicated databases. We then provide constructive methods for calculating the reachable states in such systems, given the value of N, so that one may assess the maximum liability that is incurred in allowing constraint violation.

Copyright © 1991 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.

Load The ACM SIGMOD Anthology, CDROM Edition, Volume 1-3, PODS '82-'98. and ... Load The ACM SIGMOD Anthology, Silver Edition, DVD 1, Proceedings. and ... BibTeX

Printed Edition

Proceedings of the Tenth ACM SIGACT-SIGMOD-SIGART Symposium on Principles of Database Systems, May 29-31, 1991, Denver, Colorado. ACM Press 1991, ISBN 0-89791-430-9
Contents BibTeX

Online Edition: ACM Digital Library

[Index Terms]
[Full Text in PDF Format, 1085 KB]

References

[ABG88]
Rafael Alonso, Daniel Barbará, Hector Garcia-Molina, Soraya Abad: Quasi-Copies: Efficient Data Sharing for Information Retrieval Systems. EDBT 1988: 443-468 BibTeX
[BG90]
...
[BLNS82]
Andrew Birrell, Roy Levin, Roger M. Needham, Michael D. Schroeder: Grapevine: An Exercise in Distributed Computing. Commun. ACM 25(4): 260-274(1982) BibTeX
[DLC87]
...
[EGLT76]
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
[FM82]
Michael J. Fischer, A. Michael: Sacrificing Serializability to Attain High Availability of Data. PODS 1982: 70-75 BibTeX
[Gar83]
Hector Garcia-Molina: Using Semantic Knowledge for Transaction Processing in Distributed Database. ACM Trans. Database Syst. 8(2): 186-213(1983) BibTeX
[Her87]
Maurice Herlihy: Concurrency versus Availability: Atomic Mechanisms for Replicated Data. ACM Trans. Comput. Syst. 5(3): 249-274(1987) BibTeX
[HHW89]
...
[HW87]
Maurice Herlihy, Jeannette M. Wing: Specifying Graceful Degradation in Distributed Systems. PODC 1987: 167-177 BibTeX
[KB90]
...
[KLS90]
Henry F. Korth, Eliezer Levy, Abraham Silberschatz: A Formal Approach to Recovery by Compensating Transactions. VLDB 1990: 95-106 BibTeX
[KPK89]
June H. Kim, Kyu Ho Park, Myunghwan Kim: A Model of Distributed Control: Dependency and Uncertainty. Inf. Process. Lett. 30(2): 73-77(1989) BibTeX
[KS88]
Henry F. Korth, Gregory D. Speegle: Formal Model of Correctness Without Serializability. SIGMOD Conference 1988: 379-386 BibTeX
[LBS86]
Nancy A. Lynch, Barbara T. Blaustein, Michael Siegel: Correctness Conditions for Highly Available Replicated Databases. PODC 1986: 11-28 BibTeX
[LLS88]
Rivka Ladin, Barbara Liskov, Liuba Shrira: A Technique for Constructing Highly Available Services. Algorithmica 3: 393-420(1988) BibTeX
[LLS90]
Rivka Ladin, Barbara Liskov, Liuba Shrira: Lazy Replication: Exploiting the Semantics of Distributed Services. PODC 1990: 43-57 BibTeX
[Lyn83]
Nancy A. Lynch: Multilevel Atomicity - A New Correctness Criterion for Database Concurrency Control. ACM Trans. Database Syst. 8(4): 484-502(1983) BibTeX
[Pai90]
Robert Paige: Symbolic Finite Differencing - Part I. ESOP 1990: 36-56 BibTeX
[QW86]
Xiaolei Qian, Gio Wiederhold: Knowledge-based Integrity Constraint Validation. VLDB 1986: 3-12 BibTeX
[Sar86]
...
[SDR88]
...
[SLJ88]
...
[SS84]
Peter M. Schwarz, Alfred Z. Spector: Synchronizing Shared Abstract Types. ACM Trans. Comput. Syst. 2(3): 223-250(1984) BibTeX
[WB84]
Gene T. J. Wuu, Arthur J. Bernstein: Efficient Solutions to the Replicated Log and Dictionart Problems. PODC 1984: 233-242 BibTeX
[Wei88]
...
[Wei89]
William E. Weihl: Local Atomicity Properties: Modular Concurrency Control for Abstract Data Types. ACM Trans. Program. Lang. Syst. 11(2): 249-283(1989) BibTeX

Referenced by

  1. Haifeng Yu, Amin Vahdat: Efficient Numerical Error Bounding for Replicated Network Services. VLDB 2000: 123-133
  2. Bettina Kemme, Gustavo Alonso: Don't Be Lazy, Be Consistent: Postgres-R, A New Way to Implement Database Replication. VLDB 2000: 134-143
  3. Ouri Wolfson, Sushil Jajodia, Yixiu Huang: An Adaptive Data Replication Algorithm. ACM Trans. Database Syst. 22(2): 255-314(1997)
  4. Jeff Sidell, Paul M. Aoki, Adam Sah, Carl Staelin, Michael Stonebraker, Andrew Yu: Data Replication in Mariposa. ICDE 1996: 485-494
  5. Krithi Ramamritham, Calton Pu: A Formal Characterization of Epsilon Serializability. IEEE Trans. Knowl. Data Eng. 7(6): 997-1007(1995)
  6. Yixiu Huang, Ouri Wolfson: A Competitive Dynamic Data Replication Algorithm. ICDE 1993: 310-317
  7. Narayanan Krishnakumar, Arthur J. Bernstein: High Throughput Escrow Algorithms for Replicated Databases. VLDB 1992: 175-186
  8. Tomasz Imielinski, B. R. Badrinath: Querying in Highly Mobile Distributed Environments. VLDB 1992: 41-52
  9. Ouri Wolfson, Sushil Jajodia: Distributed Algorithms for Dynamic Replication of Data. PODS 1992: 149-163
BibTeX
ACM SIGMOD Anthology - DBLP: [Home | Search: Author, Title | Conferences | Journals]
ACM SIGMOD Anthology: Copyright © by ACM (info@acm.org), Corrections: anthology@acm.org
DBLP: Copyright © by Michael Ley (ley@uni-trier.de), last change: Sat May 16 23:34:02 2009