Abstract
Replication in distributed computing systems provides improved availability and reliability in the event of site failure and network partitioning. However, if strict mutual consistency is required, transactions can be processed in at most one partition, thereby reducing availability. We present a consistency control algorithm that relaxes strict mutual consistency criteria, and allows concurrent processing in all partitions. Inconsistency of data objects in different partitions is resolved at the time of
merging the partitions when recovery occurs. The basis of our algorithm is a new
merge mechanism that utilizes available semantic information about the data objects and transaction types. We present a formal proof of correctness of the algorithm. Results from a simulation model show that our algorithm performs better than a previously proposed approach that uses compensating transactions to sacrifice serializability of replicated data.