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

Epidemic Algorithms in Replicated Databases (Extended Abstract).

Divyakant Agrawal, Amr El Abbadi, Robert C. Steinke: Epidemic Algorithms in Replicated Databases (Extended Abstract). PODS 1997: 161-172
@inproceedings{DBLP:conf/pods/AgrawalAS97,
  author    = {Divyakant Agrawal and
               Amr El Abbadi and
               Robert C. Steinke},
  title     = {Epidemic Algorithms in Replicated Databases (Extended Abstract)},
  booktitle = {Proceedings of the Sixteenth ACM SIGACT-SIGMOD-SIGART Symposium
               on Principles of Database Systems, May 12-14, 1997, Tucson, Arizona},
  publisher = {ACM Press},
  year      = {1997},
  isbn      = {0-89791-910-6},
  pages     = {161-172},
  ee        = {http://doi.acm.org/10.1145/263661.263680, db/conf/pods/AgrawalAS97.html},
  crossref  = {DBLP:conf/pods/97},
  bibsource = {DBLP, http://dblp.uni-trier.de}
}
BibTeX

Abstract

We present a family of epidemic algorithms for maintaining replicated data in a transactional framework. The algorithms are based on the causal delivery of log records where each record corresponds to one transaction instead of one operation. The fist algorithm in this family is a pessimistic protocol that ensures serializability and guarantees strict executions. Since we expect the epidemic algorithms to be used in environments with low probability of conflicts among transactions, we develop a variant of the pessimistic algorithm in which locks are released as soon as transactions finish their execution locally. However, this optimistic releasing of locks introduces the possibility of cascading aborts while ensuring serializable executions. The last member of this family of epidemic algorithms is motivated from the need for asynchronous replication solutions that are being increasingly used in commercial systems. The protocol is optimistic in that transactions commit as soon as they terminate locally and inconsistencies are detected asynchronously as the effects of committed transactions propagate through the system.

Copyright © 1997 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 ... Load The ACM SIGMOD Anthology, Silver Edition, DVD 1, Proceedings. and ... BibTeX

Printed Edition

Proceedings of the Sixteenth ACM SIGACT-SIGMOD-SIGART Symposium on Principles of Database Systems, May 12-14, 1997, Tucson, Arizona. ACM Press 1997, ISBN 0-89791-910-6
Contents BibTeX

Online Edition: ACM Digital Library

[Index Terms]
[Full Text in PDF Format, 1557 KB]

References

[AE90a]
Divyakant Agrawal, Amr El Abbadi: Integrating Security with Fault-Tolerant Distributed Databases. Comput. J. 33(1): 71-78(1990) BibTeX
[AE90b]
Divyakant Agrawal, Amr El Abbadi: Storage Efficient Replicated Databases. IEEE Trans. Knowl. Data Eng. 2(3): 342-352(1990) BibTeX
[AM83]
James E. Allchin, Martin S. McKendry: Synchronization and Recovery of Actions. PODC 1983: 31-44 BibTeX
[AM91]
Divyakant Agrawal, A. Malpani: Efficient Dissemination of Information in Computer Networks. Comput. J. 34(6): 534-541(1991) BibTeX
[BHG87]
Philip A. Bernstein, Vassos Hadzilacos, Nathan Goodman: Concurrency Control and Recovery in Database Systems. Addison-Wesley 1987, ISBN 0-201-10715-5
Contents BibTeX
[DGH+87]
Alan J. Demers, Daniel H. Greene, Carl Hauser, Wes Irish, John Larson, Scott Shenker, Howard E. Sturgis, Daniel C. Swinehart, Douglas B. Terry: Epidemic Algorithms for Replicated Database Maintenance. PODC 1987: 1-12 BibTeX
[FM82]
Michael J. Fischer, A. Michael: Sacrificing Serializability to Attain High Availability of Data. PODS 1982: 70-75 BibTeX
[GHOS96]
Jim Gray, Pat Helland, Patrick E. O'Neil, Dennis Shasha: The Dangers of Replication and a Solution. SIGMOD Conference 1996: 173-182 BibTeX
[Gif79]
David K. Gifford: Weighted Voting for Replicated Data. SOSP 1979: 150-162 BibTeX
[Had88]
Vassos Hadzilacos: A theory of reliability in database systems. J. ACM 35(1): 121-145(1988) BibTeX
[HHW89]
...
[JMM96]
H. V. Jagadish, Alberto O. Mendelzon, Inderpal Singh Mumick: Managing Rule Conflicts in an Active Database. PODS 1996: 192-201 BibTeX
[KBH+88]
...
[Lam78]
Leslie Lamport: Time, Clocks, and the Ordering of Events in a Distributed System. Commun. ACM 21(7): 558-565(1978) BibTeX
[LL86]
Barbara Liskov, Rivka Ladin: Highly-Available Distributed Service and Fault-Tolerant Distributed Garbage Collection. PODC 1986: 29-39 BibTeX
[Mat89]
...
[Ora]
...
[RGK96]
Michael Rabinovich, Narain H. Gehani, Alex Kononov: Scalable Update Propagation in Epidemic Replicated Databases. EDBT 1996: 207-222 BibTeX
[SA93]
O. T. Satyanarayanan, Divyakant Agrawal: Efficient Execution of Read-Only Transactions in Replicated Multiversion Databases. IEEE Trans. Knowl. Data Eng. 5(5): 859-871(1993) BibTeX
[Sch82]
Fred B. Schneider: Synchronization in Distributed Programs. ACM Trans. Program. Lang. Syst. 4(2): 125-148(1982) BibTeX
[Ske82]
Dale Skeen: Nonblocking Commit Protocols. SIGMOD Conference 1981: 133-142 BibTeX
[Ste97]
...
[Sto79]
Michael Stonebraker: Concurrency Control and Consistency of Multiple Copies of Data in Distributed INGRES. IEEE Trans. Software Eng. 5(3): 188-194(1979) BibTeX
[TDP+94]
...
[Tho79]
Robert H. Thomas: A Majority Consensus Approach to Concurrency Control for Multiple Copy Databases. ACM Trans. Database Syst. 4(2): 180-209(1979) BibTeX
[TTP+95]
Douglas B. Terry, Marvin Theimer, Karin Petersen, Alan J. Demers, Mike Spreitzer, Carl Hauser: Managing Update Conflicts in Bayou, a Weakly Connected Replicated Storage System. SOSP 1995: 172-183 BibTeX
[WB84]
Gene T. J. Wuu, Arthur J. Bernstein: Efficient Solutions to the Replicated Log and Dictionart Problems. PODC 1984: 233-242 BibTeX

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. Lingli Ding, Xin Zhang, Elke A. Rundensteiner: The MRE Wrapper Approach: Enabling Incremental View Maintenance of Data Warehouses Defined on Multi-Relation Information Sources. DOLAP 1999: 30-35
  3. Michael Rabinovich: Issues in Web Content Replication. IEEE Data Eng. Bull. 21(4): 21-29(1998)
  4. Todd A. Anderson, Yuri Breitbart, Henry F. Korth, Avishai Wool: Replication, Consistency, and Practicality: Are These Mutually Exclusive? SIGMOD Conference 1998: 484-495
BibTeX
ACM SIGMOD Anthology - DBLP: [Home | Search: Author, Title | Conferences | Journals]
ACM SIGMOD Anthology: Copyright © by ACM (info@acm.org), Corrections: anthology@acm.org
DBLP: Copyright © by Michael Ley (ley@uni-trier.de), last change: Sat May 16 23:34:17 2009