ACM SIGMOD Anthology TODS dblp.uni-trier.de

Bounded Ignorance: A Technique for Increasing Concurrency in a Replicated System.

Narayanan Krishnakumar, Arthur J. Bernstein: Bounded Ignorance: A Technique for Increasing Concurrency in a Replicated System. ACM Trans. Database Syst. 19(4): 586-625(1994)
@article{DBLP:journals/tods/KrishnakumarB94,
  author    = {Narayanan Krishnakumar and
               Arthur J. Bernstein},
  title     = {Bounded Ignorance: A Technique for Increasing Concurrency in
               a Replicated System},
  journal   = {ACM Trans. Database Syst.},
  volume    = {19},
  number    = {4},
  year      = {1994},
  pages     = {586-625},
  ee        = {http://doi.acm.org/10.1145/195664.195670, db/journals/tods/KrishnakumarB94.html},
  bibsource = {DBLP, http://dblp.uni-trier.de}
}
BibTeX

Abstract

Databases are replicated to improve performance and availability. 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 article, 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, 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 replicated databases in N-ignorant systems. 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. Finally, we generalize the notion of N-ignorance to a matrix of ignorance for the purpose of higher concurrency.

Copyright © 1994 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 2, TODS 1991-1995, TKDE 1989-1992" and ... DVD Version: Load ACM SIGMOD Anthology DVD 2" and ... BibTeX

Online Edition: ACM Digital Library

[Abstract, Index Terms and Review]
[Full Text in PDF Format, 2769 KB]

References

[Agrawal and Malpani 1991]
Divyakant Agrawal, A. Malpani: Efficient Dissemination of Information in Computer Networks. Comput. J. 34(6): 534-541(1991) BibTeX
[Alonso et al. 1988]
Rafael Alonso, Daniel Barbará, Hector Garcia-Molina, Soraya Abad: Quasi-Copies: Efficient Data Sharing for Information Retrieval Systems. EDBT 1988: 443-468 BibTeX
[Barbará and Hector Garcia-Molina 1992]
Daniel Barbará, Hector Garcia-Molina: The Demarcation Protocol: A Technique for Maintaining Linear Arithmetic Constraints in Distributed Database Systems. EDBT 1992: 373-388 BibTeX
[Bernstein et al. 1987]
Philip A. Bernstein, Vassos Hadzilacos, Nathan Goodman: Concurrency Control and Recovery in Database Systems. Addison-Wesley 1987, ISBN 0-201-10715-5
Contents BibTeX
[Birman et al. 1991]
Kenneth P. Birman, André Schiper, Pat Stephenson: Lightweigt Causal and Atomic Group Multicast. ACM Trans. Comput. Syst. 9(3): 272-314(1991) BibTeX
[Birrell et al. 1982]
Andrew Birrell, Roy Levin, Roger M. Needham, Michael D. Schroeder: Grapevine: An Exercise in Distributed Computing. Commun. ACM 25(4): 260-274(1982) BibTeX
[Durfee et al. 1987]
...
[Elmagarmid 1991]
...
[Eswaran et al. 1976]
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
[Farrag and Özsu 1990]
Abdel Aziz Farrag, M. Tamer Özsu: Using Semantic Knowledge of Transactions to Increase Concurrency. ACM Trans. Database Syst. 14(4): 503-525(1989) BibTeX
[Fischer and Michael 1982]
Michael J. Fischer, A. Michael: Sacrificing Serializability to Attain High Availability of Data. PODS 1982: 70-75 BibTeX
[Garcia-Molina 1983]
Hector Garcia-Molina: Using Semantic Knowledge for Transaction Processing in Distributed Database. ACM Trans. Database Syst. 8(2): 186-213(1983) BibTeX
[Garcia-Molina et al. 1991]
Hector Garcia-Molina, Dieter Gawlick, Johannes Klein, Karl Kleissner, Kenneth Salem: Modeling Long-Running Activities as Nested Sagas. IEEE Data Eng. Bull. 14(1): 14-18(1991) BibTeX
[Golding 1992]
...
[Gray 1978]
Jim Gray: Notes on Data Base Operating Systems. Advanced Course: Operating Systems 1978: 393-481 BibTeX
[Heddaya et al. 1989]
...
[Herlihy 1990]
Maurice Herlihy: Apologizing Versus Asking Permission: Optimistic Concurrency Control for Abstract Data Types. ACM Trans. Database Syst. 15(1): 96-124(1990) BibTeX
[Herlihy 1987]
Maurice Herlihy: Concurrency versus Availability: Atomic Mechanisms for Replicated Data. ACM Trans. Comput. Syst. 5(3): 249-274(1987) BibTeX
[Herlihy and Weihl 1988]
Maurice Herlihy, William E. Weihl: Hybrid Concurrency Control for Abstract Data Types. PODS 1988: 201-210 BibTeX
[Herlihy and Wing 1987]
Maurice Herlihy, Jeannette M. Wing: Specifying Graceful Degradation in Distributed Systems. PODC 1987: 167-177 BibTeX
[Herman 1983]
...
[Jefferson 1985]
David R. Jefferson: Virtual Time. ACM Trans. Program. Lang. Syst. 7(3): 404-425(1985) BibTeX
[Kim et al. 1989]
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
[Korth and Speegle 1988]
Henry F. Korth, Gregory D. Speegle: Formal Model of Correctness Without Serializability. SIGMOD Conference 1988: 379-386 BibTeX
[Korth et al. 1988]
...
[Korth et al. 1990]
Henry F. Korth, Eliezer Levy, Abraham Silberschatz: A Formal Approach to Recovery by Compensating Transactions. VLDB 1990: 95-106 BibTeX
[Krishnakumar 1992]
...
[Krishnakumar 1991]
Narayanan Krishnakumar: On Computing Serial Dependency Relations. J. Comput. Syst. Sci. 49(2): 175-188(1994) BibTeX
[Krishnakumar and Bernstein 1992]
Narayanan Krishnakumar, Arthur J. Bernstein: High Throughput Escrow Algorithms for Replicated Databases. VLDB 1992: 175-186 BibTeX
[Krishnakumar and Bernstein 1990]
...
[Ladin et al. 1990]
Rivka Ladin, Barbara Liskov, Liuba Shrira: Lazy Replication: Exploiting the Semantics of Distributed Services. PODC 1990: 43-57 BibTeX
[Lamport 1978]
Leslie Lamport: Time, Clocks, and the Ordering of Events in a Distributed System. Commun. ACM 21(7): 558-565(1978) BibTeX
[Levy et al. 1991]
Eliezer Levy, Henry F. Korth, Abraham Silberschatz: A Theory of Relaxed Atomicity (Extended Abstract). PODC 1991: 95-109 BibTeX
[Ladin et al. 1988]
Rivka Ladin, Barbara Liskov, Liuba Shrira: A Technique for Constructing Highly Available Services. Algorithmica 3: 393-420(1988) BibTeX
[Lynch 1983]
Nancy A. Lynch: Multilevel Atomicity - A New Correctness Criterion for Database Concurrency Control. ACM Trans. Database Syst. 8(4): 484-502(1983) BibTeX
[Lynch et al. 1986]
Nancy A. Lynch, Barbara T. Blaustein, Michael Siegel: Correctness Conditions for Highly Available Replicated Databases. PODC 1986: 11-28 BibTeX
[O'Neil 1986]
Patrick E. O'Neil: The Escrow Transactional Method. ACM Trans. Database Syst. 11(4): 405-430(1986) BibTeX
[Paige 1990]
Robert Paige: Symbolic Finite Differencing - Part I. ESOP 1990: 36-56 BibTeX
[Pu and Leff 1991]
...
[Qian and Wiederhold 1986]
Xiaolei Qian, Gio Wiederhold: Knowledge-based Integrity Constraint Validation. VLDB 1986: 3-12 BibTeX
[Reuter and Wächter 1991]
Andreas Reuter, Helmut Wächter: The ConTract Model. IEEE Data Eng. Bull. 14(1): 39-43(1991) BibTeX
[Rusinkiewicz and Sheth 1991]
Marek Rusinkiewicz, Amit P. Sheth: Polytransactions for Managing Independent Data. IEEE Data Eng. Bull. 14(1): 44-48(1991) BibTeX
[Rusinkiewicz et al. 1991]
...
[Sarin 1986]
Sunil K. Sarin: Robust Application Design in Highly Available Distributed Databases. Symposium on Reliability in Distributed Software and Database Systems 1986: 87-94 BibTeX
[Sarin et al. 1988]
...
[Sarin et al. 1986]
Sunil K. Sarin, Charles W. Kaufman, Janet E. Somers: Using History Information to Process Delayed Database Updates. VLDB 1986: 71-78 BibTeX
[Sha et al. 1988]
Lui Sha, John P. Lehoczky, E. Douglas Jensen: Modular Concurrency Control and Failure Recovery. IEEE Trans. Computers 37(2): 146-159(1988) BibTeX
[Sheth et al. 1991]
...
[Skeen 1982]
...
[Verjus 1983]
...
[Weihl 1989]
William E. Weihl: Local Atomicity Properties: Modular Concurrency Control for Abstract Data Types. ACM Trans. Program. Lang. Syst. 11(2): 249-283(1989) BibTeX
[Weihl 1988]
William E. Weihl: Commutativity-Based Concurrency Control for Abstract Data Types. IEEE Trans. Computers 37(12): 1488-1505(1988) BibTeX
[Weikum and Schek 1991]
Gerhard Weikum, Hans-Jörg Schek: Multi-Level Transactions and Open Nested Transactions. IEEE Data Eng. Bull. 14(1): 60-64(1991) BibTeX
[Wong and Agrawal 1992]
Man Hon Wong, Divyakant Agrawal: Tolerating Bounded Inconsistency for Increasing Concurrency in Database Systems. PODS 1992: 236-245 BibTeX
[Wuu and Bernstein 1984]
Gene T. J. Wuu, Arthur J. Bernstein: Efficient Solutions to the Replicated Log and Dictionart Problems. PODC 1984: 233-242 BibTeX

Referenced by

  1. Haifeng Yu, Amin Vahdat: Efficient Numerical Error Bounding for Replicated Network Services. VLDB 2000: 123-133
  2. Alexander Thomasian: Concurrency Control: Methods, Performance, and Analysis. ACM Comput. Surv. 30(1): 70-119(1998)
  3. Kun-Lung Wu, Philip S. Yu, Calton Pu: Divergence Control Algorithms for Epsilon Serializability. IEEE Trans. Knowl. Data Eng. 9(2): 262-274(1997)
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:39:17 2008