CONFLICT DETECTION TRADEOFFS FOR REPLICATED DATA

Many concurrency control algorithms have been proposed for use in distributed database systems. Despite the large number of available algorithms and the fact that distributed database systems are becoming a commercial reality, distributed concurrency control performance trade-offs are still not well understood. In this paper we examine some of these trade-offs by using a detailed model of a distributed DBMS to study a set of representative algorithms, including several derivatives of the two-phase locking, timestamp ordering, and optimistic approaches to distributed concurrency control. In particular, we examine the performance of these algorithms for update transactions as a function of data contention for various levels of data replication and "distributedness" of accesses to replicated data. The results provide some interesting insights into how the trade-offs between early and late conflict detection vary as a function of message cost, and should prove useful to distributed database system designers.