October 24, 2003
Noon - 1 pm
Wean Hall 8220
Microsoft Research, Cambridge, UK
Modelling Replication Protocols with Actions and Constraints
Joint work with Karthikeyan Bhargavan and Fabrice le Fessant Microsoft
I will describe a formal model of replicated-data systems, based on actions
and constraints. An action models a data transformation, and a constraint
models an invariant. The same model describes different
levels in a unified fashion:
- A client application requests updates (actions) that are related
to one another in various ways, e.g. by causal dependence or atomicity
- Concurrent updates may conflict, i.e. violate object invariants (more
- The replication protocol transfers actions and orders them (adding
- Each site executes the actions it knows, according to some serial
schedule that satisfies the constraints it knows.
- The whole system must enforce consistency.
Within the model we give three different definitions of consistency:
(1) the intuitive, "declarative" notion of eventual consistency,
(2) an "operational" definition based on equivalence of local
schedules, and (3) a property of local information called mergeability.
We show the three definitions are equivalent. If time permits, I will
analyse a few well-known replication protocols in the framework.
Dr. Shapiro graduated from ENSEEIHT, in Toulouse (France), in 1978, and
received his Ph.D. from the Universite Paul-Sabatier of Toulouse in 1980.
After a post-doc at MIT, 1980-1982, he worked for the Centre Mondial Informatique
et Ressources Humaines in Paris from 1982 to 1984.
His collaboration with INRIA started in 1983; in 1985 he started the
SOR group. He spent the 1993-1994 year on sabbatical at the Computer Science
Department of Cornell University in Ithaca, NY (USA). He was the coordinator
for the Esprit Long Term Research project PerDiS, a Persistent Distributed
Store for Cooperative Engineering applications. He has led the Cambridge
Distributed Systems Group at Microsoft Research Ltd. in Cambridge (UK)
since October 1998
Further Seminar Info: