In this thesis, we present a paradigm for concurrency control protocols for distributed replicated databases. This paradigm presents a framework for both developing and analyzing concurrency control protocols, especially those that are designed to handle partitioning failures. Any concurrency control protocol that is an instance of the paradigm must be correct. We show that several known protocols are instances of this paradigm. Consequently, these seemingly unrelated protocols can now be compared and their understanding is simplified. We also present two new concurrency control protocols: the virtual partitions protocol and the accessibility thresholds protocol. Both protocols allow the reading and writing of data in spite of site and communication failures, even when these failures lead to network partitioning. In neither protocol is it ever necessary for a read operation to physically access more than one copy, which makes these protocols desirable for applications where efficient read operations are necessary. The accessibility thresholds protocol provides the database designer with much flexibility in trading off the cost of executing operations and the availability of data objects. Unlike previous protocols, the cost of executing operations on an object is separated from the read and write availability of that object.