Achieving Incremental Consistency among Autonomous Replicated Databases

In this paper, we present methods for supporting autonomous updates in replicated databases. Autonomous updates are of particular importance to applications that cannot tolerate the delay and vulnerability due to synchronous update methods (2PC). We separate the notion of replication consistency, meaning that all copies have the same value and reflect the same update transactions, from behavior consistency, meaning that transaction execution reflects all integrity constraints. The method proposed in this paper supports independent updates during network partitioning, and achieves a consistent final database state on recovery of partitions that reflects all actions that were executed during network partitioning. To this purpose, we describe a reconciliation procedure that applies all actions to each updated data item in the order in which they were originally performed, possibly independently; therefore, reconciliation may require the undo and redo of actions. We formally define the properties that need to hold for our approach to work, and we prove that our reconciliation procedure respects these properties. Our approach is incremental, as it can be applied to any sequence of partitionings and recoveries; reconciliation occurs whenever possible or at the user's desire. However, we trade consistent behavior for update availability: in general, there is no guarantee that the execution will reflect all global consistency constraints. Localization techniques for constraints can be used to support consistent behavior for particular constraint classes.