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

Replica Control in Distributed Systems: An Asynchronous Approach.

Calton Pu, Avraham Leff: Replica Control in Distributed Systems: An Asynchronous Approach. SIGMOD Conference 1991: 377-386
@inproceedings{DBLP:conf/sigmod/PuL91,
  author    = {Calton Pu and
               Avraham Leff},
  editor    = {James Clifford and
               Roger King},
  title     = {Replica Control in Distributed Systems: An Asynchronous Approach},
  booktitle = {Proceedings of the 1991 ACM SIGMOD International Conference on
               Management of Data, Denver, Colorado, May 29-31, 1991},
  publisher = {ACM Press},
  year      = {1991},
  pages     = {377-386},
  ee        = {http://doi.acm.org/10.1145/115790.115856, db/conf/sigmod/PuL91.html},
  crossref  = {DBLP:conf/sigmod/91},
  bibsource = {DBLP, http://dblp.uni-trier.de}
}

Abstract

An asynchronous approach is proposed for replica control in distributed systems. This approach applies an extension of serializability called epsilon-serializability (ESR), a correctness criterion which allows temporary and bounded inconsistency in replicas to be seen by queries. Moreover, users can reduce the degree of inconsistency to the desired amount. In the limit, users see strict 1-copy serializability. Because the system maintains ESR correctness (1) replicas always converges to global serializability and (2) the system permits read access to object replicas before the system reaches a quiescent state.

Various replica control methods that maintain ESR are described and analyzed. Because these methods do not require users to refer explicitly to ESR criteria, they can be easily encapsulated in high-level applications that use replicated data.

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


ACM SIGMOD Anthology

Online Version (ACM WWW Account required): Full Text in PDF Format

CDROM Version: Load the CDROM "Volume 1 Issue 2, SIGMOD '75-'92" and ...

DVD Version: Load ACM SIGMOD Anthology DVD 1" and ...

Printed Edition

James Clifford, Roger King (Eds.): Proceedings of the 1991 ACM SIGMOD International Conference on Management of Data, Denver, Colorado, May 29-31, 1991. ACM Press 1991 CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML, SIGMOD Record 20(2), June 1991
Contents

Online Edition: ACM Digital Library

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

References

[1]
Divyakant Agrawal, Soumitra Sengupta: Modular Synchronization in Multiversion Databases: versionControl and Concurrency Control. SIGMOD Conference 1989: 408-417 CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[2]
Rafael Alonso, Daniel Barbará, Hector Garcia-Molina: Data Caching Issues in an Information Retrieval System. ACM Trans. Database Syst. 15(3): 359-384(1990) CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[3]
...
[4]
Philip A. Bernstein, Vassos Hadzilacos, Nathan Goodman: Concurrency Control and Recovery in Database Systems. Addison-Wesley 1987, ISBN 0-201-10715-5
Contents CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[5]
Philip A. Bernstein, Meichun Hsu, Bruce Mann: Implementing Recoverable Requests Using Queues. SIGMOD Conference 1990: 112-122 CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[6]
Kenneth P. Birman, Thomas A. Joseph: Exploiting Virtual Synchrony in Distributed Systems. SOSP 1987: 123-138 CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[7]
Andrew Birrell, Roy Levin, Roger M. Needham, Michael D. Schroeder: Grapevine: An Exercise in Distributed Computing. Commun. ACM 25(4): 260-274(1982) CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[8]
Barbara T. Blaustein, Charles W. Kaufman: Updating Replicated Data During Communications Failures. VLDB 1985: 49-58 CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[9]
Susan B. Davidson, Hector Garcia-Molina, Dale Skeen: Consistency in Partitioned Networks. ACM Comput. Surv. 17(3): 341-370(1985) CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[10]
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 CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[11]
Alan R. Downing, Ira B. Greenberg, Jon M. Peha: OSCAR: An Architecture for Weak-Consistency Replication. PARBASE / Databases 1990: 55-72 CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[12]
...
[13]
Hector Garcia-Molina, Gio Wiederhold: Read-Only Transactions in a Distributed Database. ACM Trans. Database Syst. 7(2): 209-234(1982) CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[14]
David K. Gifford: Weighted Voting for Replicated Data. SOSP 1979: 150-162 CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[15]
...
[16]
...
[17]
...
[18]
Rivka Ladin, Barbara Liskov, Liuba Shrira: Lazy Replication: Exploiting the Semantics of Distributed Services. PODC 1990: 43-57 CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[19]
Leslie Lamport: Time, Clocks, and the Ordering of Events in a Distributed System. Commun. ACM 21(7): 558-565(1978) CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[20]
...
[21]
Mahadev Satyanarayanan, James J. Kistler, Puneet Kumar, Maria E. Okasaki, Ellen H. Siegel, David C. Steere: Coda: A Highly Available File System for a Distributed Workstation Environment. IEEE Trans. Computers 39(4): 447-459(1990) CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[22]
...
[23]
...
[24]
Gio Wiederhold, Xiaolei Qian: Modeling Asynchrony in Distributed Databases. ICDE 1987: 246-250 CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[25]
...
[26]
...

Referenced by

  1. Haifeng Yu, Amin Vahdat: Efficient Numerical Error Bounding for Replicated Network Services. VLDB 2000: 123-133
  2. Bettina Kemme, Gustavo Alonso: Don't Be Lazy, Be Consistent: Postgres-R, A New Way to Implement Database Replication. VLDB 2000: 134-143
  3. Sharad Mehrotra, Rajeev Rastogi, Henry F. Korth, Abraham Silberschatz: Ensuring Consistency in Multidatabases by Preserving Two-Level Serializability. ACM Trans. Database Syst. 23(2): 199-230(1998)
  4. Alexander Thomasian: Concurrency Control: Methods, Performance, and Analysis. ACM Comput. Surv. 30(1): 70-119(1998)
  5. Todd A. Anderson, Yuri Breitbart, Henry F. Korth, Avishai Wool: Replication, Consistency, and Practicality: Are These Mutually Exclusive? SIGMOD Conference 1998: 484-495
  6. Paul M. Aoki: Generalizing ``Search'' in Generalized Search Trees (Extended Abstract). ICDE 1998: 380-389
  7. Kun-Lung Wu, Philip S. Yu, Calton Pu: Divergence Control Algorithms for Epsilon Serializability. IEEE Trans. Knowl. Data Eng. 9(2): 262-274(1997)
  8. Yuri Breitbart, Henry F. Korth: Replication and Consistency: Being Lazy Helps Sometimes. PODS 1997: 173-184
  9. Krithi Ramamritham, Panos K. Chrysanthis: A Taxonomy of Correctness Criteria in Database Applications. VLDB J. 5(1): 85-97(1996)
  10. Arif Merchant, Kun-Lung Wu, Philip S. Yu, Ming-Syan Chen: Performance Analysis of Dynamic Finite Versioning Schemes: Storage Cost vs. Obsolescence. IEEE Trans. Knowl. Data Eng. 8(6): 985-1001(1996)
  11. Jeff Sidell, Paul M. Aoki, Adam Sah, Carl Staelin, Michael Stonebraker, Andrew Yu: Data Replication in Mariposa. ICDE 1996: 485-494
  12. Parvathi Chundi, Daniel J. Rosenkrantz, S. S. Ravi: Deferred Updates and Data Placement in Distributed Databases. ICDE 1996: 469-476
  13. Krithi Ramamritham, Calton Pu: A Formal Characterization of Epsilon Serializability. IEEE Trans. Knowl. Data Eng. 7(6): 997-1007(1995)
  14. Gultekin Özsoyoglu, Richard T. Snodgrass: Temporal and Real-Time Databases: A Survey. IEEE Trans. Knowl. Data Eng. 7(4): 513-532(1995)
  15. Sang Hyuk Son, Fengjie Zhang: Real-Time Replication Control for Distributed Database Systems: Algorithms and Their Performance. DASFAA 1995: 214-221
  16. Hang Kwong Mak, Man Hon Wong: Trading Operation Consistency for Concurrency. DASFAA 1995: 405-412
  17. Daniel Barbará, Hector Garcia-Molina: The Demarcation Protocol: A Technique for Maintaining Constraints in Distributed Database Systems. VLDB J. 3(3): 325-353(1994)
  18. Patrick E. O'Neil, Mohsen Al-Ghosein, David Vaskevitch, Rick Vicik, Laura Yedwab: Transaction Processing at Microsoft: Present and Future. IEEE Data Eng. Bull. 17(1): 45-50(1994)
  19. Roger S. Barga, Calton Pu: Accessing Imprecise Data: An Approach Based on Intervals. IEEE Data Eng. Bull. 16(2): 12-15(1993)
  20. Kun-Lung Wu, Philip S. Yu, Ming-Syan Chen: Dynamic Finite Versioning: An Effective Versioning Approach to Concurrent Transaction and Query Processing. ICDE 1993: 577-586
  21. Mohan Kamath, Krithi Ramamritham: Performance Characteristics of Epsilon Serializability with Hierarchical Inconsistency Bounds. ICDE 1993: 587-594
  22. Sang Hyuk Son, Spiros Kouloumbis: A Token-Based Synchronization Scheme Using Epsilon-Serializability and Its Performance for Real-Time Distributed Database Systems. DASFAA 1993: 235-242
  23. Yuri Breitbart, Hector Garcia-Molina, Abraham Silberschatz: Overview of Multidatabase Transaction Management. VLDB J. 1(2): 181-239(1992)
  24. Man Hon Wong, Divyakant Agrawal: Tolerating Bounded Inconsistency for Increasing Concurrency in Database Systems. PODS 1992: 236-245
  25. Kun-Lung Wu, Philip S. Yu, Calton Pu: Divergence Control for Epsilon-Serializability. ICDE 1992: 506-515

Copyright © Mon Nov 2 21:11:45 2009 by Michael Ley (ley@uni-trier.de)