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

3.2.2. Construction de l'automate du consensus

La prise en compte des documents avec des bourgeons nécessite le réaménagement de certains modèles utilisés. Par exemple, dans ce qui suit, nous manipulerons les automates d'arbre avec états de sortie en lieu et place des automates d'arbre introduits dans la définition 12. Intuitivement, un état q d'un automate est qualifié d'état de sortie s'il ne lui est associé qu'une unique transition q ? (X_e,[]) permettant de reconnaître un arbre réduit à un bourgeon de type X ? L. Ainsi, un automate d'arbre à états de sortie J1 est un quintuplet (L,Q,R,q0,exit) où L,Q,R,q0 désignent les mêmes objets que ceux introduits dans la définition 12, et exit est un prédicat défini sur les états (exit: Q ? Bool). Tout état q de Q pour lequel exit q est Vrai est un état de sortie.

Nous définissons un automate d'arbre à états de sortie par le type Haskell suivant:

data Automata p q = Auto {exit::q -> Bool, next::q -> [(p, [q])]}

dans lequel, le type générique (variable de type) p est le type des productions qui étiquettent les transitions et q est celui des états de l'automate. L'automate est défini ici au moyen de deux sélecteurs : exit qui est un prédicat sur les états ayant pour type Haskell

Mémoire - ZEKENG NDADJI Milliam Maxime LIFA

3.2. Calcul du consensus 37

exit :: Automata p q -> q -> Bool, permet de déterminer si un état q d'un automate donné est un état de sortie. La fonction next qui implémente la fonction de transition, a pour type Haskell next :: Automata p q -> q -> [(p, [q])], et retourne la liste des états accessibles à partir d'un état q donné d'un automate.

Comme dans [BTT08, TT09, BTT07], nous représentons une vue par un ensemble de prédicats sur les symboles de la grammaire. La fonction gram2autoview [BTT08, TT09, BTT07] (dont le code est donné dans l'annexe B) permet de construire un automate capable de reconnaître les documents globaux qui sont des expansions d'une réplique partielle suivant une vue donnée. Un état de l'automate généré par gram2autoview, est de la forme (Tag symb, ts) et permet de reconnaître (ou d'engendrer) l'ensemble des arbres de dérivation ayant symb pour racine et ts pour projection suivant une vue donnée. On dira qu'un tel état est de type symb. Le type Tag, permet de distinguer les états de sortie (lorsque la donnée est construite à l'aide de Open) des autres états (lorsqu'elle est construite au moyen de Close). Ainsi, le type Tag est défini comme suit :

data Tag x = Close x | Open x deriving (Eq,Show)

Dans la section 3.2.1 ci-dessus, nous avons dit que, "lorsque les types des noeuds racines de deux arbres sont différents, on dit qu'ils n'admettent pas de consensus". On peut, à partir de cet extrait et de la définition des automates, déduire que, "deux automates admettent un consensus (sont consensuels) si et seulement si leurs états initiaux sont du même type". En effet, si leurs états initiaux q¹₀ de la forme (Tag symb1,ts1) et q²₀ de la forme (Tag symb2,ts2) sont de même type, alors symb1 == symb2, et ces états permettent de générer des arbres ayant comme racine un noeud de type "symb1". On a donc la fonction haveConsensus suivante, qui permet de déterminer si deux automates admettent un consensus à partir de deux états initiaux donnés; cette fonction utilise la fonction untag permettant de débarrasser un symbole de son "Tag" :

1 haveConsensus :: Eq symb => (Tag symb, t) -> (Tag symb, t1) -> Bool

2 haveConsensus state1@(tagsymb1, ts1) state2@(tagsymb2, ts2)=

3 (untag tagsymb1) == (untag tagsymb2)

4

5 untag :: Tag x -> x

6 untag (Open x) = x

7 untag (Close x) =x

Dans cette même section (sect. 3.2.1), nous avons aussi dit que, "quand deux noeuds sont en conflit, ils apparaissent dans l'arbre consensuel sous la forme d'un (unique) bourgeon". Du point de vue de la synchronisation d'automates, la notion de "noeuds en conflit" se traduit par la notion "d'états en conflit" (qui est précisée ci-dessous) et l'extrait précédent se traduit par "quand deux états sont en conflit, ils apparaissent dans l'automate du consensus sous la forme d'un (unique) état de sortie". Ainsi, si on considère deux familles de transitions

1 1 1 1 1 nl n1 2 2 2 2 272 n2_q

[(a₁,[q₁,··· q_m1]),...,(a_n1,[e ,···,q_m2])] et q-- [(a[q···,q_p1]),...,(a_n2,[q_l ,···,q_p2])]

associées aux états q¹₀ et q²₀ de deux automates d'arbre auto1 et auto2, on dira que les états q¹₀ et q²₀ (qui ne sont pas des états de sortie) sont en conflit (et on note q10 y q20) s'il n'existe pas de transition partant de chacun d'eux et portant la même étiquette, c'est à dire qu'il n'existe aucune étiquette de transition a³ telle que (a³,[q³₁,...,q³_n3]) appartient à [(a¹₁,[q¹₁,··· ,q¹ _m1]),...,(a¹ n1,[qn1 1 ,··· ,qⁿ¹_m2])] et (a³,[q⁴₁,...,q⁴_n4]) appartient à la famille [(a² ₁,[q² ₁,···,q² _p1]),...,(a² n2,[qn2 1 ,··· ,qⁿ²_p2])].

Mémoire - ZEKENG NDADJI Milliam Maxime LIFA

	3.2. Calcul du consensus		38
1	autoconsens::(Eq a1, Eq a) =>(a -> a1) -> Automata a1 (Tag a, [t1])
2	-> Automata a1 (Tag a, [t]) -> Automata a1 ((Tag a, [t1]), (Tag a,	[t]))
3	autoconsens symb2prod auto1 auto2 = Auto exit_ next_ where
4	exit_ (state1,state2) = case haveConsensus state1 state2 of
5	True -> (exit auto1 state1) && (exit auto2 state2)
6	False -> True
7
8	next_ (state1,state2) = case haveConsensus state1 state2 of
9	False -> []
10	True -> case (exit1,exit2) of
11	(False,False) -> case (isInConflicts state1 state2) of
12	True -> [(symb2prod(typeState state1),[])]
13	False -> [(a1,zip states1 states2) |
14	(a1,states1) <- next auto1 state1,
15	(a2,states2) <- next auto2 state2,
16	a1==a2, (length states1)==(length states2)]
17
18	(False,True) -> [(a, zip states1 (forwardSleepState states1))	|
19	(a,states1) <- next auto1 state1]
20
21	(True,False) -> [(a, zip (forwardSleepState states2) states2)	|
22	(a,states2) <- next auto2 state2]
23
24	(True,True) -> [(a1,[]) | (a1,[]) <- next auto1 state1,
25	(a2,[]) <- next auto2 state2, a1==a2]
26
27	where
28	exit1 = exit auto1 state1
29	exit2 = exit auto2 state2
30	forwardSleepState states = map (\state -> (Open (typeState state),	[]))	states
31	typeState state@(tagsymb, ts1) = (untag tagsymb)
32	isInConflicts state1@(tagsymb1, ts1) state2@(tagsymb2, ts2) =
33	null [(a1,zip states1 states2) |
34	(a1,states1) <- next auto1 state1,
35	(a2,states2) <- next auto2 state2,
36	a1==a2, (length states1)==(length states2)]

algorithme 1 : algorithme de construction de l'automate du consensus

L'automate synchronisé consensuelJ1(sc) = ?Ù i J1(ⁱ) dont le processus de construction (pour deux automates) est décrit par l'algorithme 1 (écrit en Haskell [Has]) ci-dessus, est un automate à états de sortie. Il est obtenu en considérant lors du calcul du produit synchrone des automates J1(ⁱ) que:

1. un état q = (q¹,--- ,q^k) est un état de sortie si :

a) les états composites qⁱ n'admettent pas de consensus (algorithme 1 lignes 4 et 6) ou

b) tous les états composites qⁱ sont des états de sortie (algorithme 1 ligne 5).

2. quand un automate J1(j) quelconque a atteint un état de sortie⁵ (algorithme 1 lignes 18, 21 et 24), il ne contribue plus au comportement mais, ne s'oppose pas à la

5. Le noeud correspondant dans le document de la projection inverse est un bourgeon et traduit le fait que l'auteur correspondant ne l'a pas édité. Dans le cas où il serait partagé avec un autre co-auteur l'ayant édité dans sa réplique, c'est l'édition réalisée par ce dernier qui sera retenue lors de la fusion.

3.2. Calcul du consensus 39

Mémoire - ZEKENG NDADJI Milliam Maxime LIFA

synchronisation des autres automates : on dit qu'il est endormi. Un état endormi sera propagé convenablement pour ne pas s'opposer à la synchronisation des autres automates (algorithme 1 lignes 18 (second paramètre de la fonction zip) et 21); pour cela, on se sert de la fonction forwardSleepState (algorithme 1 lignes 30 et 31) pour "fabriquer" des états endormis. En fait, forwardSleepState prend une liste d'états en entrée et produit, en sortie, une liste d'états de sortie dont les types sont ceux des états pris en arguments.

Ainsi, pour k automates .91(ⁱ) = (Ó,Qi,Ri,q⁽ⁱ⁾

0 ,exiti) 1 < i < k, associés à k répliques par-

tielles, l'automate synchronisé consensuel .91(sc) = ®^Ù_i .91(ⁱ) est construit comme suit (algorithme 1) :

1. Ses états sont des vecteurs d'états : Q = Q1 x ··· x Qk ;

2. Son état initial est le vecteur formé des états initiaux des différents automates :

(1) k

q0 = (q₀ ,···,q₀ );

3. Ses transitions pour un état q = (q(¹),··· ,q(^k)) quelconque, sont données par :

a) Si les états composites de q sont non consensuels, alors q n'admet aucune transition (algorithme 1 lignes 8 et 9) ;

b) Si les états composites de q admettent un consensus, alors trois cas de figure se présentent :

i. Si aucun de ces états n'est de sortie et

qu'ils sont en conflit, alors q admet une transition vers un état de sortie dont le type est le même que celui de ces états composites (algorithme 1 lignes 11 et 12) ;

qu'ils ne sont pas en conflit, alors q génère des arbres dont le noeud racine est étiqueté par une production du type de ces états, et dont les fils sont générés par des états qui sont des couples formés à partir d'un état appartenant aux états suivants de chacun de ces états composites (algorithme 1 lignes 13 à 16) ;

ii. Si certains de ces états sont des états de sortie (ils sont endormis), alors q génère des arbres dont le noeud racine est étiqueté par une production du type de ces états et appartenant aux suivants des états qui ne sont pas de sortie, et dont les fils sont générés par des états qui sont de la forme ((Tag symb, ts), (Open symb, [])), formés à partir d'états (de la forme (Tag symb, ts)) appartenant aux états suivants de l'état non de sortie (algorithme 1 lignes 18 à 22) ;

iii. Si ces états sont tous des états de sortie (q est un état de sortie), alors q admet une transition vers un état de sortie de type, le type de ces états (algorithme 1 lignes 24 et 25).

®^Ù_i est donc une relaxation de la synchronisation d'automates que nous avons intro-

duite dans la définition 14 et 2' _(.91(sc), (q_tmaj)) = consensus(2' (.91(ⁱ), q_tmaj)). Il ne reste plus

Vi Vi

qu'à appliquer notre générateur à _.91(sc) comme dans [BTT08] pour obtenir les documents les plus simples qu'il accepte, c'est à dire ceux du consensus.