Récemment, les wikis sont devenus les outils d'édition collaborative les plus populaires. Ils doivent maintenant faire face à une forte augmentation en quantité et complexité des données gérées en nombre d'utilisateurs. Pour répondre à ce problème, le passage d'une architecture client/serveur vers une architecture décentralisée sur réseau pair-à-pair est une voie possible. Elle pose cependant des problèmes liés à la concurrence des mises à jour sur des sites distants. Ce document décrit deux contributions à cette problématique. La première contribution propose un mécanisme totalement décentralisé pour la conscience de la concurrence dans une édition collaborative sur réseaux P2P. Son rôle est de permettre aux visiteurs d'un wiki d'avoir conscience du statut d'une page vis-à-vis de la concurrence - s'agit-il d'une page éditée ou fusionnée ? - et dans le cas d'une page fusionnée, d'avoir une vision des zones de la page touchées par la fusion. Ce mécanisme repose sur un détecteur de concurrence dont le principe consiste à étiqueter les patchs échangés entre les serveurs. La deuxième contribution porte sur la visualisation d'un historique concurrent. La visualisation proposée se base sur la visualisation linéaire classique: chaque site affiche la séquence locale de versions dans l'ordre où elles sont apparues, et complète cet historique avec des informations permettant de repérer les états édités et fusionnés et les parties concurrentes dans l'histoire. / Currently, Wikis are the most popular form of collaborative editors. They allow users to concurrently edit and modify a shared set of wiki pages. We anticipate large increasing of amount and complexity of data. To face this problem, some researches have been done to shift from centralized architecture to fully decentralized wikis relying on peer-to-peer networks. However, this approach leads to new problem related to concurrency and the way remote modifications are integrated at each site. To overcome this problem, this thesis introduces the idea of concurrency awareness and proposes two contributions. The first one is to build a concurrency awareness mechanism for a P2P wiki. This mechanism makes users aware of the status of the pages they access regarding concurrency: is it an edited page or a merged page? In addition, in case of merged page, it indicates which region of the page has been merged. This mechanism depends over a concurrency detection mechanism which labels the generated patches by the set of servers. The second contribution deals with the representation of the concurrent history. Our visualisation is based over the classical history visualisation: the local versions are presented at the same order of their creation, and we added the information that present the status of these versions according to the concurrence.

L'édition collaborative en temps réel permet à plusieurs utilisateurs d'éditer un même document simultanément grâce à des outils informatiques. Les applications d'édition collaborative en temps réel répliquent les données éditées chez chaque utilisateur, pour garantir une édition des données réactive et possible à chaque instant. Les conflits d'édition sont fréquents, et doivent être gérés automatiquement par l'application. L'application doit faire converger toutes les répliques vers un document commun, qui contient toutes les modifications exprimées par tous les utilisateurs. Les algorithmes actuels fonctionnent de manière satisfaisante pour des types de données simples et des possibilités d'édition minimes. Lorsque le document est plus complexe (document XML, texte structuré), ou qu'il peut être édité avec un ensemble élargi d'opérations (déplacement de texte, styliser du texte), lors de la résolution de conflits d'édition, les algorithmes échouent à proposer un contenu qui convienne aux utilisateurs. Les intentions des utilisateurs ne sont pas respectées. L'objectif de cette thèse est de proposer des algorithmes d'édition collaborative en temps réel qui respectent mieux les intentions des utilisateurs que les algorithmes actuels.Pour cela, nous étudions deux approches de la littérature nommées transformées opérationnelles et modèles de données répliquées commutatives, et montrons comment il est possible d'attribuer plus de sémantique aux opérations de base des algorithmes d'édition collaborative, ce qui permet aux utilisateurs d'exprimer avec plus de moyens leurs intentions, et aux algorithmes de résoudre plus efficacement les conflits d'édition / Real-time collaborative editors, like GoogleDocs or Etherpad, allow the simultaneous edition of a document by several users. These applications need to replicate the edited document, for the so called real-time purpose of permitting a fast and reactive editing by any user at any time. Editing conflicts frequently occur, and must be automatically handled by the application, in order to provide every users with the same copy of the document, containing every modifications issued. Most of current real-time collaborative editing algorithms were designed for simple data structures, like linear text, and simple editing ways, like inserting or removing a character only. These algorithms fail to offer an appropriate editing conflict resolution when used with a complex data structure, like XML, or with complex operations, like moving some text or adding some style. Copies are the sames but users' intentions are not preserved. The goal of this thesis is to design new real-time collaborative editing algorithms that ensure a better preservation of users' intentions. The first contribution of this thesis is an algorithm based on the Operational Transformation approach (OT). Our contribution is designed to handle rich text document (with stylized text and paragraphs) and to preserve the intentions of a set of high editing level operations (add style, merge paragraphs...). The second contribution uses the Commutative Replicated Data Types approach (CRDT), and offers an algorithm which preserves the update intention, while improving global performance of the approach when dealing with large blocs of data

Récemment, les wikis sont devenus les outils d'édition collaborative les plus populaires. Ils doivent maintenant faire face à une forte augmentation en quantité et complexité des données gérées en nombre d'utilisateurs. Pour répondre à ce problème, le passage d'une architecture client/serveur vers une architecture décentralisée sur réseau pair-à-pair est une voie possible. Elle pose cependant des problèmes liés à la concurrence des mises à jour sur des sites distants. Ce document décrit deux contributions à cette problématique. La première contribution propose un mécanisme totalement décentralisé pour la conscience de la concurrence dans une édition collaborative sur réseaux P2P. Son rôle est de permettre aux visiteurs d'un wiki d'avoir conscience du statut d'une page vis-à-vis de la concurrence - s'agit-il d'une page éditée ou fusionnée ? - et dans le cas d'une page fusionnée, d'avoir une vision des zones de la page touchées par la fusion. Ce mécanisme repose sur un détecteur de concurrence dont le principe consiste à étiqueter les patchs échangés entre les serveurs. La deuxième contribution porte sur la visualisation d'un historique concurrent. La visualisation proposée se base sur la visualisation linéaire classique: chaque site affiche la séquence locale de versions dans l'ordre où elles sont apparues, et complète cet historique avec des informations permettant de repérer les états édités et fusionnés et les parties concurrentes dans l'histoire.

Dans cette thèse, nous abordons deux problèmes soulevés par les systèmes distribués décentralisés - le placement de réseaux logiques de façon compatible avec le réseau physique sous-jacent et la construction de cohortes d'éditeurs pour dans les systèmes d'édition collaborative. Bien que les réseaux logiques (overlay networks) été largement étudiés, la plupart des systèmes existant ne prennent pas ou prennent mal en compte la topologie du réseau physique sous-jacent, alors que la performance de ces systèmes dépend dans une grande mesure de la manière dont leur topologie logique exploite la localité présente dans le réseau physique sur lequel ils s'exécutent. Pour résoudre ce problème, nous proposons dans cette thèse Fluidify, un mécanisme décentralisé pour le déploiement d'un réseau logique sur une infrastructure physique qui cherche à maximiser la localité du déploiement. Fluidify utilise une stratégie double qui exploite à la fois les liaisons logiques d'un réseau applicatif et la topologie physique de son réseau sous-jacent pour aligner progressivement l'une avec l'autre. Le protocole résultant est générique, efficace, évolutif et peut améliorer considérablement les performances de l'ensemble. La deuxième question que nous abordons traite des plates-formes d'édition collaborative. Ces plates-formes permettent à plusieurs utilisateurs distants de contribuer simultanément au même document. Seuls un nombre limité d'utilisateurs simultanés peuvent être pris en charge par les éditeurs actuellement déployés. Un certain nombre de solutions pair-à-pair ont donc été proposées pour supprimer cette limitation et permettre à un grand nombre d'utilisateurs de collaborer sur un même document sans aucune coordination centrale. Ces plates-formes supposent cependant que tous les utilisateurs d'un système éditent le même jeu de document, ce qui est peu vraisemblable. Pour ouvrir la voie à des systèmes plus flexibles, nous présentons, Filament, un protocole décentralisé de construction de cohorte adapté aux besoins des grands éditeurs collaboratifs. Filament élimine la nécessité de toute table de hachage distribuée (DHT) intermédiaire et permet aux utilisateurs travaillant sur le même document de se retrouver d'une manière rapide, efficace et robuste en générant un champ de routage adaptatif autour d'eux-mêmes. L'architecture de Filament repose sur un ensemble de réseaux logiques auto-organisées qui exploitent les similarités entre jeux de documents édités par les utilisateurs. Le protocole résultant est efficace, évolutif et fournit des propriétés bénéfiques d'équilibrage de charge sur les pairs impliqués. / In this thesis, we address two issues in the area of decentralized distributed systems: network-aware overlays and collaborative editing. Even though network overlays have been extensively studied, most solutions either ignores the underlying physical network topology, or uses mechanisms that are specific to a given platform or applications. This is problematic, as the performance of an overlay network strongly depends on the way its logical topology exploits the underlying physical network. To address this problem, we propose Fluidify, a decentralized mechanism for deploying an overlay network on top of a physical infrastructure while maximizing network locality. Fluidify uses a dual strategy that exploits both the logical links of an overlay and the physical topology of its underlying network to progressively align one with the other. The resulting protocol is generic, efficient, scalable and can substantially improve network overheads and latency in overlay based systems. The second issue that we address focuses on collaborative editing platforms. Distributed collaborative editors allow several remote users to contribute concurrently to the same document. Only a limited number of concurrent users can be supported by the currently deployed editors. A number of peer-to-peer solutions have therefore been proposed to remove this limitation and allow a large number of users to work collaboratively. These decentralized solution assume however that all users are editing the same set of documents, which is unlikely to be the case. To open the path towards more flexible decentralized collaborative editors, we present Filament, a decentralized cohort-construction protocol adapted to the needs of large-scale collaborative editors. Filament eliminates the need for any intermediate DHT, and allows nodes editing the same document to find each other in a rapid, efficient and robust manner by generating an adaptive routing field around themselves. Filament's architecture hinges around a set of collaborating self-organizing overlays that utilizes the semantic relations between peers. The resulting protocol is efficient, scalable and provides beneficial load-balancing properties over the involved peers.

Ce travail de thèse a pour objectif de renforcer la protection de la vie privée dans l'édition collaborative de documents dématérialisés. Une première partie de notre travail a consisté en l'élaboration d'un modèle sécurisé d'éditeur collaboratif de documents. La confidentialité des documents est assurée grâce à un contrôle d'accès décentralisé. Une seconde partie a été de protéger l'identité des utilisateurs communicants en assurant leur anonymat lors de l'édition des documents. Notre concept d'éditeur collaboratif est fondé sur l'utilisation d'ensembles de modifications apportées à un document, que nous nommons deltas, lesquels définissent des versions du document. Les deltas permettent de conserver l'historique des modifications successives. Lorsqu'une nouvelle version d'un document apparait, seul le nouveau delta qui en découle doit être transmis et stocké : les documents sont ainsi distribués à travers un ensemble de sites de stockage. Cela permet, d'une part, d'alléger la charge du gestionnaire des versions des documents, et d'autre part, d'améliorer la sécurité générale. La récupération décentralisée d'une nouvelle version nécessite seulement celle des deltas manquants par rapport à une version précédente; elle est donc moins coûteuse que la récupération du document en entier. L'information du lien entre les deltas est enregistrée directement avec les deltas et non dans une table ou dans un objet de métadonnées ce qui améliore leur sécurité. La gestion des versions est faite afin de maintenir une cohérence entre les versions. / This thesis aims to strengthen the protection of privacy of authors in collaborative editing of electronic documents. The first part of our work consisted in the design a secured model for a collaborative document editor. Documents' confidentiality is ensured through a decentralized access control mechanism. A second part of the work was to protect the identity of communicating users by ensuring their anonymity during collaborative document editing. Our concept of collaborative editor is based on the use of sets of modifications for a document, which we call textit{deltas}. Thus, deltas define versions of the document and they can keep the history of subsequent modifications. When a new version of a document appears, only the new delta that results must be transmitted and stored : documents are thus distributed across a set of storage sites (servers). We show how this allows, first, to reduce the load of document version control system, and secondly, to improve overall security of the collaborative system. Decentralized recovery of a new version requires only recovery of appropriate deltas against a previous version and is therefore more efficient than recovering the entire document. The information of the link between deltas is stored directly with deltas and not in a table or a metadata object, that improves their security. The version control system maintains consistency between versions. Once a user has retrieved versions, she holds them in local, and the history can be accessed at any time without being necessary to connect to the central server. Deltas can be identified, indexed and maintained their integrity through the use of hash functions.