Abstract
Recovery methods for replicated database systems should handle both site and network partitioning failures as efficiently as possible. Techniques are needed that use knowledge about what happened during a failure to reduce the costs of recovery. Another promising approach is to use information stored at replicated copies to improve the efficiency of recovery. For such techniques to be applicable to broad classes of replicated copy control algorithms, a correctness model is needed that encompasses different possibilities for object representation and gives correctness conditions for classes of algorithms. We define a new model for replicated objects in which an object's representation consists of a set of timestamped values plus a set of histories containing records of operation executions, and we give a criterion for correct transaction processing in terms of this model. We classify quorum-based recovery methods into four categories, ranging from static to dynamic, and develop correctness conditions for each category. We describe techniques for reducing the costs of recovery for dynamic quorum methods. Lastly, we investigate how communication-based recovery that takes advantage of replicated copies can be integrated with quorum methods.
