Efficient Support for Partial Write Operations in Replicated Databases.

@inproceedings{DBLP:conf/icde/RabinovichL94,
  author    = {Michael Rabinovich and
               Edward D. Lazowska},
  title     = {Efficient Support for Partial Write Operations in Replicated
               Databases},
  booktitle = {Proceedings of the Tenth International Conference on Data Engineering,
               February 14-18, 1994, Houston, Texas, USA},
  publisher = {IEEE Computer Society},
  year      = {1994},
  isbn      = {0-8186-5400-7},
  pages     = {43-53},
  ee        = {db/conf/icde/RabinovichL94.html},
  crossref  = {DBLP:conf/icde/94},
  bibsource = {DBLP, http://dblp.uni-trier.de}
}

Abstract

In this paper, we present a new replica control technique targeted at replicated systems in which write operations update a portion of the information in the data item rather than replacing it entirely. The existing protocols capable of supporting partial writes must either perform the writes on all accessible replicas of the data item, or always apply the writes to the same group (quorum set) of replicas. In the former case, the system incurs high message overhead. In the latter case, if any of the replicas in this group fail, additional replicas must be synchronously brought up-to-date during the write operation causing delay to the operation. Also, in both cases, the system loses the advantage of load sharing provided by replication. Our protocol avoids performing the write on all nodes while preserving load sharing and reducing greatly the risk of having to propagate updates synchronously.

The paper describes the protocol, proves it correct, and presents a comparative performance study of our protocol and the existing alternatives.

Keywords: Distributed Systems - Replicated Databases - Distributed Algorithms - Quorums - Partial Write Operations

Copyright © 1994 by The Institute of Electrical and Electronic Engineers, Inc. (IEEE). Abstract used with permission.

ACM SIGMOD Anthology

• 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/An2-6 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

References

[1]

Divyakant Agrawal, Amr El Abbadi: An Efficient and Fault-Tolerant Solution for Distributed Mutual Exclusion. ACM Trans. Comput. Syst. 9(1): 1-20(1991)

[2]

Philip A. Bernstein, Vassos Hadzilacos, Nathan Goodman: Concurrency Control and Recovery in Database Systems. Addison-Wesley 1987, ISBN 0-201-10715-5
Contents

[3]

...

[4]

Shun Yan Cheung, Mostafa H. Ammar, Mustaque Ahamad: The Grid Protocol: A High Performance Scheme for Maintaining Replicated Data. IEEE Trans. Knowl. Data Eng. 4(6): 582-592(1992)

[5]

Jim Gray: Notes on Data Base Operating Systems. Advanced Course: Operating Systems 1978: 393-481

[6]

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

[7]

Hector Garcia-Molina, Daniel Barbará: How to Assign Votes in a Distributed System. J. ACM 32(4): 841-860(1985)

[8]

Andy Hisgen, Andrew Birrell, Charles Jerian, Timothy Mann, Michael D. Schroeder, Garret Swart: Granularity and Semantic Level of Replication in the Echo Distributed File System. Workshop on the Management of Replicated Data 1990: 2-4

[9]

Sushil Jajodia, David Mutchler: Dynamic Voting Algorithms for Maintaining the Consistency of a Replicated Database. ACM Trans. Database Syst. 15(2): 230-280(1990)

[10]

Akhil Kumar: Hierarchical Quorum Consensus: A New Algorithm for Managing Replicated Data. IEEE Trans. Computers 40(9): 996-1004(1991)

[11]

...

[12]

Barbara Liskov, Sanjay Ghemawat, Robert Gruber, Paul Johnson, Liuba Shrira, Michael Williams: Replication in the Harp File System. SOSP 1991: 226-238

[13]

...

[14]

Michael Rabinovich, Edward D. Lazowska: Improving Fault Tolerance and Supporting Partial Writes in Structured Coterie Protocols for Replicated Objects. SIGMOD Conference 1992: 226-235

[15]

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)

[16]

Michael Stonebraker: Concurrency Control and Consistency of Multiple Copies of Data in Distributed INGRES. IEEE Trans. Software Eng. 5(3): 188-194(1979)