An Efficient, Fault-Tolerant Protocol for Replicated Data Management.

@inproceedings{DBLP:conf/pods/AbbadiSC85,
  author    = {Amr El Abbadi and
               Dale Skeen and
               Flaviu Cristian},
  title     = {An Efficient, Fault-Tolerant Protocol for Replicated Data Management},
  booktitle = {Proceedings of the Fourth ACM SIGACT-SIGMOD Symposium on Principles
               of Database Systems, March 25-27, 1985, Portland, Oregon},
  publisher = {ACM},
  year      = {1985},
  isbn      = {0-89791-153-9},
  pages     = {215-229},
  ee        = {http://doi.acm.org/10.1145/325405.325443, db/conf/pods/AbbadiSC85.html},
  crossref  = {DBLP:conf/pods/85},
  bibsource = {DBLP, http://dblp.uni-trier.de}
}

Abstract

The objective of data replication is to increase data availability in the presence of processor and link failures and to decrease data retrieval costs by reading local or close copies of data. Moreover, concurrent execution of transactions on replicated data bases must be equivalent to the serial execution of the same transactions on non-replicated databases.

We present a pedagogical derivation of a replicated data management protocol which meets the above requirements. The protocol tolerates any number of component omission and performance failures (even when these lead to network partitioning), and handles any number of (possibly simultaneous) processor and link recoveries. It implements the reading of a logical object efficiently - by reading the nearest, available copy. When reads outnumber writes and failures are rare, the protocol performs better than other known protocols.

Copyright © 1985 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.

• Windows: Click the letter of your CD drive
  A B C D E F G H I J K L M N O P Q R S T U V W X Y Z
• UNIX/LINUX/Mac: use mount point /pods8298/... or /cdrom/...

• Windows: Click the letter of your CD drive
  A B C D E F G H I J K L M N O P Q R S T U V W X Y Z
• UNIX/LINUX/Mac: use mount point /aDVD1/... or /cdrom/...

Printed Edition

Online Edition: ACM Digital Library

References

[BGa]

Philip A. Bernstein, Nathan Goodman: Concurrency Control in Distributed Database Systems. ACM Comput. Surv. 13(2): 185-221(1981) BibTeX

[BGb]

Philip A. Bernstein, Nathan Goodman: The Failure and Recovery Problem for Replicated Databases. PODC 1983: 114-122 BibTeX

[BGRCK]

...

[BSR]

Philip A. Bernstein, David W. Shipman, James B. Rothnie Jr.: Concurrency Control in a System for Distributed Databases (SDD-1). ACM Trans. Database Syst. 5(1): 18-51(1980) BibTeX

[C]

Flaviu Cristian: Correct and Robust Programs. IEEE Trans. Software Eng. 10(2): 163-174(1984) BibTeX

[CASD]

...

[D]

Susan B. Davidson: Optimism and Consistency In Partitioned Distributed Database Systems. ACM Trans. Database Syst. 9(3): 456-481(1984) BibTeX

[ES]

Derek L. Eager, Kenneth C. Sevcik: Achieving Robustness in Distributed Database Systems. ACM Trans. Database Syst. 8(3): 354-381(1983) BibTeX

[EGLT]

Kapali P. Eswaran, Jim Gray, Raymond A. Lorie, Irving L. Traiger: The Notions of Consistency and Predicate Locks in a Database System. Commun. ACM 19(11): 624-633(1976) BibTeX

[ESC]

...

[G]

David K. Gifford: Weighted Voting for Replicated Data. SOSP 1979: 150-162 BibTeX

[GMBLLPPT]

Jim Gray, Paul R. McJones, Mike W. Blasgen, Bruce G. Lindsay, Raymond A. Lorie, Thomas G. Price, Gianfranco R. Putzolu, Irving L. Traiger: The Recovery Manager of the System R Database Manager. ACM Comput. Surv. 13(2): 223-243(1981) BibTeX

[H]

...

[KR]

H. T. Kung, John T. Robinson: On Optimistic Methods for Concurrency Control. ACM Trans. Database Syst. 6(2): 213-226(1981) BibTeX

[L]

Leslie Lamport: Time, Clocks, and the Ordering of Events in a Distributed System. Commun. ACM 21(7): 558-565(1978) BibTeX

[SW]

Dale Skeen, David D. Wright: Increasing Availability in Partitioned Database Systems. PODS 1984: 290-299 BibTeX

[TGGL]

Irving L. Traiger, Jim Gray, Cesare A. Galtieri, Bruce G. Lindsay: Transactions and Consistency in Distributed Database Systems. ACM Trans. Database Syst. 7(3): 323-342(1982) BibTeX

[T]

Robert H. Thomas: A Majority Consensus Approach to Concurrency Control for Multiple Copy Databases. ACM Trans. Database Syst. 4(2): 180-209(1979) BibTeX

Referenced by

1. Yukari Shirota, Atsushi Iizawa, Hiroko Mano, Takashi Yano: The ECHO Method: Concurrency Control Method for a Large-Scale Distributed Database. ICDE 1999: 174-183
2. Sanjay Kumar Madria, S. N. Maheshwari, B. Chandra: On the Correctnes of Virtual Partition Algorithm in a Nested Transaction Environment. ADBIS 1999: 98-112
3. Xiangning Liu, Abdelsalam Helal, Weimin Du: Multiview Access Protocols for Large-Scale Replication. ACM Trans. Database Syst. 23(2): 158-198(1998)
4. Svein Erik Bratsberg, Svein-Olaf Hvasshovd, Øystein Torbjørnsen: Parallel Solutions in ClustRa. IEEE Data Eng. Bull. 20(2): 13-20(1997)
5. Rune Humborstad, Maitrayi Sabaratnam, Svein-Olaf Hvasshovd, Øystein Torbjørnsen: 1-Safe Algorithms for Symmetric Site Configurations. VLDB 1997: 316-325
6. Peter Triantafillou, David J. Taylor: VELOS: A New Approach for Efficiently Achieving High Availability in Partitioned Distributed Systems. IEEE Trans. Knowl. Data Eng. 8(2): 305-321(1996)
7. Divyakant Agrawal, Amr El Abbadi: Using Reconfiguration for Efficient Management of Replicated Data. IEEE Trans. Knowl. Data Eng. 8(5): 786-801(1996)
8. Jeff Sidell, Paul M. Aoki, Adam Sah, Carl Staelin, Michael Stonebraker, Andrew Yu: Data Replication in Mariposa. ICDE 1996: 485-494
9. Svein-Olaf Hvasshovd, Øystein Torbjørnsen, Svein Erik Bratsberg, Per Holager: The ClustRa Telecom Database: High Availability, High Throughput, and Real-Time Response. VLDB 1995: 469-477
10. Idit Keidar, Danny Dolev: Increasing the Resilience of Atomic Commit at No Additional Cost. PODS 1995: 245-254
11. Kenneth J. Goldman, Nancy A. Lynch: Quorum Consensus in Nested Transaction Systems. ACM Trans. Database Syst. 19(4): 537-585(1994)
12. Weimin Du, Ahmed K. Elmagarmid, Won Kim, Omran A. Bukhres: Support Consistent Updates in Replicated Multidatabase Systems. VLDB J. 2(2): 215-241(1993)
13. Akhil Kumar, Arie Segev: Cost and Availability Tradeoffs in Replicated Data Concurrency Control. ACM Trans. Database Syst. 18(1): 102-131(1993)
14. Michael Stonebraker, Rakesh Agrawal, Umeshwar Dayal, Erich J. Neuhold, Andreas Reuter: DBMS Research at a Crossroads: The Vienna Update. VLDB 1993: 688-692
15. Show-Jane Yen, Arbee L. P. Chen: Neighborhood/Conceptual Query Answering with Imprecise/Incomplete Data. ER 1993: 149-165
16. Divyakant Agrawal, Amr El Abbadi: The Generalized Tree Quorum Protocol: An Efficient Approach for Managing Replicated Data. ACM Trans. Database Syst. 17(4): 689-717(1992)
17. Donald D. Chamberlin, Frank B. Schmuck: Dynamic Data Distribution (D³) in a Shared-Nothing Multiprocessor Data Store. VLDB 1992: 163-174
18. Divyakant Agrawal, Amr El Abbadi: Resilient Logical Structures for Efficient Management of Replicated Data. VLDB 1992: 151-162
19. Michael Rabinovich, Edward D. Lazowska: Improving Fault Tolerance and Supporting Partial Writes in Structured Coterie Protocols for Replicated Objects. SIGMOD Conference 1992: 226-235
20. Michael Rabinovich, Edward D. Lazowska: A Fault-Tolerant Commit Protocol for Replicated Databases. PODS 1992: 139-148
21. Sampath Rangarajan, Sanjeev Setia, Satish K. Tripathi: A Fault-Tolerant Algorithm for Replicated Data Management. ICDE 1992: 230-237
22. Michael J. Carey, Miron Livny: Conflict Detection Tradeoffs for Replicated Data. ACM Trans. Database Syst. 16(4): 703-746(1991)
23. Peter Triantafillou, David J. Taylor: Efficiently Maintaining Availability in the Presence of Partitionings in Distributed Systems. ICDE 1991: 34-41
24. Sushil Jajodia, David Mutchler: Dynamic Voting Algorithms for Maintaining the Consistency of a Replicated Database. ACM Trans. Database Syst. 15(2): 230-280(1990)
25. Divyakant Agrawal, Amr El Abbadi: The Tree Quorum Protocol: An Efficient Approach for Managing Replicated Data. VLDB 1990: 243-254
26. Uwe M. Borghoff: Voting and Relocation Strategies Preserving Consistency among Replicated Files. ICDT 1990: 318-332
27. Michael Stonebraker, Gerhard A. Schloss: Distributed RAID - A New Multiple Copy Algorithm. ICDE 1990: 430-437
28. Amr El Abbadi, Sam Toueg: Maintaining Availability in Partitioned Replicated Databases. ACM Trans. Database Syst. 14(2): 264-290(1989)
29. Sushil Jajodia, David Mutchler: A Hybrid Replica Control Algorithm Combining Static and Dynamic Voting. IEEE Trans. Knowl. Data Eng. 1(4): 459-469(1989)
30. Jeffrey D. Ullman: Principles of Database and Knowledge-Base Systems, Volume II. Computer Science Press 1989, ISBN 0-7167-8162-X
    Contents
31. Akhil Kumar, Michael Stonebraker: Semantics Based Transaction Management Techniques for Replicated Data. SIGMOD Conference 1988: 117-125
32. Bharat K. Bhargava, Paul Noll, Donna Sabo: An Experimental Analysis of Replicated Copy Control During Site Failure and Recovery. ICDE 1988: 82-91
33. Akhil Kumar, Arie Segev: Optimizing Voting-Type Algorithms for Replicated Data. EDBT 1988: 428-442
34. Maurice Herlihy: Dynamic Quorum Adjustment for Partitioned Data. ACM Trans. Database Syst. 12(2): 170-194(1987)
35. Denise J. Ecklund, Earl F. Ecklund Jr., Robert O. Eifrig, Fred M. Tonge: DVSS: A Distributed Version Storage Server for CAD Applications. VLDB 1987: 443-454
36. Sushil Jajodia, David Mutchler: Dynamic Voting. SIGMOD Conference 1987: 227-238
37. Philip A. Bernstein, Vassos Hadzilacos, Nathan Goodman: Concurrency Control and Recovery in Database Systems. Addison-Wesley 1987, ISBN 0-201-10715-5
    Contents
38. Amr El Abbadi, Sam Toueg: Availability in Partitioned Replicated Databases. PODS 1986: 240-251