Inondation dans les réseaux dynamiques

Résumé : Cette note résume nos travaux sur l'inondation dans les réseaux dynamiques. Ces derniers sont définis à partir d'un processus Markovien de paramètres $p$ et $q$ générant des séquences de graphes $(G_0,G_1,G_2,\ldots)$ sur un même ensemble $[n]$ de sommets, et tels que $G_t$ est obtenu à partir de $G_{t-1}$ comme suit~: si $e\notin E(G_{t-1})$ alors $e\in E(G_{t})$ avec probabilité $p$, et si $e\in E(G_{t-1})$ alors $e\notin E(G_{t})$ avec probabilité $q$. Clementi et al. (PODC 2008) ont analysé différent processus de diffusion de l'information dans de tels réseaux, et ont en particulier établi un ensemble de bornes sur les performances de l'inondation. L'inondation consiste en un protocole élémentaire où chaque n{\oe}ud apprenant une information à un temps $t$ la retransmet à tous ses voisins à toutes les étapes suivantes. Evidemment, en dépit de ses avantages en terme de simplicité et de robustesse, le protocole d'inondation souffre d'une utilisation abusive des ressources en bande passante. Dans cette note, nous montrons que l'inondation dans les réseaux dynamiques peut être mis en {\oe}uvre de façon à limiter le nombre de retransmissions d'une même information, tout en préservant les performances en termes du temps mis par une information pour atteindre tous les n{\oe}uds du réseau. La principale difficulté de notre étude réside dans les dépendances temporelles entre les connexions du réseaux à différentes étapes de temps.
Type de document :
Communication dans un congrès
Chaintreau, Augustin and Magnien, Clemence. AlgoTel, 2009, Carry-Le-Rouet, France. 2009
Liste complète des métadonnées

Littérature citée [14 références]  Voir  Masquer  Télécharger

https://hal.inria.fr/inria-00383915
Contributeur : Hervé Baumann <>
Soumis le : mercredi 13 mai 2009 - 19:27:33
Dernière modification le : jeudi 11 janvier 2018 - 06:17:42
Document(s) archivé(s) le : lundi 15 octobre 2012 - 10:17:05

Fichier

FloodingAlgoTel.pdf
Fichiers produits par l'(les) auteur(s)

Identifiants

  • HAL Id : inria-00383915, version 1

Collections

Citation

Hervé Baumann, Pierluigi Crescenzi, Pierre Fraigniaud. Inondation dans les réseaux dynamiques. Chaintreau, Augustin and Magnien, Clemence. AlgoTel, 2009, Carry-Le-Rouet, France. 2009. 〈inria-00383915〉

Partager

Métriques

Consultations de la notice

137

Téléchargements de fichiers

64