Randomized Information Dissemination in Dynamic Environments

The authors consider randomized broadcast or information dissemination in wireless networks with switching network topologies. They show that an upper bound for the dissemination time consists of the conductance bound for a network without switching, and an adjustment that accounts for the number of informed nodes in each period between topology changes. Through numerical simulations, they show that their bound is asymptotically tight. They apply their results to the case of mobile wireless networks with unreliable communication links, and establish an upper bound for the dissemination time when the network undergoes topology changes and periods of communication link erasures.