A formalism for consistency and partial replication

Abstract : Replication protocols are complex and it is difficult to compare their consistency properties. To this effect, we propose a formalism where a replica executes actions subject to constraints in its local view or multilog. Schedules are selected non-deterministically from the set of sound schedules. This set grows with the number of actions and shrinks as the number of constraints increases. If the size of the set is one, the site has converged; if the size becomes zero, the site has detected an unrecoverable conflict. If every site runs the same schedule, they are consistent. We formalise this intuitive concept of consistency in four different ways, which generalise classical consistency criteria and which expose different aspects of consistency protocols. We prove them equivalent. We provide the first formal definition of consistency for partially replicated data. In general, achieving consistency entails global consensus; we exhibit sufficient conditions for deciding locally and derive a new decentralised protocol. In a separate technical report we prove the consistency of some published consistency protocols; this underscores the deep commonalities between them.
keyword : rep syn optim
Type de document :
[Technical Report] Microsoft Research. 2004
Liste complète des métadonnées

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

Contributeur : Marc Shapiro <>
Soumis le : jeudi 7 janvier 2010 - 11:43:52
Dernière modification le : samedi 17 septembre 2016 - 01:20:14
Document(s) archivé(s) le : jeudi 17 juin 2010 - 22:27:11


Fichiers produits par l'(les) auteur(s)


  • HAL Id : inria-00444800, version 1



Marc Shapiro, Karthikeyan Bhargavan, Yek Chong, Youssef Hamadi. A formalism for consistency and partial replication. [Technical Report] Microsoft Research. 2004. 〈inria-00444800〉



Consultations de la notice


Téléchargements de fichiers