Soutenance de thèse de Nicolas Hidalgo

Bonjour,

J'ai le grand plaisir de vous inviter à la soutenance de ma thèse
intitulée "Towards an Efficient Support for Complex Queries on
Structured Peer-to-Peer Networks" ainsi qu'au pot qui suivra.

Cette soutenance aura lieu au Laboratoire d'Informatique de Paris 6
(LIP6) à Jussieu (http://www.lip6.fr/informations/comment.php), salle
25/26-105 le 29 novembre 2011 à 16h00 en présence du jury suivant:

- Anne-Marie Kermarrec, Directrice de Recherche INRIA - Rapporteur
- Claudia Roncancio, Professeur Université de Grenoble - Rapporteur
- Peter Druschel, Scientific Director Max Planck Institute for
Software Systems - Examinateur
- Franck Petit, Professeur Université Pierre et Marie Curie - Examinateur
- Xavier Bonnaire, Professeur Associé Universidad Tecnica Federico
Santa Maria - co-directeur de thèse
- Pierre Sens, Professeur Université Pierre et Marie Curie - Directeur
de Thèse
- Luciana Arantes, Maitre de Conference Université Pierre et Marie
Curie - co-directeur de thèse

ABSTRACT:
Distributed Hash Tables (DHTs) provide the substrate to build
scalable, structured, and efficient Peer-to-Peer (P2P) networks which
are distributed systems with the potential to handle massive amounts
of data on a very large scale. Due to the hashing assignment of object
keys to peers and its lookup operation, exact match queries present
very good performance on DHT-based P2P systems. Although, traditional
DHTs cannot provide an effective support for complex queries, such as
range queries. In this work, we are particularly interested in those
solutions based on prefix tree indexes since they provide a portable
and scalable approach for satisfying complex queries over DHTs.
Nevertheless, the search methods proposed by such solutions usually
generate both high latencies and unnecessary message traffic overhead
which degrade system performance. Furthermore, some of them present
load balancing problems and do not tolerate P2P churn.

In this thesis we have proposed two solutions: PORQUE and ECHO. The
former is oriented to support low-latency searches while the latter is
oriented to support low-overhead searches. Performance evaluation
results of experiments confirm that both PORQUE and ECHO can reduce
latency and message traffic of searches by more than 50 \% when
compared to PHT. Our solutions also offer load balancing minimising
as much as possible bottlenecks over the index structure. By
exploiting different datasets distributions, performance results show
that our solutions perform independently of data skewness. Moreover,
performance of PORQUE and ECHO do not degrade in dynamic environments.

Résumé:
Les Tables de Hachage Distribuées (Distributed Hash Tables, ou DHT, en
anglais) permettent la construction de réseaux pair-à-pair structurés
pour des services de stockage persistant, hautement disponibles, et
passant à l'échelle. Les fonctions de hachage utilisées pour générer
les clés assurent une bonne répartition des objets sur les pairs du
réseau et permettent la localisation très efficace d'un objet à partir
de sa clé. Cependant, les DHTs sont peu efficaces pour gérer des
requêtes complexes telles que les requêtes par intervalle. Pour
pallier cela, plusieurs solutions ont été proposées dans la
littérature. Dans cette thèse, nous nous intéressons plus
particulièrement aux solutions reposant sur des arbres préfixes (trie
en anglais) construit au-dessus des DHTs car ces arbres fournissent
une solution portable et passant à l'échelle pour réaliser des
requêtes complexes. Cependant, les méthodes de recherche proposées par
les arbres préfixes distribués ont généralement une latence importante
et génèrent un nombre de messages élevés qui dégradent les
performances du système global. De plus, certaines des solutions
proposées équilibrent mal la charge des noeuds et sont
particulièrement inefficaces en cas d'arrivées et de départs massifs
de noeuds (churn en anglais).

Cette thèse vise donc à fournir de nouveaux supports pour les arbres
préfixes au-dessus de DHT permettant de faire des requêtes complexes
performantes. Nos approches assurent un bon un équilibrage de charge
des noeuds stockant les index et offrent un surcoût limité en messages
combiné à une latence faible. De plus, elles supportent mieux la
dynamique du réseau pair-à-pair par rapport aux approches classiques.
Nous avons étendu l'arbre préfixe PHT en proposant deux solutions:
PORQUE et ECHO. PORQUE vise à réduire la latence tandis qu'ECHO
fournit des recherches avec un faible surcoût. Nous avons implémenté
et évalué ses deux solutions au-dessus du simulateur PeerSim. Les
résultats des expérimentations confirment que PORQUE et ECHO peuvent
réduire la latence et le trafic réseau de plus de 50% par rapport à
PHT. Nos solutions équilibrent aussi la charge en évitant les goulets
d'étranglement dans les noeuds stockant les niveaux supérieurs de
l'arbre. Nous avons réalisé nos évaluations sur plusieurs ensembles de
données (réels et synthétiques) ayant des répartitions de clés
différentes. Les résultats montrent que nos solutions sont peu
sensibles à l'asymétrie dans la distribution des clés tout en ayant
une bonne résistance à la dynamique du réseau.

Cordialement,
Nicolas HIDALGO
Laboratoire LIP6, équipe-projet REGAL