Parsimonious flooding in dynamic graphs
Hervé Baumann, Pierluigi Crescenzi, Pierre Fraigniaud · 2009
An edge-Markovian process with birth-rate p and death-rate q generates sequences of graphs (G0,G1,G2,…) with the same node set [n] such that Gt is obtained from Gt−1 as follows: if e ∉ E(Gt−1) then e ∈ E(Gt) with probability p, and if e ∈ E(Gt−1) then e ∉ E(Gt) with probability q. Clementi et al. (PODC 2008) analyzed thoroughly information dissemination in such dynamic graphs, by establishing bounds on their flooding time--flooding is the basic mechanism in which every node becoming aware of an information at step t forwards this information to all its neighbors at all forthcoming steps t∦ > t. In this paper, we establish tight bounds on the complexity of flooding for all possible birth rates and death rates, completing the previous results by Clementi et al. Moreover, we note that despite its many advantages in term of simplicity and robustness, flooding suffers from its high bandwidth consumption. Hence we also show that flooding in dynamic graphs can be implemented in a more parsimonious manner, so that to save bandwidth, yet preserving efficiency in term of simplicity and completion time.