Inondation dans les réseaux dynamiques

International audienceCette 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