Réconciliation par consensus des mises à jour des répliques partielles d'un document structuré.

Chapitre3

Fusion consensuelle des mises à jour

des répliques partielles

Sommaire

3.1 - Problématique de la réconciliation par consensus 34

3.2 - Calcul du consensus 34

3.3 - Synthèse 43

La fusion des mises à jour portées sur les répliques partielles d'un document structuré est inévitable dans un processus d'édition coopérative asynchrone. Dans notre approche d'édition coopérative, elle consiste à trouver un document global qui intègre au mieux les contributions de chaque co-auteur, sachant que chaque co-auteur a édité sa réplique suivant un modèle grammatical local (dérivé du modèle global); le modèle local garantit la cohérence des mises à jour de la réplique partielle vis-à-vis du modèle global ¹ et assure ainsi la faisabilité de la fusion. Pour différentes raisons, plusieurs co-auteurs peuvent avoir le droit d'éditer un même noeud de façon concurrente. Cette considération couplée à l'asynchronisme de l'édition induit la possibilité que des mises à jour soient incohérentes ou conflictuelles; il faut donc pouvoir détecter ces conflits lors de la fusion et y remédier si possible. L'algorithme de fusion proposé dans [BTT08, BTT07] ne permet pas de remédier à de tels conflits. Nous proposons dans ce chapitre une instrumentalisation de cet algorithme, afin de détecter et éliminer (résoudre) les conflits lors de la fusion. Pour cela, nous nous servons d'un automate d'arbre dit du consensus, construit en faisant le produit synchrone des automates (à états de sortie) associés aux différentes répliques partielles à fusionner.

Ce chapitre est organisé comme suit : après avoir présenté le problème de la fusion consensuelle (sect. 3.1), nous définissons la notion d'automate d'arbre à états de sortie, et ensuite, nous proposons un algorithme (algorithme 1) pour la construction de l'automate du consensus (sect. 3.2).

1. Un modèle local garantit la cohérence des mises à jour d'une réplique partielle ti vis-à-vis du modèle global.

3.1. Problématique de la réconciliation par consensus 34

Mémoire - ZEKENG NDADJI Milliam Maxime LIFA

3.1. Problématique de la réconciliation par consensus

Dans un processus d'édition coopérative asynchrone d'un document, on peut permettre pour plusieurs raisons, à différents co-auteurs d'éditer une même partie dudit document ; on peut le faire, pour avoir différentes versions de ces parties et ainsi, avoir la possibilité de choisir une version satisfaisant, au mieux, les critères d'édition fixés à l'avance. De ce fait, quand on atteint un point de synchronisation, on peut se retrouver avec des répliques non fusionnables dans leur entièreté car, contenant des mises à jour non compatibles 2 : il faut les réconcilier. On peut le faire en remettant en cause (annulation) certaines actions des éditions locales afin de lever les conflits et aboutir à une version globale cohérente dite de consensus.

Les études portant sur la réconciliation des versions d'un document reposent sur des heuristiques [Men02] dans la mesure où il n'y a pas de solution générale à ce problème. Rappelons que dans notre cas, étant donné que toutes les actions d'édition sont réversibles ³ et qu'il est facile de localiser les conflits lors de la tentative de fusion des répliques partielles, nous disposons d'une méthode canonique pour éliminer les conflits : nous remplaçons lors de la fusion tout noeud (du document global) dont les répliques sont en conflit par un bourgeon. On élague donc au niveau des noeuds où un conflit apparaît, en remplaçant le sous arbre correspondant par un bourgeon du type approprié, indiquant que cette partie du document n'est pas encore éditée : les documents obtenus sont appelés les consensus. Ce sont les préfixes maximaux sans conflits de la fusion des documents issus des différentes expansions des diverses répliques partielles mises à jour.

Le problème de la fusion consensuelle de n répliques partielles dont le modèle global est donné par une grammaire G = (S,P,A) peut donc s'énoncer comme suit :

Problème de la fusion consensuelle : Étant donné k vues (Vi)1<i<k et k répliques partielles (tma j

Vi )1<i<k, fusionner consensuellement la famille (tma j

Vi )1<i<k consiste à rechercher les plus grands documents t^maj _S? G satisfaisant :

bi E 1,...,n \I ]ti ? G, ti ti₌ tmaj ðV_i(ti) < tNI

j

dans laquelle, la relation ti= permet de lier deux documents non en conflit qui sont éventuellement des mises à jour l'un pour l'autre.