Flooding in Dynamic Graphs

One of the basic communication tasks which has been extensively studied in the context of communication networks is the broadcast operation: one distinguished node of the network (the source node) aims at sending a message to all the other nodes of the network. The simplest communication process that implements such an operation is the flooding mechanism, according to which (1) the source node is initially informed, and (2) when a node v, which is not informed yet, has an informed neighbor, then v becomes informed itself, at the next time step. The question is how long does it take to get all the nodes informed? That is, what is the speed of information spreading? Clearly, this question has an easy answer in the case of static networks: the flooding completion time is just equal to the diameter of the network. In a dynamic network, however, nodes and edges can appear and disappear over time. (Several emerging networking technologies such as ad hoc wireless, sensor, mobile networks, and peer-to-peer networks are inherently dynamic). In this case, it is not even clear whether the flooding completion time is finite. In order to investigate such an issue, the concept of evolving graph has been introduced in the literature (an evolving graph is a sequence of graphs G[t] with the same set of nodes). This concept is clearly general enough for allowing us to model basically any kind of dynamicity, ranging from adversarial evolving graphs to random evolving graphs, in which, at each time step, the graph G[t] is chosen randomly according to a probability distribution over a specified family of graphs. In this talk, we survey some recent results which have been obtained while analyzing the flooding completion time in the case of a special class of random evolving graph model, that is, the edge-Markovian model: according to this model, the evolving graph starts with an arbitrary initial graph, and, at every time step, if an edge exists (respectively, does not exist), then it will die (respectively, appear) at next time step with probability q (respectively,p)