Digital Symposium Collection 2000

Update Propagation Protocols For Replicated Databases Yuri Breitbart, Raghavan Komondoor, Rajeev Rastogi, S. Seshadri, and Abraham Silberschatz   View Paper (PDF)   Return to Recovery and Concurrency Abstract Replication is often used in many distributed systems to provide a higher level of performance, reliability and availability. Lazy replica update protocols, which propagate updates to replicas through independent transactions after the original transaction commits, have become popular with database vendors due to their superior performance characteristics. However, if lazy protocols are used indiscriminately, they can result in non-serializable executions. In this paper, we propose two new lazy update protocols that guarantee serializability but impose a much weaker requirement on data placement than earlier protocols. Further, many naturally occurring distributed systems, like distributed data warehouses, satisfy this requirement. We also extend our lazy update protocols to eliminate all requirements on data placement. The extension is a hybrid protocol that propagates as many updates as possible in a lazy fashion. We implemented our protocols on the Datablitz database system product developed at Bell Labs. We also conducted an extensive performance study which shows that our protocols outperform existing protocols over a wide range of workloads. References Note: References link to DBLP on the Web. [ABKW98] Todd A. Anderson , Yuri Breitbart , Henry F. Korth , Avishai Wool : Replication, Consistency, and Practicality: Are These Mutually Exclusive? SIGMOD Conference 1998 : 484-495 [BK97] Yuri Breitbart , Henry F. Korth : Replication and Consistency: Being Lazy Helps Sometimes. PODS 1997 : 173-184 [BKRSS98] ... [BLRSSS97] Philip Bohannon , Daniel F. Lieuwen , Rajeev Rastogi , Abraham Silberschatz , S. Seshadri , S. Sudarshan : The Architecture of the Dalí Main-Memory Storage Manager. Multimedia Tools and Applications 4(2) : 115-151(1997) [CRR96] Parvathi Chundi , Daniel J. Rosenkrantz , S. S. Ravi : Deferred Updates and Data Placement in Distributed Databases. ICDE 1996 : 469-476 [ENRS97] Guy Even , Joseph Naor , Satish Rao , Baruch Schieber : Fast Approximate Graph Partitioning Algorithms. SODA 1997 : 639-648 [GHKO81] Jim Gray , P. Homan , Henry F. Korth , Ron Obermarck : A Straw Man Analysis of the Probability of Waiting and Deadlock in a Database System. Berkeley Workshop 1981 : 125 [GHOS96] Jim Gray , Pat Helland , Patrick E. O'Neil , Dennis Shasha : The Dangers of Replication and a Solution. SIGMOD Conf. 1996 : 173-182 [GJ79] M. R. Garey , David S. Johnson : Computer and Intractability: A Guide to NP-Completeness. W. H. Freeman 1979, ISBN 0-7167-1044-7 [LMT90] ... [SK80] Abraham Silberschatz , Zvi M. Kedem : Consistency in Hierarchical Database Systems. JACM 27(1) : 72-80(1980) [ST97] ... BIBTEX @inproceedings{DBLP:conf/sigmod/BreitbartKRSS99,   author    = {Yuri Breitbart and                 Raghavan Komondoor and                 Rajeev Rastogi and                 S. Seshadri and                 Abraham Silberschatz},    editor    = {Alex Delis and                 Christos Faloutsos and                 Shahram Ghandeharizadeh},    title     = {Update Propagation Protocols For Replicated Databases},    booktitle = {SIGMOD 1999, Proceedings ACM SIGMOD International Conference                 on Management of Data, June 1-3, 1999, Philadephia, Pennsylvania,                 USA},    publisher = {ACM Press},    year      = {1999},    isbn      = {1-58113-084-8},    pages     = {97-108},    crossref  = {DBLP:conf/sigmod/99},    bibsource = {DBLP, http://dblp.uni-trier.de} } }, Copyright(C) 2000 ACM