Evènement pour le groupe Modélisation et Verification


Date 2009-06-18  11:00-12:15
TitreEdition 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.  
LieuSalle 076, LaBRI, Rez-de-chaussée 
OrateurDenis Lugiez 
Emaildenis.lugiez@lif.univ-mrs.fr 
UrlLIFM, Marseille 



Aucun document lié à cet événement.

Retour
Retour à l'index