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.