Hop Limited Flooding Over Dynamic Networks
The authors study the performance of hop-limited broadcasting of a message in dynamic graphs where links between nodes switch between active and inactive states. They 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. They 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.