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

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

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 ... Online Version (ACM WWW Account required): Full Text in PDF Format

ACM SIGMOD Anthology

DVD Version: Load ACM SIGMOD Anthology DVD 1" and ...

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

Referenced by

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

Copyright © Mon Nov 2 21:12:27 2009 by Michael Ley (ley@uni-trier.de)