Concurrency Control using Locks in Distributed Databases

Candidate: Wolfson,Ouri

Abstract

Distributed Databases have drawn a great deal of research interest recently because of a combination of several related reasons. First is the tremendous expansion in the quantity of data that has to be processed in the modern world. Second is the growth in the number of interelated processing centers because microcomputers and communication technology enable greater dispersion of organizations. Third is the realization that complex problems to be addressed in this and next decade, such as different aspects of Artificial Intelligence, will require at least some parallel processing for adequate solution. In Distributed Databases the typical problems of Centralized Databases become more difficult. One of them is Concurrency Control. It can be summarized as follows. Users of the Database access it by executing transactions. Different transactions are executed concurrently therefore their actions interleave. Without proper control this interleaving may produce incorrect results, even if individual transactions are correct. The Concurrency Control process has to prevent these situations. There are several possible mechanisms for controlling concurrency, of which the most widely used is Locking. In this thesis we examine and analyze Locking as a Concurrency Control mechanism for Distributed Databases. We define Distributed Locking Policies (methods for locking entities in Distributed Databases) and show how existing Policies for a Centralized Database generalize to the Distributed case. We also define a new category of Distributed Locking Policies, D-policies, into which these generalizations fall. An algorithm which determines whether all transactions of a given D-policy are guaranteed to produce only correct interleavings (are safe) is presented. The algorithm is efficient, even though testing an arbitrary set of transactions for safety is coNP-complete. However, we prove that optimal locking of transactions to satisfy the conditions tested by the algorithm is NP-hard even for a Centralized Database.