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

3.2. Calcul du consensus

La solution que nous proposons au problème de la fusion consensuelle découle d'une instrumentalisation de celle proposée pour l'expansion dans [BTT08, BTT07, TT09] et décrite précédemment (chap. 2 sect. 2.3). En effet, nous définissons un opérateur binaire

commutatif noté pour synchroniser les automates d'arbre A(ⁱ) construits pour réaliser
les différentes expansions afin de générer l'automate d'arbre de la fusion consensuelle. En notant _A(sc) cet automate, les documents du consensus sont les arbres du langage engendré par l'automate _A(sc) à partir d'un état initial construit à partir du tuple formé des états initiaux des automates A(ⁱ) : L _(A(sc), (q_tmaj)) = consensus{L (A(ⁱ), q_tma j)}. A(sc) est

Vi Vi

obtenu en procédant de la façon suivante :

2. C'est notamment le cas s'il existe au moins un noeud du document global accessible par plus d'un coauteur et édité par au moins deux d'entre eux en utilisant des productions différentes.

3. Rappel : Les actions d'édition effectuées sur une réplique partielle peuvent être annulées tant qu'elles n'ont pas encore été intégrées dans le document global.

1. 3.2. Calcul du consensus 35

Mémoire - ZEKENG NDADJI Milliam Maxime LIFA

Pour chaque vue v, construire l'automate 91(ⁱ) qui réalisera l'expansion de la réplique

partielle _tma j

Vi comme indiqué précédemment (chap. 2 sect. 2.3.3) : (91(ⁱ), q_tmaj) =

v

T_S

j ;

2. Au moyen de l'opérateur ?^Ù, calculer l'automate générant le langage du consensus ⁹¹(sc) = ?^Ù_i 91(ⁱ) ;

3. Générer les documents acceptés par ⁹1(sc) : ce sont ceux du consensus.

Avant de présenter l'algorithme du calcul du consensus, précisons en utilisant les notions introduites précédemment (chap. 2 section 2.1.1), les concepts de documents en conflit et de consensus entre plusieurs documents.

3.2.1. Consensus entre plusieurs (deux) documents

Soient t1,t2 : N^* ? A deux arbres (documents) en conflit de domaines respectifs Dom(t1) et Dom(t2) : si on appelle type la fonction qui retourne le type ⁴ d'un noeud en se servant de son étiquette, on dira que t1 et t2 n'admettent pas de consensus, et on note t1 Yt2, si les types de leurs noeuds racines sont différents. C'est dire (t1 Yt2) ? (type(t1(E)) =6 type(t2(E))). On dira alors que t1 et t2 sont en conflit, et on note t1 y t2, quand ils admettent un consensus mais ne sont pas fusionnables dans leur entièreté. Intuitivement, deux documents t1 et t2 (non réduits à des bourgeons) ne sont pas entièrement fusionnables, s'il existe une adresse w ? Dom(t1) n Dom(t2) telle que le type du noeud n1 situé à l'adresse w dans t1 est différent de celui du noeud n2 situé à la même adresse dans t2. Plus formellement, t1 y t2 s'il existe une adresse w ? Dom(t1) n Dom(t2) telle que t1(w) = t2(w) et au moins un des noeuds n1i,1 = i = n situés aux adresses w.i dans t1 a un type différent de celui du noeud n2i (lorsqu'il existe) situé à la même adresse dans t2. C'est à dire

(t1 y t2 avec t1(E) =6 X_W, t2(E) =6 X_W) ?

(non (t1 Yt2)) et (?w.i ? Dom(t1) nDom(t2), t1(w) = t2(w), type(t1(w.i)) =6 type(t2(w.i)))

Si t1 et t2 sont en conflit, l'arbre consensuel t_c : N^* ? A issu de t1 et t2 est tel que :

Le domaine de t_c est l'union des domaines des deux arbres auquel on soustrait les éléments appartenant aux domaines des sous-arbres issus des noeuds en conflit (on élague au niveau des noeuds en conflit).

Quand un noeud n1 de t1 est en conflit avec un noeud n2 de t2, ils apparaissent dans l'arbre consensuel t_c sous la forme d'un (unique) bourgeon.

Ainsi, ?w ? Dom(t_c) on a :

tc(w) =

{

t1(w) si t1(w) = t2(w) t1(w) si t2(w) = XW t2(w) si t1(w) = XW t1(w) si w ?/ Dom(t2) et ?u, v ? N^*tel que w = u.v, t2(u) = XW t2(w) si w ?/ Dom(t1) et ?u, v ? N^*tel que w = u.v, t1(u) = XW XW si t1(w) =6 XW et t2(w) =6 XW et t1(w) =6 t2(w)

La figure 3.1 (page 36) regroupe les étapes de la fusion consensuelle de deux documents t1 et t2 en un document tf. La fusion se fait par niveau hiérarchique du haut vers le bas. Chaque étape illustre certaines des alternatives contenues dans la formule ci-dessus ; les noeuds impliqués sont mis en évidence via des couleurs. Au niveau 3 par exemple, nous illustrons le traitement de deux noeuds en conflit (noeuds étiquetés C - en rouge -).

4. Rappel : on note X_W l'étiquette d'un bourgeon de type X ; et un noeud clos étiqueté A est de type A.

3.2. Calcul du consensus 36

Mémoire - ZEKENG NDADJI Milliam Maxime LIFA

FIGURE 3.1 - Fusion consensuelle progressive de deux documents.