Theel, Oliver
- Raynal, Michel
Rapport de recherche de l'INRIA -
Rennes ,
Equipe : ADP
30 pages - Octobre 1996 - Document en anglais
Titre français : Mécanismes et politiques de cohérence pour la gestion des données réparties
Abstract : Consistency criteria adopted for the management of persistent replicated objects in a distributed system define the degree of concurrency allowed among operations accessing objects. Several notions of consistency are known from the literature, among them are causal consistency, causal serializability, and serializability. In this paper, we propose a generalizing algorithm for concurrency control in a transaction system that exhibits a clean separation between policy and mechanism. A consistency criterion selected is manifested as a set of rules forming the policy. The mechanism, however, remains unchanged regardless of the currently used policy. The mechanism implements causally consistent message delivery and uses tokens and quorums of tokens to enforce access operation ordering according to the specified consistency criterion. Since a policy is implemented as a set of rules, switching on-the-fly from one consistency criterion to another one can easily be done whenever changes in access patterns or cost/availability requirements suggest a modification. An example of an application exploiting the advantages of switching among various consistency criteria concludes the paper.
Résumé : Depuis la sérialisabilité jusqu'à la cohérence causale, plusieurs critères de cohérence sont envisageables pour les données gérées dans les systèmes répartis. Le choix d'un critère particulier relève à la fois de la nature des données et de l'application qui les manipule. Cet article propose une approche modulaire pour mettre en oeuvre toute une famille de critères de cohérence. La première partie définit un ensemble de mécanismes généraux à partir desquels peuvent facilement être implantés des critères particuliers. Ces mécanismes sont fondés sur des jetons et des vecteurs de version. La seconde partie montre comment un critère de cohérence particulier peut être defini par un ensemble de règles de synchronisation. L'interprétation de ces règles par les mécanismes précédents offre alors une mise en oeuvre particulière du critère concerné. Un avantage de l'approche proposée réside dans la possibilité de changer statiquement ou dynamiquement le critère de cohérence. L'intérét de telles modifications du critère de cohérence est illustré à l'aide d'un exemple pertinent (positionnement et controle d'un véhicule en présence d'obstacles
Key-Words : DISTRIBUTED SYSTEMS / DISTRIBUTED TRANSACTIONS / TRANSACTIONAL CONSISTENCY /
CAUSAL CONSISTENCY / CAUSAL SERIALIZABILITY / SERIALIZABILITY / TOKEN-BASED
ALGORITHMS / QUORUM SCHEMES
Mots-clés : SYSTÈMES DISTRIBUÉS / TRANSACTIONS DISTRIBUÉS / COHÉRENCE DES TRANSACTIONS /
COHÉRENCE CAUSALE / SÉRIALISABILITÉ CAUSALE / SÉRIALISABILITÉ / ALGORITHMES À
JETONS / QUORUMS
