COST AND AVAILABILITY TRADEOFFS IN REPLICATED DATA CONCURRENCY-CONTROL

High availability of data is clearly a very important goal in a distri buted system. Most previous studies have concentrated on the unconstra ined maximization of availability, disregarding communications costs. Here we model this problem as one of minimizing communications costs s ubject to availability constraints. Two models for such constrained op timization are presented: The first characterizes availability determi nistically, while the second one does so probabilistically. Other simp ler models that are special cases of these two basic models and that a rise from making simplifying assumptions such as equal vote values or constant intersite communications costs are also discussed. We describ e a semi-exhaustive algorithm and efficient heuristics for solving eac h model. The algorithms utilize a novel signature-based method for ide ntifying equivalent vote combinations, and an efficient procedure for computing availability. Computational results for the various algorith ms are also given.