Digital Symposium Collection 2000

Fast Algorithms for Maintaining Replica Consistency in Lazy Master Replicated Databases Esther Pacitti, Pascale Minet, and Eric Simon   View Paper (PDF)   Return to Distributed Databases Note: The quality of the PDF contained herein reflects that of the material supplied to the DiSC'00 Production Team. Abstract In a lazy master replicated database, a transaction can commit after updating one replica copy at some master node. After the transaction commits, the updates are propagated towards the other replicas, which are updated in separate refresh transactions. A central problem is the design of algorithms that maintain replica's consistency while minimizing the performance degeneration due to the synchronization of refresh transactions. We propose a simple and general refreshment algorithm that solves this problem and we prove its correctness. We then present two main optimizations. One is based on specific properties of replicas' topology. The other uses an immediate update propagation strategy. Our performace evaluation demonstrates the effectiveness of the optimization. References Note: References link to DBLP on the Web. [1] Gustavo Alonso , Amr El Abbadi : Partitioned Data Objects in Distributed Databases. Distributed and Parallel Databases 3(1) : 5-35(1995) [2] Divyakant Agrawal , Gustavo Alonso , Amr El Abbadi , Ioana Stanoi : Exploiting Atomic Broadcast in Replicated Databases (Extended Abstract). Euro-Par 1997 : 496-503 [3] Rafael Alonso , Daniel Barbará , Hector Garcia-Molina : Data Caching Issues in an Information Retrieval System. TODS 15(3) : 359-384(1990) [4] Philip A. Bernstein , Eric Newcomer: Principles of Transaction Processing for Systems Professionals. Morgan Kaufmann 1996, ISBN 1-55860-415-4 [5] Surajit Chaudhuri , Umeshwar Dayal : An Overview of Data Warehousing and OLAP Technology. SIGMOD Record 26(1) : 65-74(1997) [6] Parvathi Chundi , Daniel J. Rosenkrantz , S. S. Ravi : Deferred Updates and Data Placement in Distributed Databases. ICDE 1996 : 469-476 [7] Stefano Ceri , Jennifer Widom : Managing Semantic Heterogeneity with Production Rules and Persistent Queues. VLDB 1993 : 108-119 [8] Lyman Do , Pamela Drew : The Management of Interdependent Asynchronous Transactions in Heterogeneous Database Environments. DASFAA 1995 : 16-25 [9] Alan R. Downing , Ira B. Greenberg , Jon M. Peha : OSCAR: A System for Weak-Consistency Replication. Workshop on the Management of Replicated Data 1990 : 26-30 [10] Jim Gray , Pat Helland , Patrick E. O'Neil , Dennis Shasha : The Dangers of Replication and a Solution. SIGMOD Conf. 1996 : 173-182 [11] Laurent George , Pascale Minet : A FIFO Worst Case Analysis for a Hard Real-Time Distributed Problem with Consistency Constraints. ICDCS 1997 : 0- [12] ... [13] Ashish Gupta , Inderpal Singh Mumick , V. S. Subrahmanian : Maintaining Views Incrementally. SIGMOD Conference 1993 : 157-166 [14] Rainer Gallersdörfer , Matthias Nicola : Improving Performance in Replicated Databases through Relaxed Coherency. VLDB 1995 : 445-456 [15] ... [16] Jim Gray , Andreas Reuter : Transaction Processing: Concepts and Techniques. Morgan Kaufmann 1993, ISBN 1-55860-190-2 Contents [17] Paul W. P. J. Grefen , Jennifer Widom : Protocols for Integrity Constraint Checking in Federated Databases. Distributed and Parallel Databases 5(4) : 327-355(1997) [18] ... [19] Bettina Kemme , Gustavo Alonso : A Suite of Database Replication Protocols based on Group Communication Primitives. ICDCS 1998 : 156-163 [20] Bo Kähler , Oddvar Risnes : Extending Logging for Database Snapshot Refresh. VLDB 1987 : 389-398 [21] M. Tamer Özsu , Patrick Valduriez : Principles of Distributed Database Systems, Second Edition. Prentice-Hall 1999 [22] ... [23] Esther Pacitti , Eric Simon , Rubens N. Melo : Improving Data Freshness in Lazy Master Schemes. ICDCS 1998 : 164-171 [24] Ioana Stanoi , Divyakant Agrawal , Amr El Abbadi : Using Broadcast Primitives in Replicated Databases. ICDCS 1998 : 148-155 [25] Sunil K. Sarin , Charles W. Kaufman , Janet E. Somers : Using History Information to Process Delayed Database Updates. VLDB 1986 : 71-78 [26] Amit P. Sheth , Marek Rusinkiewicz : Management of Interdependent Data: Specifying Dependency and Consistency Requirements. Workshop on the Management of Replicated Data 1990 : 133-136 [27] ... [28] 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 [29] Yue Zhuge , Hector Garcia-Molina , Joachim Hammer , Jennifer Widom : View Maintenance in a Warehousing Environment. SIGMOD Conference 1995 : 316-327 BIBTEX @inproceedings{DBLP:conf/vldb/PacittMS99,   author    = {Esther Pacitti and                 Pascale Minet and                 Eric Simon},    editor    = {Malcolm P. Atkinson and                 Maria E. Orlowska and                 Patrick Valduriez and                 Stanley B. Zdonik and                 Michael L. Brodie},    title     = {Fast Algorithms for Maintaining Replica Consistency in Lazy Master                 Replicated Databases},    booktitle = {VLDB'99, Proceedings of 25th International Conference on Very                 Large Data Bases, September 7-10, 1999, Edinburgh, Scotland,                 UK},    publisher = {Morgan Kaufmann},    year      = {1999},    isbn      = {1-55860-615-5},    pages     = {126-137},    crossref  = {DBLP:conf/vldb/99},    bibsource = {DBLP, http://dblp.uni-trier.de} } }, Copyright(C) 2000 ACM