|
Evènement pour le groupe Modélisation et Verification
Date | 2009-06-18 11:00-12:15 |
Titre | Edition Collaborative d'arbres XML |
Résumé | L'edition collaborative consiste à travailler sur un document commun de
manière distribuée et concurrente. Un problème essentiel est d'assurer la
cohérence du processus, car des opérations concurrentes peuvent etre
conflictuelles (ajouter ou supprimer une lettre à la meme position). De
nombreux systèmes reposent sur une centralisation implicite (par des
time-stamps par exemple) ou explicite (existence d'un site maitre comme avec
svn). L'approche Pair à Pair ne permet pas cette centralisation, et à tout
moment de nouveaux sites peuvent rejoindre le processus d'édition. Dans ce
cadre l'approche optimiste considère que toutes les opérations doivent etre
prises en compte, et utilise une approche transformationnelle pour intégrer
les opérations concurrentes: au lieu d'effectuer l'opération o2 concurrente à
o1, on effectue une opération modifiée IT(o1,o2). Quand l'opérateur de
transformation IT satisfait deux propriétés TP1 et TP2, il existe un
algorithme qui assure la convergence du processus (chaque site a la meme
copie du document à la fin du processus). Pour le cas des mots aucun des
jeux
d'opérations et des transformations proposées ne satisfont ces propriétés et
des contre-exemples montrent qu'ils n'assurent pas la convergence (cf thèse
d'A. Imine). Dans cet exposé nous nous intéressons à l'édition des arbres
étiquetés non-ordonnés avec des opérations d'ajout, suppression ou
réétiquetage. Le premier résultat est de montrer qu'il n'existe pas de
transformation satisfaisant TP1 et TP2 dans ce cadre. Le deuxième résultat
consiste à étendre la structure de données par des informations fournies
naturellement par le processus d'édition qui garantissent l'unicité des
étiquettes et de montrer que les propriétés TP1 et TP2 sont satisfaites ce
qui autorise l'edition collaborative sur cette structure. Finalement, nous
montrons comment garder ces propriétés en ajoutant une opération de
déplacement de sous-arbres à condition de modifier la structure de donnée en
ajoutant une mémoire. Nous terminerons en discutant le cas des arbres
ordonnés et le problème du undo (annulation d'une opération).
Travail en commun avec Stéphane Martin.
|
Lieu | Salle 076, LaBRI, Rez-de-chaussée |
Orateur | Denis Lugiez |
Email | denis.lugiez@lif.univ-mrs.fr |
Url | LIFM, Marseille |
Aucun document lié à cet événement. RetourRetour à l'index
| |