Cost and availability tradeoffs in replicated data concurrency control

Reviewer: M. Tamer Özsu

Replication of data for higher availability and better performance has aroused significant interest in recent years. The existence of replicas in a system requires the implementation of special protocols to guarantee the consistency of the various copies. Many of these replication protocols have been reported in the literature. An important class of replication protocols is the quorum-based protocols, in which votes are assigned to replicas and a transaction that wants to read or write a data item has to obtain a read quorum or a write quorum, respectively, in order to carry out the operation. One of the important problems in these protocols is the optimal assignment of votes to replicas and the determination of the read and write quorums. This paper investigates this problem in the context of static replication protocols. Static protocols are those where the vote assignment and the read and write quorums are fixed a priori. This paper is important primarily because it provides an evaluation of a static protocol within a series of constraints on the system, such as failure tolerance and availability. Fault tolerance and availability differ in that fault tolerance is a deterministic measure, whereas availability is a probabilistic measure. Basically, three optimization models are studied: vote assignment and quorum determination to minimize communication cost (in executing the replication protocol); vote assignment and quorum determination to minimize communication cost when the system has to meet or exceed a minimum fault tolerance threshold; and vote assignment and quorum determination to minimize communication cost when the system has to meet or exceed an availability requirement. These three models are analyzed along two dimensions: whether all the replicas have equal votes, and whether the communication costs between any two sites are identical. Thus, 12 decision problems are considered. Analytical solutions are available for a number of them, and heuristic algorithms are proposed to deal with the remainder. This paper is important for those who are interested in replication protocols. It provides a rigorous analysis (even if it is of only one protocol), which is generally lacking in this field. The paper is self-contained and fairly easy to read; it provides an easy-to-follow introduction to the problem and to the various approaches to solving it before describing the main results. The paper does not cover a number of issues that are of interest. It does not consider the dynamic protocols, which are probably more difficult to analyze. It does not consider the behavior of the algorithms in multiconstraint environments (that is, when both fault-tolerance and availability constraints are imposed). Nevertheless, it is important and should provide the framework for further studies.