On the Asymptotic -Expected Flooding Time of Stationary Edge-Markovian Graphs
Consider that nodes are aware of some piece of data . This note derives the expected time required for the data to be disseminated through-out a network of nodes, when communication between nodes evolves according to a graphical Markov model with probability parameter . In this model, an edge between two nodes exists at discrete time with probability if this edge existed at , and with probability if this edge did not exist at . Each edge is interpreted as a bidirectional communication link over which data between neighbors is shared. The initial communication graph is assumed to be an Erdos-Renyi random graph with parameters , hence we consider a \emph{stationary} Markov model . The asymptotic "-expected flooding time" of is defined as the expected number of iterations required to transmit the data from nodes to nodes, in the limit as approaches infinity. Although most previous results on the asymptotic flooding time in graphical Markov models are either \emph{almost sure} or \emph{with high probability}, the bounds obtained here are \emph{in expectation}. However, our bounds are tighter and can be more complete than previous results.