Cost and Availability Tradeoffs in Replicated Data Concurrency Control.

Akhil Kumar, Arie Segev: Cost and Availability Tradeoffs in Replicated Data Concurrency Control. ACM Trans. Database Syst. 18(1): 102-131(1993)

@article{DBLP:journals/tods/KumarS93,
  author    = {Akhil Kumar and
               Arie Segev},
  title     = {Cost and Availability Tradeoffs in Replicated Data Concurrency
               Control},
  journal   = {ACM Trans. Database Syst.},
  volume    = {18},
  number    = {1},
  year      = {1993},
  pages     = {102-131},
  ee        = {http://doi.acm.org/10.1145/151284.151287, db/journals/tods/KumarS93.html},
  bibsource = {DBLP, http://dblp.uni-trier.de}
}

BibTeX

Abstract

High availability of data is clearly a very important goal in a distributed system. Most previous studies have concentrated on the unconstrained maximization of availability, disregarding communications costs. Here we model this problem as one of minimizing commumcations costs subject to availability constraints. Two models for such constrained optimization are presented: The first characterizes availability deterministically, while the second one does so probabilistitally. Other simpler models that are special cases of these two basic models and that arise from making simplifying assumptions such as equal vote values or constant intersite communications costs are also discussed. We describe a semi-exhaustive algorithm and efficient heuristics for solving each model. The algorithms utilize a novel signature-based method for identifying equivalent vote combinations, and an efficient procedure for computing availability. Computational results for the various algorithms are also given.

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

Joint ACM SIGMOD / IEEE Computer Society Anthology

CDROM Version: Load the CDROM "Volume 3 Issue 2, TODS 1991-1995, TKDE 1989-1992" 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/An3-2 or /cdrom

DVD Version: Load ACM SIGMOD Anthology DVD 2" 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 DVD and click on the path of your mount point:
/Anthology/aDVD2 or /dvd

BibTeX

Online Edition: ACM Digital Library

[Index Terms and Review]
[Full Text in PDF Format, 1989 KB]

References

[1]: Daniel Barbará, Hector Garcia-Molina: The Reliability of Voting Mechanisms. IEEE Trans. Computers 36(10): 1197-1208(1987) BibTeX
[2]: Daniel Barbará, Hector Garcia-Molina, Annemarie Spauster: Protocols for Dynamic Vote Reassignment. PODC 1986: 195-205 BibTeX
[3]: Philip A. Bernstein, Vassos Hadzilacos, Nathan Goodman: Concurrency Control and Recovery in Database Systems. Addison-Wesley 1987, ISBN 0-201-10715-5
Contents BibTeX
[4]: Philip A. Bernstein, Nathan Goodman: An Algorithm for Concurrency Control and Recovery in Replicated Distributed Databases. ACM Trans. Database Syst. 9(4): 596-615(1984) BibTeX
[5]: ...
[6]: Shun Yan Cheung, Mustaque Ahamad, Mostafa H. Ammar: Optimizing Vote and Quorum Assignments for Reading and Writing Replicated Data. ICDE 1989: 271-279 BibTeX
[7]: Susan B. Davidson, Hector Garcia-Molina, Dale Skeen: Consistency in Partitioned Networks. ACM Comput. Surv. 17(3): 341-370(1985) BibTeX
[8]: Derek L. Eager, Kenneth C. Sevcik: Achieving Robustness in Distributed Database Systems. ACM Trans. Database Syst. 8(3): 354-381(1983) BibTeX
[9]: Amr El Abbadi, Dale Skeen, Flaviu Cristian: An Efficient, Fault-Tolerant Protocol for Replicated Data Management. PODS 1985: 215-229 BibTeX
[10]: Hector Garcia-Molina, Daniel Barbará: Optimizing the Reliability Provided by Voting Mechanisms. ICDCS 1984: 340-346 BibTeX
[11]: Hector Garcia-Molina, Daniel Barbará: How to Assign Votes in a Distributed System. J. ACM 32(4): 841-860(1985) BibTeX
[12]: David K. Gifford: Weighted Voting for Replicated Data. SOSP 1979: 150-162 BibTeX
[13]: Maurice Herlihy: Dynamic Quorum Adjustment for Partitioned Data. ACM Trans. Database Syst. 12(2): 170-194(1987) BibTeX
[14]: ...
[15]: Sushil Jajodia, David Mutchler: Dynamic Voting Algorithms for Maintaining the Consistency of a Replicated Database. ACM Trans. Database Syst. 15(2): 230-280(1990) BibTeX
[16]: Akhil Kumar, Arie Segev: Optimizing Voting-Type Algorithms for Replicated Data. EDBT 1988: 428-442 BibTeX
[17]: Michael Stonebraker: Concurrency Control and Consistency of Multiple Copies of Data in Distributed INGRES. IEEE Trans. Software Eng. 5(3): 188-194(1979) BibTeX
[18]: 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

Richard Y. Wang, Veda C. Storey, Christopher P. Firth: A Framework for Analysis of Data Quality Research. IEEE Trans. Knowl. Data Eng. 7(4): 623-640(1995)
Anna Brunstrom, Scott T. Leutenegger, Rahul Simha: Experimental Evaluation of Dynamic Data Allocation Strategies in A Distributed Database with Changing Workloads. CIKM 1995: 395-402

BibTeX

ACM SIGMOD Anthology - DBLP: [Home | Search: Author, Title | Conferences | Journals]