Increasing concurrency and autonomy in replicated database systems

Databases are often replicated for reasons of increased performance and increased availability of the data. Since transactions can concurrently access shared (possibly replicated) data, their execution has to be carefully controlled using concurrency control protocols so that "correctness" is preserved. Traditionally, concurrency controls in replicated databases ensure one-copy serializability--the effect of the execution of transactions on the replicated data is equivalent to some serial execution of those transactions on a single copy. However, preserving one-copy serializability is too restrictive in some applications. In addition, message passing delays incurred in maintaining the mutual consistency of the replicas reduce throughput. In this dissertation, we emphasize relaxing both the requirements of serializability and mutual consistency to increase throughput.;In the first part of this dissertation, we primarily deal with applications that can permit bounded violations of the integrity constraints of the system. We propose a novel correctness model called bounded ignorance that utilizes this relaxed notion of (traditional) correctness to increase concurrency. For clarity, we first develop the concepts and implementations around a simple transaction model. We formalize bounded ignorance as N-ignorance, where a transaction can be unaware of the updates of at most N concurrent transactions in the system. We provide a suite of implementation techniques to ensure that a system is N-ignorant. These algorithms increase the amount of concurrency and autonomy in the system, thereby increasing throughput. To determine the extent to which the integrity constraints can be violated, we also provide an analysis of the reachable states in the system.;The notion of bounded ignorance in the general transaction model is that of a matrix of ignorance. Deriving the matrix of ignorance given the original constraints and the relaxed constraints is a difficult problem in general, but we provide a case-study of ignorance matrix construction in a relational database environment.;Finally, we discuss algorithms that use the state of the database to vary the amount of concurrency in the system. We extend state-based algorithms called escrow algorithms to provide efficient transaction management in resource allocation applications. We also provide simulation results indicating the efficiency of our algorithms versus existing algorithms.