Les systèmes d'édition collaborative permettent à plusieurs utilisateurs d'éditer simultanément un document. Aujourd'hui, l'édition collaborative massive est une réalité. Il ne s'agit plus d'éditer à quelques utilisateurs mais à des milliers d'utilisateurs répartis dans le monde. Les éditeurs collaboratifs actuels n'ont pas été conçus pour supporter un nombre si important d'utilisateurs. Les problèmes soulevés ne sont pas d'ordre technologique, ils remettent en cause les fondements algorithmiques des éditeurs. L'objectif de cette thèse est de proposer des algorithmes adaptés à l'édition collaborative massive. Nous montrons qu'un tel algorithme doit assurer trois critères : convergence des données, préservation des intentions et passage à l'échelle. Au regard de l'état de l'art, seul le modèle des transformées opérationnelles (OT) peut concilier ces trois critères.<br />La première contribution de cette thèse montre que l'approche OT conçue pour des éditeurs temps réel peut être utilisée pour réaliser des outils asynchrones. Nous avons réalisé un gestionnaire de configurations dénommé SO6. La seconde contribution est une approche formelle à la conception et à la vérification de fonctions de transformation pour le modèle OT. Cette approche repose sur un démonstrateur automatique de théorème. Avec cette approche, nous montrons que toutes les fonctions de transformation proposées jusqu'ici sont fausses. La troisième et dernière contribution de ce travail est un nouvel algorithme de réplication optimiste (WOOT) adapté à l'édition collaborative massive de structures linéaires. Ce modèle repose sur le calcul monotone d'une extension linéaire des ordres partiels formés par les relations entre les différents éléments de la structure.

Les outils d'édition collaborative permettent à un groupe de personnes distribuées dans le temps, dans l'espace et à travers les organisations, de travailler ensemble sur les mêmes documents. Un système d'édition collaborative efficace doit permettre à n'importe qui de modifier n'importe quel type de données à n'importe quel moment. Cela pose des problèmes de maintient de la cohérence des données au sein des ces systèmes. Nous présentons trois approches de maintient de la cohérence dans les systèmes collaboratifs distribués: une approche transactionnelle, une approche basée sur les transformées opérationnelles et une approche basée sur les types commutatifs répliqués.

Les éditeurs collaboratifs permettent à des utilisateurs éloignés de collaborer à une tâche commune qui va de l'utilisation d'un agenda partagé à la réalisation de logiciels. Ce concept est né avec SCCS en 1972 et connait un engouement récent (ex: Wikipedia). L'absence de centralisation et l'asynchronisme sont des aspects essentiels de cette approche qui relève d'un modèle pair-à-pair (P2P). D'un autre côté, le format XML est devenu une référence pour la manipulation et l'échange de documents. Notre travail vise à la réalisation d'un éditeur collaboratif P2P pour l'édition de documents semi-structurés qui sont une abstraction du format XML. Le problème est difficile et de nombreuses propositions se sont révélées erronées ou ne passant pas à l'échelle. Nous rappelons les concepts et l'état de l'art sur l'édition collaborative, les modèles centralisés et le P2P. Ensuite, nous explorons deux approches différentes : les transformées opérationnelles et le CRDT (Commutative Replicated Data Type) avec différentes structures de données arborescentes. L'objectif est de réaliser les opérations de base (ajout, suppression et ré-étiquetage) tout en garantissant la convergence du processus d'édition. Nous proposons un algorithme générique pour l'approche CRDT basée sur une notion d'indépendance dans la structure de données. Nous avons étendu nos travaux afin de réaliser l'opération de déplacement d'un sous-arbre et de prendre en compte le typage XML. Peu de travaux abordent ces deux points qui sont très utiles pour l'édition de documents. Finalement, nous donnons les résultats expérimentaux obtenus avec un prototype permettant de valider notre approche.

Les éditeurs collaboratifs permettent à des utilisateurs éloignés de collaborer à une tâche commune qui va de l'utilisation d'un agenda partagé à la réalisation de logiciels. Ce concept est né avec SCCS en1972 et connait un engouement récent (ex: Wikipedia). L'absence de centralisation et l'asynchronisme sont des aspects essentiels de cette approche qui relève d'un modèle pair-à-pair (P2P).  D'un autre côté,le format XML est devenu une référence pour la manipulation et l'échange de documents. Notre travail vise à la réalisation d'un éditeur collaboratif P2P pour l'édition de documents semi-structurés qui sont une abstraction du format XML.  Le problème est difficile et de nombreuses propositions se sont révélées erronées ou ne passant pas à l'échelle. Nous rappelons les concepts et l'état de l'art sur l'édition collaborative, les modèles centralisés et le P2P.  Ensuite, nous explorons deux approches différentes : les transformées opérationnelles et le CRDT (Commutative Replicated Data Type) avec différentes structures de données arborescentes. L'objectif est de réaliser les opérations de base (ajout, suppression et ré-étiquetage) tout en garantissant la convergence du processus d'édition. Nous proposons un algorithme générique pour l'approche CRDT basée sur une notion d'indépendance dans la structure de données.  Nous avons étendu nos travaux afin de réaliser l'opération de déplacement d'un sous-arbre et de prendre en compte le typage XML. Peu de travaux abordent ces deux points qui sont très utiles pour l'édition de documents. Finalement, nous donnons les résultats expérimentaux obtenus avec un prototype permettant de valider notre approche. / Collaborative editors allow different users to work together on a common task. Such tasks range from using a shared calendar to realizing software programmed by users located at distant sites. This concept was invented in 1972 with SCCS. In the last years, this paradigm became popular (ex. Wikipedia). Decentralization and asynchronicity are essential in this approach, leading to peer-to-peer (P2P) models. Meanwhile, the XML format has arrived as the de facto standard for editing and exchanging documents. Our work aims at defining a collaborative editor for semi-structured documents, which provide an abstraction of the XML format. The problem is difficult since many previous approaches are flawed or not scalable. Firstly,we describe the basic concepts on collaborative edition and network models and we give the state of the art of this topic. Then, we investigate two different approaches : the operational transformation(OT) approach and the Commutative Replicated Data Type (CRDT) approach for different (tree-like) data structures. Our goal is to ensure the convergence of the editing process with the basic operations (Add, Deland rename a node. We have proposed a new generic algorithm based on semantic independence in data structure for CRDT approach. We have extended our results by dealing with the operation that moves a subtree and with XML schema compliance. Few works have been devoted to these extensions which are useful in collaborative edition. Finally, we provide experimental results obtained from our implementation that validate our approach.