Direction de recherche : Pierre SENS

Co-encadrement : SOPENA Julien

Algorithmes de dissémination épidémiques dans les réseaux à grande échelle : comparaison et adaptation aux topologie

La dissémination d'informations (broadcast) est essentielle pour de nombreuses applications réparties. Celle-ci doit être efficace, c'est à dire limiter la redondance des messages, et assurer forte fiabilité et faible latence. Nous considérons ici les algorithmes répartis profitant des propriétés des topologies sous-jacentes. Cependant, ces propriétés et les paramètres dans les algorithmes sont hétérogènes. Ainsi, nous devons trouver une manière pour les comparer équitablement. D'abord, nous étudions les protocoles probabilistes de dissémination d’informations (gossip) exécutées sur trois graphes aléatoires. Les trois graphes représentent les topologies typiques des réseaux à grande-échelle : le graphe de Bernoulli, le graphe géométrique aléatoire et le graphe scale-free. Afin de comparer équitablement leurs performances, nous proposons un nouveau paramètre générique : le fanout effectif. Pour une topologie et un algorithme donnés, le fanout effectif caractérise la puissance moyenne de la dissémination des sites infectés. De plus, il simplifie la comparaison théorique des différents algorithmes sur une topologie. Après avoir compris l’impact des topologies et les algorithmes sur les performances , nous proposons un algorithme fiable et efficace pour la topologie scale-free.

Publications 2012-2013

• 2013
  • R. Hu : “Algorithmes de dissémination épidémiques dans les réseaux à grande échelle : comparaison et adaptation aux topologie”, soutenance de thèse, soutenance 02/12/2013, direction de recherche Sens, Pierre, co-encadrement : Sopena, Julien (2013)
  • R. Hu, J. Sopena, L. Arantes, P. Sens, I. Demeure : “Efficient Dissemination Algorithm for Scale-Free Topologies”, ICPP'13 - 42^th International Conference on Parallel Processing, Lyon, France, pp. 310-319, (IEEE Computer Society) (2013)
  • R. Hu, J. Sopena, L. Arantes, P. Sens, I. Demeure : “Comparaisons équitables des algorithmes de gossip sur les topologies aléatoires à grande-échelle”, ComPAS'2013 - 9^e Conférence Française sur les Systèmes d'Exploitation (CFSE'13), Chapitre français de l'ACM-SIGOPS, GDR ARP, Grenoble, France (2013)
• 2012
  • R. Hu, J. Sopena, L. Arantes, P. Sens, I. Demeure : “Fair Comparison of Gossip Algorithms over Large-Scale Random Topologies”, Reliable Distributed Systems (SRDS), 2012 IEEE 31^st Symposium on, Irvine, California, United States, pp. 331-340, (IEEE Computer Society Press) (2012)