Seminars

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

For Further Seminar Info:
Visit http://www.pdl.cmu.edu/SDI/