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

1.2.3. Conflits dans les systèmes d'édition coopérative, méthodes de détection et approches de résolution

Lorsque l'édition coopérative est appliquée dans un environnement distribué asynchrone, on peut envisager que chaque site possède des copies d'un même document. Ces copies (qu'on appelle répliques ou réplicats en accord avec [SS05]) peuvent être modifiées par les différents co-auteurs. Il arrive un moment où on voudrait obtenir un autre document de base intégrant les mises à jour portées sur les différentes répliques : il faut alors fusionner ces dernières. La fusion ou synchronisation des répliques d'un document peut être définie de manière informelle [TT09] comme une opération qui consiste à fusionner les mises à jour effectuées de façon désynchronisée sur ces répliques par rapport au document de base afin d'obtenir une nouvelle copie du document de base qui intègre éventuellement toutes les modifications des différentes répliques dans le cas où elles sont non conflictuelles, ou éventuellement des indications sur les sources de conflits.

L'opération de fusion se déroule généralement en deux phases [TT09] : la phase de détection des mises à jour pendant laquelle on identifie dans les différentes répliques, les endroits qui ont été mis à jour depuis la dernière synchronisation, et la phase de réconciliation dans laquelle on combine les différentes mises à jour pour produire un nouveau document (sans conflits). Il existe plusieurs techniques de fusion dans la littérature. Nous pouvons citer les fusions two-way, three-way, textuelle, sémantique, syntaxique et structurelle. Ces techniques sont bien présentées et comparées dans [Men02]. Elles diffèrent principalement par leurs capacités à détecter et à résoudre les conflits.

L'un des problèmes majeurs posés par l'opération de fusion est la gestion des conflits. Dans le cas de l'édition coopérative des documents, les conflits représentent les différentes parties pour lesquelles les répliques divergent. Les sources des conflits sont en général les mises à jour apportées à différentes répliques par différents co-auteurs. Toutefois, dans un contexte où l'édition n'est pas positive, ¹⁸ une seule mise à jour peut entraîner des conflits. On distingue principalement les conflits d'ordre syntaxique, sémantique ou structurel. Les

17. Bizagi Modeler est disponible à l'adresse http://www.bizagi.com/.

18. Dans une édition positive basée sur une réplication optimiste, les documents édités ne font que croître: il n'y a pas d'effacement possible dès qu'une synchronisation a été effectuée [SS05].

1.2. Un exemple de CSCW : L'édition coopérative 16

Mémoire - ZEKENG NDADJI Milliam Maxime LIFA

Administration de la Faculté des sciences de l'université de Dschang

Département 3

Département 2

Département 1

Scolarité

I I^r Enregistrer le ^1J~^1 dossier Reception L d'un dossier de candidature

Traitement en parallèle par les départements.

·

Z. Ô m n

A a n [ m O

A Y 2_ n n

3 a a n m

3 3

4

rir une Vérifier de la existence de la dé. he fiche 'on

Vérifier l'existence de la fiche

Vérifier l'existence de la fiche

Si une copie de la fiche existe au département alors ily a un doublon. On termine surune erreur. - 7/

0O 0 a

2 Q o o a

â 7^.

â

n. û9

6

r

. 6 ^Ç 4.

6

\

-

O

l l

O

\

Ô

d L^,C m m

ro d 2. - - C m m i

!. - m

~/ O C i

I^llll

Ille . 2û O F a n 3o o ro

Fin de la séquence parallèle et synchronisation

Y

r Mettre a' ur le dossier du candidat 1 ^f Fin

FIGURE 1.4 - Un exemple de diagramme d'orchestration BPMN, illustrant le processus de sélection d'un étudiant dans une des filières de la FS UDs.

1.2. Un exemple de CSCW : L'édition coopérative 17

Mémoire - ZEKENG NDADJI Milliam Maxime LIFA

méthodes de détection des conflits sont nombreuses dans la littérature. Nous présentons certaines dans cette section ainsi que quelques approches de résolution des conflits. Le lecteur intéressé est invité à consulter [Men02] pour en savoir plus.

1.2.3.1. Les techniques de détection des conflits Les matrices de fusion [SLMD96, Fea89, MD94]

Une piste intéressante pour la détection des conflits lors de la fusion est l'analyse et la comparaison des mises à jour qui ont été portées sur les différentes répliques. On peut ainsi répertorier toutes les combinaisons des opérations de mises à jour qui sont susceptibles d'entraîner une inconsistance. Les combinaisons ainsi détectées sont stockées dans une matrice de fusion ou table de conflits. La détection des conflits se fait dans ce cas par simple consultation des entrées de la matrice de fusion [SLMD96]. Une approche un peu plus générale [Fea89] basée sur les matrices de fusion consiste à ne plus stocker dans ces dernières les opérations mais plutôt les changements qu'elles induisent. De cette façon, il est plus facile d'introduire de nouvelles opérations sous la condition que celles ci n'occasionnent que des changements déjà répertoriés dans la matrice de fusion. On peut aussi stocker dans la matrice de fusion, à coté des potentiels conflits, les actions à réaliser pour résoudre les conflits [MD94]. Le problème principal posé par les matrices de fusion est l'espace mémoire qu'elles occupent lorsqu'il faut fusionner plus de deux répliques.

Les ensembles de conflit [WK97]

Les ensembles de conflit [WK97] peuvent être utilisés à la place des matrices de fusion. Ils contiendront ainsi les combinaisons d'opérations pouvant entraîner des conflits. Ici, les opérations sont fortement liées à la sémantique des éléments à fusionner. On construit un ensemble de conflit pour chaque type de conflit susceptible d'apparaître lors de la fusion. Il faut donc connaître ces types de conflit à l'avance et, l'ensemble constitué de ces types est statique vu qu'il ne varie pas tant que la sémantique des éléments à fusionner est la même. Une même opération peut intervenir dans plusieurs ensembles de conflit et deux opérations appartenant au même ensemble de conflit sont susceptibles de créer des conflits si on essaie de les fusionner.

1.2.3.2. La résolution des conflits

Après la détection des conflits, il faut pouvoir les résoudre. Les approches de résolution dépendent énormément du type de conflit qui a été détecté. Ces approches de résolution peuvent être complètement manuelles (appliquées par un Homme), interactives (les correctifs sont appliqués avec l'accord d'un Homme) ou complètement automatisées.

Certains conflits proviennent juste du fait que l'opérateur de fusion soit non commutatif; l'ordre dans lequel l'opération de fusion est appliquée aux répliques devient alors crucial. La méthode de résolution est dans ce cas plutôt simple car il suffit de trouver le bon ordre pour l'application de l'opérateur de fusion [Men02].

Une autre stratégie de résolution des situations de conflit consiste à calculer toutes les solutions valides et de les proposer immédiatement aux co-auteurs pour que ces derniers décident de la solution à appliquer. Bien entendu cette approche dite d'explosion [WK97] peut être difficile à mettre en oeuvre. En plus elle peut entraîner une explosion combinatoire (ensemble de solutions valides très grand). Une autre façon (appelée réconciliation [MD94]) de procéder serait de ne prendre en compte aucune des mises à jour menant à un

1.3. Synthèse 18

Mémoire - ZEKENG NDADJI Milliam Maxime LIFA

conflit et, peut être de remplacer le noeud correspondant au conflit par un noeud neutre dans le document global obtenu : c'est cette approche que nous adoptons. De ce fait, les co-auteurs pourront rééditer ou choisir une édition valide déjà réalisée pour remplacer ces noeuds neutres. On pourrait même envisager le calcul de l'ensemble des solutions valides grâce à la stratégie d'explosion, et ainsi créer une stratégie hybride (appelée consolidation [MD94]).

Les conflits peuvent être prévenus, réduits ou même évités si on fixe les bonnes pré-conditions à l'avance. Si on considère par exemple un cas d'édition dans lequel chaque co-auteur est chargé de rédiger une partie (un noeud) bien précise et distincte du document, alors les conflits seront énormément réduits voire inexistants. Dans un autre cas où plusieurs co-auteurs pourraient éditer un même noeud, on peut définir une hiérarchie entre ces co-auteurs et ainsi définir un ordre de priorité sur les différentes contributions; la pré-condition stipulant qu'en cas de conflit la contribution à retenir est celle qui a la plus haute priorité, permet de résoudre certains conflits.