CoRe: a Flexible and Generic Consistency Management for Distributed Typed Cache

Georges Brun-Cottan ­­­­ INRIA Projet SOR

We address the specific problem of information sharing in a small evolving group of members, possibly spread over a network exhibiting variable latencies. For example, latency can change because members move, because large-scale networks exhibit inherently varying latencies, or because group composition changes. This model can accurately characterize applications such as cooperative editing and multi-user network games. The problem is to achieve correct behavior while still being responsive. Let us assume that 1) responsiveness is achieved by caching mechanisms; 2) application correctness is determined by consistency properties; and 3) strong consistency is unrealistic. We need to decide on a trade-off involving responsiveness and consistency properties; the correctness of this trade-off must be asserted by the application. Deciding on a good trade-off is hard because it may only be possible to do so accurately at run-time. This is due not only to the varying environment, but also because the environment cannot be fully characterized before run-time. A second important problem is that implementing correct distributed protocols, exhibiting bounded inconsistency in groups whose compositions evolve dynamically, is a challenge---involving significant design and development resources.

These two problems demand flexible consistency machinery whose complex and costly core should be reusable. The underlying problem is two-fold: fundamentals (which distributed properties should be made flexible?) and engineering/system (how do the consistency management machinery interact with the application's execution model?).

The CoRe [2] environment attempts to address these two problems. CoRe is built around an extensible library implementing generic consistency managers. A consistency manager embodies properties such as sequentiality [4], linearizability [3], causality [6], and space- or time-bounded constraints [1] for weaker consistency. It is implemented as a group of distributed fragments [5] cooperating to achieve an ordering of accesses accurate for the specified consistency properties. There is one fragment per replica 1. The consistency manager does not directly manage local access to a replica. CoRe requires the application to provide two abstract representations: intentions embody access type semantics while activities embody the execution model (the accesses themselves). An intention implements two predicates: one defining conflicting rules (used locally), and one identifying when distributed agreement is needed, given an access type. An activity has an interface close to the Current interface of the Corba transaction service [7]. The consistency manager orders abstract accesses, which embody opaque data (functionality or state), by interacting with the activities.

The application's state is perceived by the consistency manager only through the intention interface. This independence with respect to representation allows traditional objects, plain memory, or even a virtual replicated state, to be managed by the consistency manager.

Work is still in progress. Only one linearizable consistency manager is running, used by a cooperative extension to Emacs and a trivial resource simulator. We intend to create a more convincing demonstration by incorporating accurate consistency protocols into the ACM flight simulator. We are also studying how to transform agreement requirements into an accurate continuous function, modeling bounded-divergence of replicas in the spirit of epsilon-serialisibility [8] divergence control.


1 Each cache is a replica of the whole shared information.
Last modified: Mon Aug 11 16:35:41 MET DST 1997