The Actions-Constraints approach to replication: Definitions and proofs

Abstract : Replicated information raises the major issue of consistency. We have developped a simple, formal framework, in order to better understand and compare consistency properties of replication protocols. The framework is both formal and implementable. Our language is simple enough to prove interesting properties, yet sufficiently powerful to specify diverse systems. In our model, each site maintains its local view of data, of actions to execute, and of the constraints that define legal execution schedules. Adding actions increases the number of possible schedules; adding constraints reduces scheduling non-determinism. We exhibit significant subsets of actions that are progressively more determined and show a number of useful properties. The system is consistent if every action is eventually scheduled and local executions converge. We compare different possible formulations of the consistency property and prove them to be mutually equivalent. This underscores the deep commonalities between diverse protocols. One of our formulations can be used to characterise consistency in partially replicated systems, i.e., where a site has visibility of only a subset of data, actions and constraints. Finally, we show how a number of protocols from the literature are modeled in the action-constraint framework
Keywords : rep syn optim
Type de document :
[Research Report] MSR-TR-2004-14, Microsoft Research. 2004
Liste complète des métadonnées
Contributeur : Alain Monteil <>
Soumis le : jeudi 24 décembre 2015 - 09:43:17
Dernière modification le : vendredi 16 septembre 2016 - 15:16:49


  • HAL Id : hal-01248210, version 1



Marc Shapiro, Karthikeyan Bhargavan. The Actions-Constraints approach to replication: Definitions and proofs. [Research Report] MSR-TR-2004-14, Microsoft Research. 2004. 〈hal-01248210〉



Consultations de la notice