Marc Shapiro
Microsoft Research, Cambridge


Exploring the consistency problem space
---------------------------------------

We study consistency protocols for replicated shared data.  The
Action-Constraint framework that we use enables to decompose the problem
of ensuring consistency into simpler, easily understandable 
sub-problems. For each we exhibit an abstract algorithm, which we 
populate with concrete implementations taken from the literature.  As 
the sub-problems are largely orthogonal, these can be mixed and matched, 
with careful attention to issues of non-determinism and termination. The 
model encompasses correctness conditions for partial replication, which 
has been previously poorly understood.  As an illustration, we decompose 
Holliday's protocol for partial replication of databases into its basic 
building blocks.

Another interesting result is a new serialisation protocol that does not
abort actions; its design is made possible by the simplicity of the
action-constraint framework.  A simulation study compares a number of
representative protocol combinations.



Bio:

Dr. Shapiro graduated from ENSEEIHT, in Toulouse (France), in 1978, and 
received his Ph.D. from the Universit	 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 now leads the Cambridge Distributed Systems Group at MSRC, Microsoft 
Research Ltd. in Cambridge (UK) since October 1998.