Cet ouvrage et des milliers d'autres font partie de la bibliothèque YouScribe
Obtenez un accès à la bibliothèque pour les lire en ligne
En savoir plus

Partagez cette publication




AVERTISSEMENT

Ce document est le fruit d'un long travail approuvé par le
jury de soutenance et mis à disposition de l'ensemble de la
communauté universitaire élargie.

Il est soumis à la propriété intellectuelle de l'auteur. Ceci
implique une obligation de citation et de référencement lors
de l’utilisation de ce document.

D’autre part, toute contrefaçon, plagiat, reproduction
illicite encourt une poursuite pénale.


➢ Contact SCD Nancy 1 : theses.sciences@scd.uhp-nancy.fr




LIENS


Code de la Propriété Intellectuelle. articles L 122. 4
Code de la Propriété Intellectuelle. articles L 335.2- L 335.10
http://www.cfcopies.com/V2/leg/leg_droi.php
http://www.culture.gouv.fr/culture/infos-pratiques/droits/protection.htm Departement de formation doctorale en informatique Ecole doctorale IAEM Lorraine
UFR STMIA
Edition collaborative massive sur
reseaux Pair-a-Pair
THESE
presentee et soutenue publiquement le 18 octobre 2010
pour l’obtention du
Doctorat de l’universite Henri Poincare { Nancy 1
(specialite informatique)
par
Stephane Weiss
Composition du jury
President : Olivier FESTOR Directeur de Recherche, INRIA Lorraine
Rapporteurs : Achour MOSTEFAOUI Ma^ tre de Conferences, Universite de Rennes
Marc SHAPIRO Directeur de Recherche, INRIA Rocquencourt
Examinateur : Esther PACITTI Professeur, Universite de Montpellier 2
Directeurs de These : Pascal MOLLI Professeur, Universite de Nantes
Pascal URSO Ma^ tre de Conferences, Universite de Lorraine
Laboratoire Lorrain de Recherche en Informatique et ses Applications | UMR 7503Mis en page avec la classe thloria.Remerciements
Je tiens tout particulierement a remercier l’ensemble du jury pour l’in-
ter^et porte a mes travaux.
Tout d’abord, je souhaite remercier les rapporteurs Achour Mostefaoui
et Marc Shapiro pour leur lecture attentive de mon manuscript et leurs
nombreux commentaires qui m’ont permis de l’ameliorer.
Je souhaite egalement remercier Esther Pacitti et Olivier Festor pour
leur r^ole d’examinateur. Je tiens, de plus, a remercier Olivier Festor pour
avoir accepte d’^etre president du jury.
Je tiens a remercier mes encadrants Pascal Urso et Pascal Molli pour
m’avoir guide tout au long de cette these.
A Pascal Urso, pour m’avoir enseigne les rudiments du formalisme qui
faisaient cruellement defaut a ma formation initiale. Je le remercie pour les
nombreuses et toujours passionnantes discussions que nous avons eu.
A Pascal Molli, pour m’avoir dirige lors de ma these. Je le remercie
pour sa vision eclairee du web, ses nombreux conseils et critiques qui m’ont
permis de progresser.
Je tiens aussi a remercier Claude Godart pour m’avoir permis de decou-
vrir le monde de la recherche et de l’enseignement.
Je ne pourrais pas nir sans remercier tous ceux qui m’ont accompagne
durant ces annees, je pense bien su^r aux membres de l’equipe SCORE et
tout particulierement a Gerald Oster, Claudia Ignat, Charbel Rahhal, Na-
wal Guermouche, Hien Truong mais aussi a Ioana Ilea, Guzman Llambias,
Victor Munteanu.
Finalement, je souhaite remercier ma famille qui, par son soutien et sa
presence, a contribue a cette these.
iiiTable des matieres
Introduction 1
Chapitre 1 Problematique 5
1.1 Les systemes collaboratifs . . . . . . . . . . . . . . . . . . . . . . . . . . . 6
1.2 Les systemes d’edition collaborative . . . . . . . . . . . . . . . . . . . . . . 7
1.2.1 Modele de systeme d’edition collaborative . . . . . . . . . . . . . . 8
1.2.2 Annulation dans les systemes d’edition collaborative . . . . . . . . . 13
1.2.3 Edition collaborative massive . . . . . . . . . . . . . . . . . . . . . 16
1.3 Conclusion . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 19
Chapitre 2 Etat de l’art 21
2.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 22
2.1.1 Le modele de coherence CCI . . . . . . . . . . . . . . . . . . . . . . 22
2.1.2 L’annulation de groupe . . . . . . . . . . . . . . . . . . . . . . . . . 25
2.2 Les approches . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 26
2.2.1 Usenet . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 26
2.2.2 Les approches veriant uniquement la causalite . . . . . . . . . . . 27
2.2.3 Le modele ACF . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 28
2.2.4 L’approche des transformees operationnelles . . . . . . . . . . . . . 30
2.2.5 Le modele type de donnees replique commutatif (CRDT) . . . . 35
2.3 Conclusion . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 39
Chapitre 3 Modele pour l’edition collaborative 41
3.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 42
3.2 Modele de systeme d’edition collaboratif . . . . . . . . . . . . . . . . . . . 42
3.2.1 Modele general . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 42
3.2.2 Modele pour l’edition collaborative de documents texte . . . . . . . 45
iii
Table des matieres
3.3 Modele de coherence . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 47
3.3.1 Respect de la causalite . . . . . . . . . . . . . . . . . . . . . . . . . 48
3.3.2 Convergence des repliques . . . . . . . . . . . . . . . . . . . . . . . 49
3.3.3 Preservation de l’intention . . . . . . . . . . . . . . . . . . . . . . . 51
Chapitre 4 Logoot 57
4.1 Logoot : un CRDT pour les documents texte . . . . . . . . . . . . . . . . . 58
4.1.1 Modele de donnees de Logoot . . . . . . . . . . . . . . . . . . . . . 58
4.1.2 Modication d’un document Logoot . . . . . . . . . . . . . . . . . . 60
4.1.3 Analyse en complexite moyenne . . . . . . . . . . . . . . . . . . . . 65
4.2 Correction et passage a l’echelle . . . . . . . . . . . . . . . . . . . . . . . . 66
4.2.1 Correction de l’approche . . . . . . . . . . . . . . . . . . . . . . . . 66
4.2.2 Passage a l’echelle . . . . . . . . . . . . . . . . . . . . . . . . . . . . 67
4.2.3 Conclusion . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 68
4.3 Experimentations . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 68
4.3.1 Methodologie . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 69
4.3.2 Validation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 72
4.3.3 Comparaison avec les approches existantes . . . . . . . . . . . . . . 74
4.3.4 Conclusions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 77
Chapitre 5 L’annulation dans les CRDTs 79
+5.1 CRDT : Un CRDT d’annulation . . . . . . . . . . . . . . . . . . . . . . . 80
5.1.1 Hypotheses sur le CRDT . . . . . . . . . . . . . . . . . . . . . . . . 81
+5.1.2 Modele du CRDT . . . . . . . . . . . . . . . . . . . . . . . . . . . 81
+5.1.3 La complexite temporelle du CRDT . . . . . . . . . . . . . . . . . 89
5.1.4 Optimisations pour les CRDTs sans dependance . . . . . . . . . . . 90
+5.2 Logoot . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 91
+5.2.1 Logoot et inversibilite . . . . . . . . . . . . . . . . . . . . . . . . . 91
+ +5.2.2 Logoot , un algorithme de type CRDT . . . . . . . . . . . . . . . 93
+5.2.3 Analyse en complexite moyenne de Logoot . . . . . . . . . . . . . 95
5.2.4 Conclusion . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 97
+5.3 Validation experimentale de Logoot . . . . . . . . . . . . . . . . . . . . . 97
5.3.1 Extension du corpus pour l’annulation . . . . . . . . . . . . . . . . 97
5.3.2 Validation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 98
5.3.3 Comparaison avec les approches existantes . . . . . . . . . . . . . . 99
iv

Un pour Un
Permettre à tous d'accéder à la lecture
Pour chaque accès à la bibliothèque, YouScribe donne un accès à une personne dans le besoin