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}
}

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 ...

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
UNIX/LINUX/Mac: use mount point /pods8298/... or /cdrom/...

Load The ACM SIGMOD Anthology, Silver Edition, DVD 1, Proceedings. and ...

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
UNIX/LINUX/Mac: use mount point /aDVD1/... or /cdrom/...

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

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
[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)
[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)
[FM82]: Michael J. Fischer, A. Michael: Sacrificing Serializability to Attain High Availability of Data. PODS 1982: 70-75
[Gar83]: Hector Garcia-Molina: Using Semantic Knowledge for Transaction Processing in Distributed Database. ACM Trans. Database Syst. 8(2): 186-213(1983)
[Her87]: Maurice Herlihy: Concurrency versus Availability: Atomic Mechanisms for Replicated Data. ACM Trans. Comput. Syst. 5(3): 249-274(1987)
[HHW89]: ...
[HW87]: Maurice Herlihy, Jeannette M. Wing: Specifying Graceful Degradation in Distributed Systems. PODC 1987: 167-177
[KB90]: ...
[KLS90]: Henry F. Korth, Eliezer Levy, Abraham Silberschatz: A Formal Approach to Recovery by Compensating Transactions. VLDB 1990: 95-106
[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)
[KS88]: Henry F. Korth, Gregory D. Speegle: Formal Model of Correctness Without Serializability. SIGMOD Conference 1988: 379-386
[LBS86]: Nancy A. Lynch, Barbara T. Blaustein, Michael Siegel: Correctness Conditions for Highly Available Replicated Databases. PODC 1986: 11-28
[LLS88]: Rivka Ladin, Barbara Liskov, Liuba Shrira: A Technique for Constructing Highly Available Services. Algorithmica 3: 393-420(1988)
[LLS90]: Rivka Ladin, Barbara Liskov, Liuba Shrira: Lazy Replication: Exploiting the Semantics of Distributed Services. PODC 1990: 43-57
[Lyn83]: Nancy A. Lynch: Multilevel Atomicity - A New Correctness Criterion for Database Concurrency Control. ACM Trans. Database Syst. 8(4): 484-502(1983)
[Pai90]: Robert Paige: Symbolic Finite Differencing - Part I. ESOP 1990: 36-56
[QW86]: Xiaolei Qian, Gio Wiederhold: Knowledge-based Integrity Constraint Validation. VLDB 1986: 3-12
[Sar86]: ...
[SDR88]: ...
[SLJ88]: ...
[SS84]: Peter M. Schwarz, Alfred Z. Spector: Synchronizing Shared Abstract Types. ACM Trans. Comput. Syst. 2(3): 223-250(1984)
[WB84]: Gene T. J. Wuu, Arthur J. Bernstein: Efficient Solutions to the Replicated Log and Dictionart Problems. PODC 1984: 233-242
[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)