Voting as the optimal static pessimistic scheme for managing replicated data
- 4 December 2002
- conference paper
- Published by Institute of Electrical and Electronics Engineers (IEEE)
Abstract
The problem of finding an optimal static pessimistic replica control scheme is investigated. It has been widely accepted that coteries (proposed by Garcia-Molina and Barbara) provide the most general framework for such schemes. Under such as assumption, it is demonstrated that the voting scheme is an optimal static pessimistic scheme for fully connected networks with negligible link failure rates, as well as for Ethernet systems. It is also shown that voting is not optimal for somewhat more general systems. The authors propose a modification of the algorithm of Tong and Kain for the best voting in the operation-independent case so that it runs in linear (rather than exponential) time. They also propose a linear-time algorithm for computing the optimal vote assignment when relative frequencies of read and write operations are known.Keywords
This publication has 13 references indexed in Scilit:
- A scheme for maintaining consistency and availability of replicated files in a partitioned distributed systemPublished by Institute of Electrical and Electronics Engineers (IEEE) ,2003
- Optimizing vote and quorum assignments for reading and writing replicated dataPublished by Institute of Electrical and Electronics Engineers (IEEE) ,2003
- Integrating static and dynamic voting protocols to enhance file availabilityPublished by Institute of Electrical and Electronics Engineers (IEEE) ,2003
- A static pessimistic scheme for handling replicated databasesPublished by Association for Computing Machinery (ACM) ,1989
- Dynamic votingACM SIGMOD Record, 1987
- Consistency in a partitioned network: a surveyACM Computing Surveys, 1985
- An algorithm for concurrency control and recovery in replicated distributed databasesACM Transactions on Database Systems, 1984
- A Majority consensus approach to concurrency control for multiple copy databasesACM Transactions on Database Systems, 1979
- Weighted voting for replicated dataPublished by Association for Computing Machinery (ACM) ,1979
- Computing the Reliability of Complex NetworksSIAM Journal on Applied Mathematics, 1977