Replica Control in Distributed Systems: An Asynchronous Approach.

@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

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

• 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
• Mac: Click here
• UNIX/LINUX: mount the CD and click on the path of your mount point:
  /Anthology/smod7592 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
• Mac: Click here
• UNIX/LINUX: mount the DVD and click on the path of your mount point:
  /Anthology/aDVD1 or /dvd

Printed Edition

Online Edition: ACM Digital Library

References

[1]

Divyakant Agrawal, Soumitra Sengupta: Modular Synchronization in Multiversion Databases: versionControl and Concurrency Control. SIGMOD Conference 1989: 408-417 BibTeX

[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) BibTeX

[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 BibTeX

[5]

Philip A. Bernstein, Meichun Hsu, Bruce Mann: Implementing Recoverable Requests Using Queues. SIGMOD Conference 1990: 112-122 BibTeX

[6]

Kenneth P. Birman, Thomas A. Joseph: Exploiting Virtual Synchrony in Distributed Systems. SOSP 1987: 123-138 BibTeX

[7]

Andrew Birrell, Roy Levin, Roger M. Needham, Michael D. Schroeder: Grapevine: An Exercise in Distributed Computing. Commun. ACM 25(4): 260-274(1982) BibTeX

[8]

Barbara T. Blaustein, Charles W. Kaufman: Updating Replicated Data During Communications Failures. VLDB 1985: 49-58 BibTeX

[9]

Susan B. Davidson, Hector Garcia-Molina, Dale Skeen: Consistency in Partitioned Networks. ACM Comput. Surv. 17(3): 341-370(1985) BibTeX

[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 BibTeX

[11]

Alan R. Downing, Ira B. Greenberg, Jon M. Peha: OSCAR: An Architecture for Weak-Consistency Replication. PARBASE / Databases 1990: 55-72 BibTeX

[12]

...

[13]

Hector Garcia-Molina, Gio Wiederhold: Read-Only Transactions in a Distributed Database. ACM Trans. Database Syst. 7(2): 209-234(1982) BibTeX

[14]

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

[15]

...

[16]

...

[17]

...

[18]

Rivka Ladin, Barbara Liskov, Liuba Shrira: Lazy Replication: Exploiting the Semantics of Distributed Services. PODC 1990: 43-57 BibTeX

[19]

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

[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) BibTeX

[22]

...

[23]

...

[24]

Gio Wiederhold, Xiaolei Qian: Modeling Asynchrony in Distributed Databases. ICDE 1987: 246-250 BibTeX

[25]

...

[26]

...