Coherence of Shared Replicated Data within Groups of Remote Cooperating Processes
Cohérence de données répliquées partagées par un groupe de processus coopérant à distance
Résumé
Cooperative applications must communicate in order to make progress, and are therefore inherently affected by communication latency. In wide-area settings this latency can increase to a point where traditional consistency management no longer provides sufficient reactivity -- in some cases making the application unusable. We address this problem by considering a cooperative application to be a collection of cooperating replicas, and then concentrate on the management of consistency within such a group of replicas.
This problem is significant for two reasons: it appears in any application domain where we have cooperation between human agents, and is a fundamental part of the structure of cooperation mechanisms. Our comprehensive study of "weak consistency" covers four domains: transactional systems, distributed shared memories, distributed shared objects, and platforms for group communication. Our contribution has three significant aspects:
1.
We present a new model of execution that is free of causal dependencies. It is based on replicated histories, and is used to formalise the consistency criteria presented in this document.
2.
We present a new model of sharing, cooperative replication -- a derivative of active replication that does not impose a unique global ordering on the execution of operations. Replicas are autonomous except when their local view of the global computation can no longer guarantee correct behaviour of the distributed application.
3.
We present a few system principles with which we define a new component, the consistency manager. This component:
manages the cooperation between replicas and implements the most complex parts of consistency management: the control of distribution, replication and concurrency;
provides a consistency contract that imposes deterministic properties on distributed operations. These can be considered as the "correctness criteria" for the distributed application;
is bound dynamically to the application at execution time; and
is reusable.
We have implemented Core -- a complete development environment conforming to the above principles -- that runs on Unix, is documented, and freely available by FTP. Core provides the usual services for distributed applications (a name service, group communication and management of group membership, for example), as well as an extensible class library with which specific consistency managers can be developed. It also provides numerous classes with which application designers can implement new kinds of shared object. Two example applications have been built using Core: an extension to Emacs that permits collaborative editing, and a simple manager for shared resources.
This problem is significant for two reasons: it appears in any application domain where we have cooperation between human agents, and is a fundamental part of the structure of cooperation mechanisms. Our comprehensive study of "weak consistency" covers four domains: transactional systems, distributed shared memories, distributed shared objects, and platforms for group communication. Our contribution has three significant aspects:
1.
We present a new model of execution that is free of causal dependencies. It is based on replicated histories, and is used to formalise the consistency criteria presented in this document.
2.
We present a new model of sharing, cooperative replication -- a derivative of active replication that does not impose a unique global ordering on the execution of operations. Replicas are autonomous except when their local view of the global computation can no longer guarantee correct behaviour of the distributed application.
3.
We present a few system principles with which we define a new component, the consistency manager. This component:
manages the cooperation between replicas and implements the most complex parts of consistency management: the control of distribution, replication and concurrency;
provides a consistency contract that imposes deterministic properties on distributed operations. These can be considered as the "correctness criteria" for the distributed application;
is bound dynamically to the application at execution time; and
is reusable.
We have implemented Core -- a complete development environment conforming to the above principles -- that runs on Unix, is documented, and freely available by FTP. Core provides the usual services for distributed applications (a name service, group communication and management of group membership, for example), as well as an extensible class library with which specific consistency managers can be developed. It also provides numerous classes with which application designers can implement new kinds of shared object. Two example applications have been built using Core: an extension to Emacs that permits collaborative editing, and a simple manager for shared resources.
La progression des applications coopératives est confrontée, de façon inhérente, à la latence des moyens de communication. Lorsque celle-ci devient importante, les modèles de cohérence traditionnels entraînent un manque de réactivité rédhibitoire. Nous attaquons ce problème, en réduisant une application coopérative à une collection de réplicats coopérants, puis en se focalisant sur la gestion de cohérence d'un tel groupe de réplicats.
Ce problème est important par deux aspects : par son application dans tous les domaines impliquant la coopération d'individus et par son caractère fondamental dans la structuration et la compréhension des mécanismes de coopération.
Notre étude critique, des critères de cohérence associés aux cohérences dites «faibles», embrasse quatre domaines : les systèmes transactionnels, les mémoires partagées réparties, les objets concurrents et les plate-formes de communication. Notre thèse contribue sur trois points :
Notre modèle d'exécution est libre de tout a priori concernant la causalité des opérations. Ce modèle est basé sur des histoires répliquées.
Notre modèle de partage, la réplication coopérante, dérivée de la réplication active, n'impose pas un ordre commun unique sur l'exécution des opérations. Les réplicats sont autonomes et ne coopèrent que lorsque leur vue de l'histoire globale ne suffit plus à garantir la correction de l'application.
Nos principes systèmes permettent de construire un nouveau type de composant, le gestionnaire de cohérence . Ce composant :
prend en charge la coopération des réplicats. Il implante la partie complexe de la gestion de cohérence : le contrôle de la distribution, de la réplication et de la concurrence ;
maintient, sur l'ordre réparti des opérations, des propriétés déterministes. Ces propriétés définissent un contrat de cohérence ; elles peuvent être utilisées comme critère de correction ;
est choisi à l'exécution par l'application ;
est réutilisable.
Nous avons réalisé Core, une plate-forme de développement complète, partiellement documentée et accessible sur FTP, développée au-dessus d'Unix. Core offre, outre les services usuels nécessaires à la mise en oeuvre de groupes de processus répartis, une bibliothèque extensible de gestionnaires de cohérence. Core offre aussi de nombreuses classes, utilisées tant pour la réalisation de nouveaux gestionnaires que pour l'expression de nouveaux types et modèles d'exécution, par les concepteurs d'applications. Nous avons réalisé, avec Core, deux applications : une application d'édition coopérative basée sur Emacs et une simulation de ressource partagée.
Ce problème est important par deux aspects : par son application dans tous les domaines impliquant la coopération d'individus et par son caractère fondamental dans la structuration et la compréhension des mécanismes de coopération.
Notre étude critique, des critères de cohérence associés aux cohérences dites «faibles», embrasse quatre domaines : les systèmes transactionnels, les mémoires partagées réparties, les objets concurrents et les plate-formes de communication. Notre thèse contribue sur trois points :
Notre modèle d'exécution est libre de tout a priori concernant la causalité des opérations. Ce modèle est basé sur des histoires répliquées.
Notre modèle de partage, la réplication coopérante, dérivée de la réplication active, n'impose pas un ordre commun unique sur l'exécution des opérations. Les réplicats sont autonomes et ne coopèrent que lorsque leur vue de l'histoire globale ne suffit plus à garantir la correction de l'application.
Nos principes systèmes permettent de construire un nouveau type de composant, le gestionnaire de cohérence . Ce composant :
prend en charge la coopération des réplicats. Il implante la partie complexe de la gestion de cohérence : le contrôle de la distribution, de la réplication et de la concurrence ;
maintient, sur l'ordre réparti des opérations, des propriétés déterministes. Ces propriétés définissent un contrat de cohérence ; elles peuvent être utilisées comme critère de correction ;
est choisi à l'exécution par l'application ;
est réutilisable.
Nous avons réalisé Core, une plate-forme de développement complète, partiellement documentée et accessible sur FTP, développée au-dessus d'Unix. Core offre, outre les services usuels nécessaires à la mise en oeuvre de groupes de processus répartis, une bibliothèque extensible de gestionnaires de cohérence. Core offre aussi de nombreuses classes, utilisées tant pour la réalisation de nouveaux gestionnaires que pour l'expression de nouveaux types et modèles d'exécution, par les concepteurs d'applications. Nous avons réalisé, avec Core, deux applications : une application d'édition coopérative basée sur Emacs et une simulation de ressource partagée.