Skip to Main content Skip to Navigation
New interface
Reports (Research report)

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
Document type :
Reports (Research report)
Complete list of metadata
Contributor : Alain Monteil Connect in order to contact the contributor
Submitted on : Thursday, December 24, 2015 - 9:43:17 AM
Last modification on : Friday, November 18, 2022 - 9:23:57 AM


  • 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⟩



Record views


Files downloads