From the past years, Distributed Databases have taken
attention in the database research community. Data distribution and replication
offer opportunities for improving performance through parallel query execution
and load balancing as well as increasing the availability of data. In fact,
these opportunities have played a major role in motivating the design of the
current generation of database machines (e.g., 1, 2). This paper addresses
some of the important performance issues related to these algorithms.
Most of the distributed concurrency control algorithms come
into one of three basic classes: locking algorithms 3,4,5,6,7, Timestamp
algorithms, 8,9,1, and optimistic (or certification) algorithms 10,11,12,
13. Many proposed algorithms reviewed 14 and describe how additional
algorithms may be synthesized by combining basic mechanisms from the locking
and timestamp classes 14.
Given the many proposed distributed concurrency control
algorithms, a number of researchers have undertaken studies of their
performance. For example, the behavior of various distributed locking
algorithms was investigated in 15, 4, 16, 17. Where algorithms with varying
degrees of centralization of locking and approaches to deadlock handling have
been studied and compared with one another. Several distributed Timestamp based
algorithms were examined in 18. A qualitative study addressing performance
issues for a number of distributed locking and timestamp algorithms was
presented in 14. The performance of locking was compared with that of basic
timestamp ordering in 19, with basic and multi-version timestamp ordering in
20. While the distributed concurrency control performance studies to date
have been useful but a number of important questions remain unanswered.
1. How do the performance characteristics of the various
basic algorithm classes compare under alternative assumptions about the nature
of the database, the workload, and the computational environment?
2. How does the distributed nature of transactions affect
the behavior of the various classes of concurrency control algorithms?
3. How much of a performance penalty must be incur for
synchronization and updates when data is replicated for availability or query
We examine four concurrency control algorithms in this
study, including two locking algorithms, a timestamp algorithm and an
optimistic algorithm. The algorithms considered span a wide range of
characteristics in terms of how conflicts are detected and resolved. Section 2
describes our choice of concurrency control algorithms. The structure and
characteristics of our model are described in Section 3 and section 4 describes
the testing of algorithms. Finally, Section 5 summarizes the main conclusions
of this study and raises questions that we plan to address in the future.