Agreeing to Agree: Conflict Resolution for Optimistically Replicated Data

Current techniques for reconciling disconnected changes to optimistically replicated data often use version vectors or related mechanisms to track causal histories. This allows the system to detect when the value at one replica dominates another and when, on the other hand, two replicas are in conflict. However, current algorithms do not provide entirely satisfactory ways of repairing conflicts. The usual approach is to introduce fresh events into the causal history, even in situations where the causally independent values at the two replicas are actually equal. These events may later conflict with each other or with further updates, slowing or even preventing convergence of the whole system. To address this issue, we propose enriching the set of possible actions at a replica to include a notion of explicit conflict resolution between existing events, where the user at a replica declares that one set of events dominates another, or that a set of events are equivalent. We begin by precisely specifying the behavior of this refined replication framework from a user's point of view. Next, we present a negative result: if communication between replicas is completely unrestricted--updates are propagated through the sytem by individual replicas sending information to other replicas, who may or may not ever reply directly--then the storage space used by any correct implementation of this specification must grow without bound. Finally, we follow this up with a positive result: if communication is assumed to "reciprocal," with pairs of replicas exchanging information about their current states, then the specification can be implemented by an algorithm with the property that the information stored at any replica and the sizes of the messages sent between replicas are bounded by a polynomial function of the number of replicas in the system.