DATE: Friday,
October 24, 2003
TIME: Noon - 1 pm
PLACE: Wean Hall 8220
SPEAKER:
Marc
Shapiro
Microsoft Research, Cambridge, UK
TITLE:
Modelling Replication Protocols with Actions and Constraints
Joint work with Karthikeyan Bhargavan and Fabrice le Fessant Microsoft
Research Ltd.
Cambridge, U.K.
ABSTRACT:
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 (constraints).
- Concurrent updates may conflict, i.e. violate object invariants (more constraints).
- The replication protocol transfers actions and orders them (adding other constraints).
- 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.
BIO:
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
SDI / LCS Seminar Questions?
Karen Lindenfelser, 86716, or visit www.pdl.cmu.edu/SDI/