Agreeing to Agree: Conflict Resolution for Optimistically Replicated Data

Abstract : 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 tell whether the value at one replica dominates another or whether the two replicas are in conflict. However, current algorithms do not provide entirely sat- isfactory 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. In some sce- narios 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 enrich 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 precisely specify the behavior of this refined replication framework from a user's point of view and show that, if communication is assumed to be “reciprocal” (with pairs of replicas exchanging information about their current states), then this 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.
keyword : Harmony
Type de document :
Communication dans un congrès
20th International Symposium on Distributed Computing (DISC), Sep 2006, Stockholm, Sweden. 4167, pp.269--283, 2006, Lecture Notes in Computer Science. 〈10.1007/11864219_19〉
Liste complète des métadonnées

Littérature citée [25 références]  Voir  Masquer  Télécharger

https://hal.inria.fr/inria-00535653
Contributeur : Alan Schmitt <>
Soumis le : vendredi 12 novembre 2010 - 11:41:10
Dernière modification le : jeudi 11 janvier 2018 - 06:20:05
Document(s) archivé(s) le : dimanche 13 février 2011 - 02:37:38

Fichier

Greenwald2006Agreeing-to-Agree...
Fichiers produits par l'(les) auteur(s)

Identifiants

Collections

Citation

Michael Greenwald, Sanjeev Khanna, Keshav Kunal, Benjamin Pierce, Alan Schmitt. Agreeing to Agree: Conflict Resolution for Optimistically Replicated Data. 20th International Symposium on Distributed Computing (DISC), Sep 2006, Stockholm, Sweden. 4167, pp.269--283, 2006, Lecture Notes in Computer Science. 〈10.1007/11864219_19〉. 〈inria-00535653〉

Partager

Métriques

Consultations de la notice

199

Téléchargements de fichiers

100