Management of replicated data in distributed systems
Mirjana Obradovic · 1991
This thesis discusses the problem of maintaining availability and consistency of replicated data in a distributed system. In the last few years, a substantial amount of work has been done in the area of managing replicated data in distributed systems. Data are replicated for two main reasons: availability and read performance. When several copies of the same data items are stored at different sites (nodes), read/write operations may be possible in spite of individual site and link failures of network partitions. Also, having a locally available copy of a data item sometimes decreases message traffic and response time. We investigate the problem of finding an optimal state pessimistic replica control scheme. It has been widely accepted that coteries (preposed by Garcia-Molina and Barbara) provide the most general framework for such schemes. We demonstrate that the voting scheme, a special case of the coterie scheme, is optimal for fully connected networks, Ethernet systems and rings. We also address the question of computing optimal vote assignment for these types of networks. We provide the first efficient algorithm for computing the optimal vote assignment when frequency rates of read operations and write operations are known. We also propose an approximation technique for computing vote assignments with significantly decreased running time, compared to the existing solutions. Finally, we develop a reduction method for reducing the number of operations considered in the analysis.