Cost and availability tradeoffs in replicated data concurrency control
Akhil Kumar, Arie Segev · ACM Transactions on Database Systems · 1993
High availabilityof 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.