Replication, Consistency, and Practicality: Are These Mutually Exclusive?

Todd A. Anderson, Yuri Breitbart, Henry F. Korth, Avishai Wool: Replication, Consistency, and Practicality: Are These Mutually Exclusive? SIGMOD Conference 1998: 484-495

@inproceedings{DBLP:conf/sigmod/AndersonBKW98,
  author    = {Todd A. Anderson and
               Yuri Breitbart and
               Henry F. Korth and
               Avishai Wool},
  editor    = {Laura M. Haas and
               Ashutosh Tiwary},
  title     = {Replication, Consistency, and Practicality: Are These Mutually
               Exclusive?},
  booktitle = {SIGMOD 1998, Proceedings ACM SIGMOD International Conference
               on Management of Data, June 2-4, 1998, Seattle, Washington, USA},
  publisher = {ACM Press},
  year      = {1998},
  isbn      = {0-89791-995-5},
  pages     = {484-495},
  ee        = {http://doi.acm.org/10.1145/276304.276347, db/conf/sigmod/AndersonBKW98.html},
  crossref  = {DBLP:conf/sigmod/98},
  bibsource = {DBLP, http://dblp.uni-trier.de}
}

BibTeX

Abstract

Previous papers have postulated that traditional schemes for the management of replicated data are doomed to failure in practice due to a quartic (or worse) explosion in the probability of deadlocks. In this paper, we present results of a simulation study for three recently introduced protocols that guarantee global serializability and transaction atomicity without resorting to the two-phase commit protocol. The protocols analyzed in this paper include a global locking protocol [10], a ``pessimistic'' protocol based on a replication graph [5], and an ``optimistic'' protocol based on a replication graph [7]. The results of the study show a wide range of practical applicability for the lazy replica-update approach employed in these protocols. We show that under reasonable contention conditions and sufficiently high transaction rate, both replication-graph-based protocols outperform the global locking protocol. The distinctions among the protocols in terms of performance are significant. For example, an offered load where 70% - 80% of transactions under the global locking protocol were aborted, only 10% of transactions were aborted under the protocols based on the replication graph. The results of the study suggest that protocols based on a replication graph offer practical techniques for replica management. However, it also shows that performance deteriorates rapidly and dramatically when transaction throughput reaches a saturation point.

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

ACM SIGMOD DiSC

CDROM Version: Load the CDROM "DiSC, Volume 1 Number 1" 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
Mac: Click here
UNIX/LINUX: mount the CD and click on the path of your mount point:
/Anthology/Disc99_1 or /cdrom

Online Version (ACM WWW Account required): Full Text in PDF Format

ACM SIGMOD Anthology

DVD Version: Load ACM SIGMOD Anthology DVD 1" 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
Mac: Click here
UNIX/LINUX: mount the DVD and click on the path of your mount point:
/Anthology/aDVD1 or /dvd

BibTeX

Printed Edition

Laura M. Haas, Ashutosh Tiwary (Eds.): SIGMOD 1998, Proceedings ACM SIGMOD International Conference on Management of Data, June 2-4, 1998, Seattle, Washington, USA. ACM Press 1998, ISBN 0-89791-995-5 BibTeX , SIGMOD Record 27(2), June 1998
Contents

Online Edition: ACM SIGMOD

[Abstract]
[Full Text (Postscript)]

References

[1]: Divyakant Agrawal, Amr El Abbadi, Robert C. Steinke: Epidemic Algorithms in Replicated Databases (Extended Abstract). PODS 1997: 161-172 BibTeX
[2]: Philip A. Bernstein, Vassos Hadzilacos, Nathan Goodman: Concurrency Control and Recovery in Database Systems. Addison-Wesley 1987, ISBN 0-201-10715-5
Contents BibTeX
[3]: Yuri Breitbart, Hector Garcia-Molina, Abraham Silberschatz: Overview of Multidatabase Transaction Management. VLDB J. 1(2): 181-239(1992) BibTeX
[4]: Yuri Breitbart, Dimitrios Georgakopoulos, Marek Rusinkiewicz, Abraham Silberschatz: On Rigorous Transaction Scheduling. IEEE Trans. Software Eng. 17(9): 954-960(1991) BibTeX
[5]: Yuri Breitbart, Henry F. Korth: Replication and Consistency: Being Lazy Helps Sometimes. PODS 1997: 173-184 BibTeX
[6]: ...
[7]: ...
[8]: Parvathi Chundi, Daniel J. Rosenkrantz, S. S. Ravi: Deferred Updates and Data Placement in Distributed Databases. ICDE 1996: 469-476 BibTeX
[9]: ...
[10]: Jim Gray, Pat Helland, Patrick E. O'Neil, Dennis Shasha: The Dangers of Replication and a Solution. SIGMOD Conference 1996: 173-182 BibTeX
[11]: ...
[12]: Jim Gray, Andreas Reuter: Transaction Processing: Concepts and Techniques. Morgan Kaufmann 1993, ISBN 1-55860-190-2
Contents BibTeX
[13]: ...
[14]: ...
[15]: ...
[16]: Calton Pu, Avraham Leff: Replica Control in Distributed Systems: An Asynchronous Approach. SIGMOD Conference 1991: 377-386 BibTeX
[17]: Jeff Sidell, Paul M. Aoki, Adam Sah, Carl Staelin, Michael Stonebraker, Andrew Yu: Data Replication in Mariposa. ICDE 1996: 485-494 BibTeX

Referenced by

Bettina Kemme, Gustavo Alonso: Don't Be Lazy, Be Consistent: Postgres-R, A New Way to Implement Database Replication. VLDB 2000: 134-143
Yuri Breitbart, Raghavan Komondoor, Rajeev Rastogi, S. Seshadri, Abraham Silberschatz: Update Propagation Protocols For Replicated Databases. SIGMOD Conference 1999: 97-108
Matthias Nicola, Matthias Jarke: Increasing the Expressiveness of Analytical Performance Models for Replicated Databases. ICDT 1999: 131-149
Avishai Wool: Quorum Systems in Replicated Databases: Science or Fiction? IEEE Data Eng. Bull. 21(4): 3-11(1998)

BibTeX

ACM SIGMOD Anthology - DBLP: [Home | Search: Author, Title | Conferences | Journals]