Hop Limited Flooding over Dynamic Networks

We consider performance of hop-limited broadcasting of a message in dynamic graphs where links between nodes switch between active and inactive states. We analyze the performance with respect to the completion time, defined as the time for the message to reach a given portion of nodes, and the communication complexity, defined as the number of message forwarding per node. We analyze two natural flooding algorithms. First is a lazy algorithm where the message can be forwarded by a node only if it was first received by this node through a path shorter than the hop limit count. Second is a more complex protocol where each node forwards the message at a given time, if it could have been received by this node through a path shorter than the hop limit count. We derive exact asymptotics for the completion time and the communication complexity for large network size which reveal the effect of the hop limit count. Perhaps surprisingly, we find that both flooding algorithms perform near optimum and that the simpler (lazy) algorithm is only slightly worse than the other, more complicated algorithm. The results provide insights into performance of networked systems that use hop limits, for example, in the contexts of peer-to-peer systems and mobile ad-hoc networks.