Agreeing to Disagree: Conflict Resolution for Optimistically Replicated Data

Current approaches for reconciling disconnected changes to optimistically replicated data typically use version vectors or similar mechnisms to track causal histories. Such approaches 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 very satisfactory ways of repairing conflicts -- the usual way of doing it involves introducing fresh events into the causal history, even in situations where the causally independent values at the two replicas are actually equal. These events will then conflict with each other, slowing or even preventing convergence of the whole system, even with synchronous communication between replicas. We address this issue by using a notion of explicit conflict resolution where a replica explicitly declares which conflicting events it wants to resolve. A key feature we introduce is agreement events where a replica can agree with a conflicting value instead of only having the choice to dominate it. We outline a set of desirable characteristics in a conflict resolution system and present an algorithm that has the property that the information stored at any replica as well as the sizes of the messages exchanged by it, are bounded by a quadratic function of the number of distinct replicas in the system.