Skip to Main content Skip to Navigation
Conference papers

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.
Document type :
Conference papers
Complete list of metadata

Cited literature [14 references]  Display  Hide  Download

https://hal.inria.fr/inria-00383915
Contributor : Hervé Baumann <>
Submitted on : Wednesday, May 13, 2009 - 7:27:33 PM
Last modification on : Saturday, March 28, 2020 - 2:09:12 AM
Long-term archiving on: : Monday, October 15, 2012 - 10:17:05 AM

File

FloodingAlgoTel.pdf
Files produced by the author(s)

Identifiers

  • HAL Id : inria-00383915, version 1

Citation

Hervé Baumann, Pierluigi Crescenzi, Pierre Fraigniaud. Inondation dans les réseaux dynamiques. AlgoTel, 2009, Carry-Le-Rouet, France. ⟨inria-00383915⟩

Share

Metrics

Record views

215

Files downloads

172