Abstract
The work presented in this master thesis belongs to CSCW
(Computer Supported Cooperative Work) research field; precisely, it is
a contribution to the cooperative editing of documents and its goal is, the
production of an algorithm that can merge partial replicas of a structured
document. In fact, in an asynchronous cooperative editing workflow of a
structured document, each of the co-authors receives in the different phases of
the process, a copy of the document in which he inserts his contribution.
Sometimes, to increase confidentiality and cooperation, this copy may only be a
partial replica containing just some parts of the (global) document which are
of demonstrated interest for the considered co-author. Note that some parts may
interest more than one co-author; those parts will therefore be accessible and
editable concurrently. When comes the synchronization time (at the end of a
phase of the process for example), a merging of all contributions of all
authors in a single document should be made. Due to the asynchronism of edition
and to the potential existence of the document parts offering concurrent
access, conflicts may arise when merging and make partial replicas unmergeable
in their entirety: those replicas are inconsistent or in conflict. We propose
in this master thesis, a merging approach (based on the cooperative edition
model presented in [BTT08, BTT07, TT09]) said by consensus of such partial
replicas using tree automata. Specifically, from the updated partial replicas,
we build a tree automaton that accepts and/or generates exactly the maximum
prefixes containing no conflict of partial replicas merged. These maximum
prefixes are the consensus documents.
Keywords : Structured documents, Worflow of
cooperative edition, Merging partial replicas, Conflict, Consensus, Tree
automata, Automata product, Lazy evaluation, TinyCE v2.
1
Introduction
Sommaire
Le contexte du travail 1
La problématique étudiée 2
Le travail réalisé 3
Organisation du manuscrit 3
Le contexte du travail
La coopération et la collaboration apparaissent de nos
jours comme des valeurs essentielles pour les entreprises, les
différentes instances municipales et gouvernementales, les
établissements de santé, les grandes institutions d'enseignement
et autres... Réunir plusieurs acteurs (spécialistes) autour d'un
objectif commun est donc devenu un véritable challenge [Gir14]. C'est
dans ce contexte que le Travail Coopératif Assisté par
Ordinateur (TCAO ou CSCW - Computer Supported Cooperative
Work - en anglais) a vu le jour et a évolué. Le domaine du
CSCW a favorisé la mise sur pied de nombreux logiciels (group-ware
ou systèmes de CSCW) et de plusieurs approches
scientifiques pour la résolution des problèmes causés par
le CSCW : ces problèmes sont liés essentiellement aux contraintes
d'espace (la situation géographique de chaque acteur) et de temps (le
mode de communication entre les acteurs). Les systèmes de CSCW
permettent de mettre en relation plusieurs acteurs répartis dans le
temps, l'espace et à travers les organisations afin que ces derniers
coordonnent leurs actions pour l'accomplissement d'une tâche
précise.
Un exemple très présent de CSCW est
l'édition coopérative des documents. En effet, on
rencontre de plus en plus le scénario des auteurs situés sur des
sites géographiquement éloignés qui se coordonnent pour
éditer de façon asynchrone un même document (c'est le cas
par exemple de plusieurs chercheurs rédigeant un même article de
recherche). D'autres cas de CSCW reposent parfois sur l'édition
coopérative des documents; puisque ceux ci (les documents) sont de plus
en plus utilisés pour l'échange des informations entre
applications. Les documents constituent de ce fait, une véritable aide
à la coordination.
Les documents électroniques peuvent être
répartis en trois groupes : les documents linéaires, les
documents semi-structurés et les documents
structurés [Bon98]. Nous nous intéressons ici aux
documents structurés.
Les documents structurés
Ce sont des documents qui présentent une structure
régulière définie par un modèle
générique appelé modèle de document : ce
sont généralement des grammaires (modèles
La problématique étudiée 2
Mémoire - ZEKENG NDADJI Milliam Maxime
LIFA
grammaticaux). La structure régulière
et l'interopérabilité de tels documents en ont fait de
véritables outils d'échange entre applications
hétérogènes ou non. Les documents structurés
facilitent la coopération et la coordination des actions de plusieurs
personnes. Toutes ces caractéristiques couplées à la
puissance toujours croissante des réseaux de communication en terme de
débit et de sûreté, ont révolutionné la
façon d'éditer de tels documents. On est passé du
modèle classique, dans lequel un auteur édite son document en
local, à un modèle selon lequel plusieurs co-auteurs participent
à l'édition asynchrone d'un même document. On peut imaginer
plusieurs scénarios pour la réalisation de ce modèle
d'édition en ce qui concerne les documents structurés.
L'édition coopérative des documents
structurés
Le processus d'édition coopérative d'un document
structuré est enclenché par l'un des co-auteurs; en effet, il
crée sur le serveur central, un document initial conforme à un
modèle donné. Ensuite, ledit document est distribué
à tous les co-auteurs pour qu'ils y insèrent, sur leurs sites
respectifs (en local), leurs contributions (phase de distribution). Une fois
que tous les différents co-auteurs ont édité leurs copies
respectives (conformément à un modèle local) du document,
il faut fusionner toutes leurs contributions, pour obtenir un document global :
on parle de synchronisation. Le document global obtenu, pourra
éventuellement être redistribué pour la suite de
l'édition.
L'édition coopérative des documents
structurés est un problème d'actualité en raison de la
forte utilisation de ces derniers dans les systèmes informatiques
modernes. Une approche d'édition coopérative asynchrone des
documents structurés [BTT08, BTT07, TT09] consiste, pour des raisons de
confidentialité, à associer une"vue" à chaque co-auteur.
La vue d'un co-auteur donné indique ainsi, les parties du document
auxquelles ce dernier a accès. De ce fait, pour chaque co-auteur, le
document global est répliqué suivant sa vue (on dit qu'il est
projeté), et la copie présente sur chaque site est donc une
réplique partielle du document global. Quand arrive un point de
synchronisation, on réalise la projection inverse de chaque
réplique partielle, pour obtenir des documents conformes au
modèle global, puis on fusionne les documents ainsi obtenus en un
document global.
La fusion des documents est une problématique assez
ancienne qui a déjà été étudiée dans
plusieurs contextes : le contexte des documents structurés XML [Ask94,
CSGM, CSR+, LF02, Lin04, Man01], le contexte des bases de
données, le contexte des programmes informatiques [Men02]... En ce qui
concerne l'édition coopérative des documents structurés,
il existe une approche de fusion des répliques partielles basée
sur les automates d'arbres [BTT08, BTT07, TT09].
La problématique étudiée
Pendant la fusion des documents structurés, on
recherche un document global intégrant les mises à jour de tous
les co-auteurs. À ce niveau, il peut surgir deux problèmes :
L'ambiguïté : on peut trouver
plusieurs documents satisfaisant ce critère de recherche. Ce
problème est en général dû à un défaut
de conception du modèle de document et une bonne analyse pourrait
permettre d'y remédier.
Les conflits : les modifications
portées par les différents co-auteurs peuvent ne pas être
compatibles. Cet état de chose rend impossible l'obtention d'un document
global qui intègre les mises à jour de tous les co-auteurs. Pour
éviter (anticiper) ce problème, on pourrait contrôler
les éditions locales afin d'assurer la cohérence et ainsi,
la compatibilité des
L'organisation du manuscrit 3
Mémoire - ZEKENG NDADJI Milliam Maxime
LIFA
répliques partielles. On pourrait aussi, à
posteriori, réconcilier les différentes répliques
partielles : c'est à dire remettre en cause certaines actions
d'édition pour rendre les répliques fusionnables.
Le problème que nous étudions dans ce
mémoire est celui de la réconciliation des répliques
partielles d'un document structuré; plus précisément nous
voulons proposer un algorithme capable de détecter et d'annuler les
actions d'édition menant aux conflits puis de fusionner les nouvelles
répliques obtenues.
Le travail réalisé
Un document en cours d'édition est
représenté par un arbre contenant, potentiellement au niveau des
feuilles, des noeuds ouverts ou bourgeons. Éditer un document, consiste
à développer (remplacer) un ou plusieurs de ses bourgeons par un
ou plusieurs sous-arbres conformément au modèle de document.
Fusionner consensuellement les mises à jour
t1 ···tn de n
répliques partielles d'un document t, consiste à
trouver un document tc, conforme au modèle de
document (appelé modèle global dans la suite), intégrant
tous les noeuds des ti non en conflit et dans lequel, tous les noeuds
en conflit sont remplacés par des bourgeons. L'algorithme de fusion
consensuelle présenté dans ce mémoire est une adaptation
de celui de fusion proposé dans [BTT08] qui ne gère pas les
conflits. Techniquement, la démarche permettant d'obtenir les documents
faisant partie du consensus est la suivante:
1. Pour chaque mise à jour tma
j
i d'une réplique partielle, nous associons un
automate d'arbre à états de sortie (i)
reconnaissant les arbres (conforme au modèle global) dont
tma j
i est une projection.
2. L'automate consensuel (sc) engendrant
les documents du consensus est obtenu en effectuant un produit synchrone
des automates (i) au moyen d'un opérateur
commutatif noté ØÙ : (sc) =
ØÙ i (i) que nous
définissons.
L'automate consensuel obtenu est celui qui produit les
documents du consensus : c'est à dire les préfixes maximaux sans
conflits de la fusion des documents issus des différentes expansions des
diverses répliques partielles mises à jour.
Nous avons aussi proposé une implémentation en
Haskell de notre algorithme, puis nous avons construit un prototype de
réconciliateur graphique en Java pour pouvoir réaliser nos
tests.
L'organisation du manuscrit
La suite de ce mémoire est structurée en quatre
chapitres et deux annexes organisés comme suit:
Chapitre 1 - Notions d'édition
coopérative et de conflits. Nous présentons ici la
notion de travail coopératif et les notions qui lui sont connexes
(groupware, workflow...). Nous nous focalisons ensuite sur la
notion d'édition coopérative des documents (les types de
documents édités, la détection des conflits, la
résolution des conflits) et sur le rôle et la circulation de
ceux-ci dans les procédures d'entreprise.
Chapitre 2 - L'édition coopérative des
documents structurés. Dans ce chapitre, nous présentons
une approche d'édition coopérative et les outils formels issus de
la littérature (grammaires algébriques, automates d'arbre...) que
nous utilisons pour la spécification et
L'organisation du manuscrit 4
Mémoire - ZEKENG NDADJI Milliam Maxime
LIFA
la manipulation des documents structurés, puis nous
introduisons de façon plus formelle et en accord avec [BTT08, BTT07,
TT09] les définitions relatives aux notions de vues, de projection, de
projection inverse et de fusion des répliques partielles d'un document
structuré.
Chapitre 3 - Fusion consensuelle des
mises à jour des répliques partielles. Nous
présentons dans ce chapitre notre solution au problème de la
réconciliation des répliques partielles d'un document
structuré.
Chapitre 4 - Un prototype
d'éditeur coopératif désynchronisé. Dans
ce chapitre, nous présentons TinyCE v2 (a Tiny Cooperative
Editor version 2, prononcer"taï-ni-ci-i"), un prototype
expérimental d'éditeur coopératif
désynchronisé inspiré de TinyCE (prononcer
"tennesse") [TT10] et qui nous permet de mettre en oeuvre les algorithmes
présentés dans ce travail et d'en faire la
démonstration.
Conclusion générale. Nous
réalisons le bilan de notre travail et nous répertorions quelques
perspectives d'amélioration de ce dernier.
Annexe A - Un autre exemple complet
de fusion consensuelle. Dans cette annexe, nous illustrons notre
algorithme de fusion consensuelle en l'appliquant à un workflow
d'édition sans conflit et dont les répliques partielles mises
à jour ne sont pas forcément des documents clos.
Annexe B - Quelques fonctions Haskell
pour le calcul des consensus. Nous donnons le code Haskell des
algorithmes qui ont été présentés ainsi que
quelques commentaires nécessaires pour une bonne
compréhension.
5
| 
