La société de l'information demande un accès efficace à un ensemble d'informations qui sont souvent hétérogènes et distribuées. Dans le but d'un partage efficace de cette information, plusieurs solutions techniques ont été proposées. L'infrastructure Pair-à-Pair (P2P) est un paradigme émergent et offrant de nouvelles opportunités pour la mise en place de systèmes distribués à grande échelle. D'autre part, le concept de base de données distribuée a été introduit dans le but d'organiser une collection multiple de bases de données logiquement liées et distribuées sur un réseau d'ordinateurs. Récemment, les systèmes P2P de gestion de données communément appelés PDMS (Peer Data Management System) ont vu le jour. Ils combinent les avantages des systèmes P2P avec ceux des bases de données distribuées. Dans le but de contribuer à la recherche sur la gestion de données dans un contexte P2P, nous proposons le PDMS SenPeer. SenPeer suit une topologie super-pair basée sur l'organisation des pairs en communautés sémantiques en fonction de leur thème d'intérêt. Pour faciliter l'échange de données entre pairs nous établissons des processus de découverte de correspondances sémantiques et de reformulation de requêtes en présence de plusieurs modèles de données. Ces correspondances sémantiques, en combinaison avec les schémas des pairs sont à la base d'une topologie sémantique au dessus du réseau physique et utilisée pour un routage efficace des requêtes. Les requêtes sont échangées à travers un format commun d'échange de requête et un processus d'optimisation distribué permet de choisir le meilleur plan d'exécution de la requête en fonction des caractéristiques du PDMS. Une validation expérimentale par la mise en place d'un simulateur permet d'affirmer l'utilité et la performance des techniques proposées.

Le but de cette thèse est de contribuer au développement des techniques de localisation et de description de données dans des environnements P2P. Au niveau de la couche application, nous nous concentrons sur l'exploitatoin des sémantiques qui peuvent être capturées à partir des données partagées. Ces sémantiques peuvent améliorer l'efficacité de recherche, ainsi que permettre des requêtes complexes. A cet effet, nous présentons une technique originale d'indexation de données dans les systèmes P2P qui se base sur les résumés linguistiques. Nos résumés sont des vues synthétiques et multidimensionnelles qui supportent la localisation des données pertinentes en se basant sur leur contenu. Plus intéressant, ils fournissent des représentations intelligibles de données, qui peuvent renvoyer des réponses approximatives à des requêtes d'utilisateur. Au niveau de la couche réseau P2P, nous nous concentrons sur l'exploitation des caractéristiques de la topologie, à savoir les caractéristiques de leur regroupement (clustering). Des informations sur le clustering du réseau P2P peuvent être utilisées pour réduire le trafic de réseau produit par le mécanisme de flooding. Ceci permet d'améliorer l'exécution des systèmes P2P, indépendamment de l'emploi des index de données à la couche application, puisque le mécanisme de flooding représente toujours un bloc constitutif fondamental des systèmes non structurés P2P. Dans cette thèse, nous présentons un bref état de l'art sur les systèmes P2P de partage de données P2P et nous nous concentrons sur l'évolution des systèmes simples de partages des fichiers vers des systèmes de gestion des données. En second lieu, nous proposons une solution pour la gestion des résumés de données dans des systèmes P2P. Nous définissons un modèle approprié et des techniques efficaces pour la création et la mise à jour des résumés. Nous discutons également le traitement des requêtes dans le cadre des résumés. Troisième- ment, nous proposons une technique de recherche basée sur clustering implémentée au dessus d'un protocole de custering selon la connectivité des noeuds. Nous nous concentrons sur la reduction des messages de re- quêtes redondants qui surchargent inutilement le système. Nous avons validé nos solutions par la simulation et les résultats montrent une bonne performance.

De nombreuses applications distribuées partagent la même nécessité de traiter des flux de données de façon continue, par ex. la surveillance de réseau ou la gestion de réseaux de capteurs. Dans ce contexte, un problème important et difficile concerne le traitement de requêtes continues de jointure qui nécessite de maintenir une fenêtre glissante sur les données la plus grande possible, afin de produire le plus possible de résultats probants. Dans cette thèse, nous proposons une nouvelle méthode pair-à-pair, DHTJoin, qui tire parti d'une Table de Hachage Distribuée (DHT) pour augmenter la taille de la fenêtre glissante en partitionnant les flux sur un grand nombre de nœuds. Contrairement aux solutions concurrentes qui indexent tout les tuples des flux, DHTJoin n'indexe que les tuples requis pour les requêtes et exploite, de façon complémentaire, la dissémination de requêtes. DHTJoin traite aussi le problème de la dynamicité des nœuds, qui peuvent quitter le système ou tomber en panne pendant l'exécution. Notre évaluation de performances montre que DHTJoin apporte une réduction importante du trafic réseau, par rapport aux méthodes concurrentes.

Cette thèse étudie la découverte de services (composants logiciels, exécutables, librairies scientifiques) sur des plates-formes distribuées à grande échelle. Les approches traditionnelles, proposées pour des environnements stables et relativement petits, s'appuient sur des techniques centralisées impropres au passage à l'échelle dans des environnements géographiquement distribués et instables. Notre contribution s'articule autour de trois axes. 1) Nous proposons une nouvelle approche appelée DLPT (Distributed Lexicographic Placement Table), qui s'inspire des systèmes pair-à-pair et s'appuie sur un réseau de recouvrement structuré en arbre de préfixes. Cette structure permet des recherches multi-attributs sur des plages de valeurs. 2) Nous étudions la distribution des noeuds de l'arbre sur les processeurs de la plate-forme sous-jacente, distribuée, dynamique et hétérogène. Nous proposons et adaptons des heuristiques de répartition de la charge pour ce type d'architectures. 3) Notre plate-forme cible, par nature instable, nécessite des mécanismes robustes pour la tolérance aux pannes. La réplication traditionnellement utilisée s'y avère coûteuse et incapable de gérer des fautes transitoires. Nous proposons des techniques de tolérance aux pannes best-effort fondées sur la théorie de l'auto-stabilisation pour la construction d'arbres de préfixes dans des environnements pair-à-pair. Nous présentons deux approches. La première, écrite dans un modèle théorique à gros grain, permet de maintenir des arbres de préfixes instantanément stabilisants, c'est-à-dire reconstruits en un temps optimal après un nombre arbitraire de fautes. La deuxième, écrite dans le modèle à passage de messages, permet l'implantation d'une telle architecture dans des réseaux très dynamiques. Enfin, nous présentons un prototype logiciel mettant en oeuvre cette architecture et présentons ses premières expérimentations sur la plate-forme Grid'5000.

Le sujet de ma thèse consiste à analyser la sécurité d'un système de stockage pair à pair. Durant la première phase j'ai commencé par me familiariser avec le système existant (que du code), par la suite j'ai analysé la résistance du système en la présence d'attaques internes (que j'ai implémenté) en utilisant la simulation (travaux publiés dans HPCS'11). Le simulateur utilisé est un simulateur propriétaire qui reprend le code initial du système et modulable. Les résultats de cette analyse (perte de données) m'ont conduit à mettre en place un mécanisme de détection pour détecter ces attaques avant qu'elles ne causent la perte des données. Ce mécanisme de détection consiste à mettre en place un système de notation à deux niveaux : niveau 1:notation des échanges entre pair, niveau 2: notation des notes accordées à chaque pair (confiance en ces notes). Le principe de ce système est basé sur l'historique des échanges et la diffusion des notes entre les pairs. Dans un premier temps un système de notation à un niveau à été modélisé, implémenté et son efficacité analysée en utilisant deux méthodes (simulation pour les résultats quantitatifs et le model-checking pour les résultats qualitatifs. Pour la partie modélisation et vérification j'ai utilisé le formalisme ABCD [1], et les compilateurs SNAKES[2] et NICO[3,4]. Les résultats ont montrés la limite de ce système de notation à un seul niveau. (Travaux publiés dans TMS'12). A noter que jusque là seulement quelques attaques ont été détectées. En parallèle de tout ça un travail de modélisation dans un contexte de génie logiciel à été fait. Modélisation de l'application (Java) en utilisant le formalisme ABCD.

Les méthodes d'apprentissage semi-supervisé constituent une catégorie de méthodes d'apprentissage automatique qui combinent points étiquetés et données non labellisées pour construire le classifieur. Dans la première partie de la thèse, nous proposons un formalisme d'optimisation général, commun à l'ensemble des méthodes d'apprentissage semi-supervisé et en particulier aux Laplacien Standard, Laplacien Normalisé et PageRank. En utilisant la théorie des marches aléatoires, nous caractérisons les différences majeures entre méthodes d'apprentissage semi-supervisé et nous définissons des critères opérationnels pour guider le choix des paramètres du noyau ainsi que des points étiquetés. Nous illustrons la portée des résultats théoriques obtenus sur des données synthétiques et réelles, comme par exemple la classification par le contenu et par utilisateurs des systèmes pair-à-pair. Cette application montre de façon édifiante que la famille de méthodes proposée passe parfaitement à l’échelle. Les algorithmes développés dans la deuxième partie de la thèse peuvent être appliquées pour la sélection des données étiquetées, mais également aux autres applications dans la recherche d'information. Plus précisément, nous proposons des algorithmes randomisés pour la détection rapide des nœuds de grands degrés et des nœuds avec de grandes valeurs de PageRank personnalisé. A la fin de la thèse, nous proposons une nouvelle mesure de centralité, qui généralise à la fois la centralité d'intermédiarité et PageRank. Cette nouvelle mesure est particulièrement bien adaptée pour la détection de la vulnérabilité de réseau. / Semi-supervised learning methods constitute a category of machine learning methods which use labelled points together with unlabeled data to tune the classifier. The main idea of the semi-supervised methods is based on an assumption that the classification function should change smoothly over a similarity graph. In the first part of the thesis, we propose a generalized optimization approach for the graph-based semi-supervised learning which implies as particular cases the Standard Laplacian, Normalized Laplacian and PageRank based methods. Using random walk theory, we provide insights about the differences among the graph-based semi-supervised learning methods and give recommendations for the choice of the kernel parameters and labelled points. We have illustrated all theoretical results with the help of synthetic and real data. As one example of real data we consider classification of content and users in P2P systems. This application demonstrates that the proposed family of methods scales very well with the volume of data. The second part of the thesis is devoted to quick detection of network central nodes. The algorithms developed in the second part of the thesis can be applied for the selections of quality labelled data but also have other applications in information retrieval. Specifically, we propose random walk based algorithms for quick detection of large degree nodes and nodes with large values of Personalized PageRank. Finally, in the end of the thesis we suggest new centrality measure, which generalizes both the current flow betweenness centrality and PageRank. This new measure is particularly well suited for detection of network vulnerability.

Les systèmes pair-à-pair (P2P) sont aujourd'hui très populaires. Leur utilisation va de la messagerie instantanée au partage de fichiers, en passant par la sauvegarde et le stockage distribué ou encore le streaming video. Parmi les protocoles P2P, les protocoles basés sur le "gossip" sont une famille de protocoles qui a fait l'objet de nombreux travaux de recherche durant la dernière décennie. Les raisons de l'engouement pour les protocoles basés sur le "gossip" sont qu'ils sont considérés robustes, faciles à mettre en oeuvre et qu'ils ont des propriétés de passage à l'échelle intéressantes. Ce sont donc des candidats intéressants dès lors qu'il s'agit de réaliser des systèmes distribués dynamiques à large échelle. Cette thèse considère deux problématiques rencontrées lorsque l'on déploie des protocoles basé sur le "gossip" dans un environnement réel comme l'Internet. La première problématique est la prise en compte des pare-feux (NAT) dans le cadre des protocoles d'échantillonnage basés sur le "gossip". Ces protocoles font l'hypothèse que, a tout moment, chaque noeud est capable de communiquer avec n'importe quel noeud du réseau. Cette hypothèse est fausse dès lors que certains noeuds utilisent des NAT. Nous présentons Nylon, un protocole d'échantillonnage qui fonctionne malgré la présence de NAT. Nylon introduit un faible surcoût pour gérer les NAT et partage équitablement ce surcoût entre les noeuds possédant un NAT et les autres noeuds. La deuxième problématique que nous étudions est la possibilité de limiter la dissémination de messages de type "spam" dans les protocoles de dissémination basés sur le "gossip". Ces protocoles sont en effet des vecteurs idéaux pour diffuser les messages de type "spam" du fait qu'il n'y a pas d'autorité de contrôle permettant de filtrer les messages basés sur leur contenu. Nous proposons FireSpam, un protocole de dissémination basé sur le "gossip" qui permet de limiter la diffusion des messages de type "spam". FireSpam fonctionne par filtrage décentralisé (chaque noeud participe au filtrage). Par ailleurs, il fonctionne malgré la présence d'une fraction de noeuds malicieux (aussi appelés "Byzantins") et malgré la présence de noeuds dits "rationnels" (aussi appelés "égoïstes"). Ces derniers sont prêts à dévier du protocole s'ils ont un intérêt à le faire.

Cette thèse évalue les performances de systèmes de stockage de données sur des réseaux de pairs. Ces systèmes reposent sur trois piliers: la fragmentation des données et leur dissémination chez les pairs, la redondance des données afin de faire face aux éventuelles indisponibilités des pairs et l'existence d'un mécanisme de recouvrement des données perdues ou temporairement indisponibles. Nous modélisons deux mécanismes de recouvrement des données par des chaînes de Markov absorbantes. Plus précisément, nous évaluons la qualité du service rendu aux utilisateurs en terme de longévité et de disponibilité des données de chaque mécanisme. Le premier mécanisme est centralisé et repose sur l'utilisation d'un serveur pour la reconstruction des donnée perdus. Le second est distribué : la reconstruction des fragments perdus met en oeuvre, séquentiellement, plusieurs pairs et s'arrête dès que le niveau de redondance requis est atteint. Les principales hypothèses faites dans nos modèles sont validées soit par des simulations soit par des traces réelles recueillies dans différents environnements distribués. Pour les processus de téléchargement et de recouvrement des données nous proposons un modèle de simulation réaliste qui est capable de prédire avec précision le comportement de ces processus mais le temps de simulation est long pour de grands réseaux. Pour surmonter cette restriction nous proposons et analysons un algorithme efficace au niveau flux. L'algorithme est simple et utilise le concept de (min-max). Il permet de caractériser le temps de réponse des téléchargements en parallèle dans un système de stockage distribué.

Nous nous intéressons aux systèmes distribués d'information ouverts, mettant en oeuvre un grand nombre de sources d'informations autonomes et hétérogènes, tels que les systèmes pairs à pairs. Dans un tel contexte, un pair peut jouer à la fois le rôle d'initiateur de requêtes et celui de fournisseur d'informations. Le rôle du médiateur consiste à faire le lien entre initiateurs et fournisseurs, en allouant les requêtes qui lui sont confiées aux fournisseurs qui lui paraissent les plus pertinents. Les attentes des initiateurs et celles des fournisseurs peuvent être antagonistes : les premiers préférant des réponses pertinentes, les seconds privilégiant de traiter certains types de requêtes. Souvent, les médiateurs permettent de prendre en compte qu'un seul des deux points de vue. Cette thèse propose un mécanisme de médiation flexible qui permet de considérer les deux points de vue en même temps, de façon à assurer la satisfaction de tous les acteurs du système. D'un côté, les fournisseurs font des offres monétaires représentant leur intérêt pour la requête. De l'autre, les préférences des initiateurs pour les fournisseurs sont prises en compte au travers de la notion de qualité. Ces deux critères sont la base de la phase de sélection des fournisseurs de notre médiation. De plus, la médiation flexible propose la réquisition de fournisseurs lorsqu'ils ne veulent pas traiter une requête. Nous étudions notre médiation d'un point de vue théorique tout d'abord, en considérant des propriétés usuelles de microéconomie et en proposant une nouvelle définition pour prendre en compte la satisfaction à long terme des participants (initiateurs et fournisseurs). L'étude théorique est complétée par un ensemble de simulations dans différents contextes qui permettent de la comparer à d'autres mécanismes d'allocation de requêtes. Les résultats montrent que la médiation flexible assure généralement la satisfaction sur le long terme des participants et permettent de déterminer les conditions dans lesquelles il est préférable de l'utiliser.

La mise en réseau des dispositifs de gestion de l'information, qu'ils soient de petite taille (capteur - dispositif) ou de grande taille (cluster -super calcu- lateur) accompagnent et accélèrent l'émergence d'une informatique ubiquitaire. Ce mouvement de fond entraîne une explosion, tant de la quantité que de la diversité de l'information disponible. Le sens même de ces informations est souvent ignoré par les traitements opérés dans les couches basses des systèmes qui gèrent ces informations. Dans un contexte où les sources d'information deviennent surabondantes, l'exé- cution de l'opération la plus élémentaire, portant sur la plus élémentaire des in- formations, passe par la maîtrise du sens associé aux données manipulées. Une des évolutions majeures à venir est donc, l'intégration, au cœur des systèmes, du sens associé à l'information et aux processus de traitement. Les domaines plus particulièrement développés sont la recherche de sens dans les textes et la gestion de données dans les systèmes ubiquitaires à grande échelle. Ces recherches ont été conduites au sein de la communauté IMAG et se poursuivent aujourd'hui dans l'équipe SIGMA - laboratoire LIG et de l'Université Joseph Fourier.