Replication, Consistency, and Practicality: Are These Mutually Exclusive?
Todd A. Anderson, Yuri Breitbart, Henry F. Korth, Avishai Wool
Full Paper (PDF)

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.

References

References, where available, link to the DBLP on the World Wide Web.

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

@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-955-5},
pages = {484-495},
crossref = {DBLP:conf/sigmod/98},
bibsource = {DBLP, http://dblp.uni-trier.de}
}


DBLP: Copyright ©1999 by Michael Ley (ley@uni-trier.de).