Séminaire REGAL
Decoupling Causal Update Commitment Agreement from Update Propagation in Optimistic Replication
Monday, March 20, 2006Joao Barreto (doctorant à l'INESC de Lisbonne)
Optimistic replication protocols make progress towards consistency through a posteriori synchronization among replicas. During a single anti-entropy session, a number of correlated steps usually takes place: updates are propagated, a tentative update schedule is proposed, conflicts are detected and resolved, and commitment agreement evolves. For most existing solutions, the three last steps are based on the partial order defined by the happens-before relation between updates. Such a relation is compactly expressed by version vectors and, in most cases, is sufficient to assert the absence of conflicts in a given schedule of updates and agree on their commitment. However, by tying the propagation of such causalility information to coarse anti-entropy sessions with relatively high memory and bandwidth requirements, existing protocols are limited when such resources are constrained or connectivity is weak. This paper advocates the decoupling of the causal commitment agreement protocol from the actual propagation of updates. We propose an abstract protocol that achieves this decoupling and may be instantiated with existing solutions, enabling them to make consistency evolve in situations that otherwise would not be possible or would be more expensive in terms of resource consumption. Two potential applications are proposed; their evaluation suggests important consistency benefits in relevant networking environments.