Conflict Detection Tradeoffs for Replicated Data

Abstract

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 tradeoffs are still not well understood. In this paper we examine some of these tradeoffs 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 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 tradeoffs between early and late conflict detection vary as a function of message cost, and should prove useful to distributed database system designers.