Voting as the optimal static pessimistic scheme for managing replicated data

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 an 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.