On the Asymptotic u0u_0-Expected Flooding Time of Stationary Edge-Markovian Graphs

preprint2020arXivOpen access

Abstract

Consider that u0u_0 nodes are aware of some piece of data d0d_0. This note derives the expected time required for the data d0d_0 to be disseminated through-out a network of nn nodes, when communication between nodes evolves according to a graphical Markov model G‾n,p^\overline{ \mathcal{G}}_{n,\hat{p}} with probability parameter p^\hat{p}. In this model, an edge between two nodes exists at discrete time k∈N+k \in \mathbb{N}^+ with probability p^\hat{p} if this edge existed at k−1k-1, and with probability (1−p^)(1-\hat{p}) if this edge did not exist at k−1k-1. 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 (n,p^)(n,\hat{p}), hence we consider a \emph{stationary} Markov model G‾n,p^\overline{\mathcal{G}}_{n,\hat{p}}. The asymptotic "u0u_0-expected flooding time" of G‾n,p^\overline{\mathcal{G}}_{n,\hat{p}} is defined as the expected number of iterations required to transmit the data d0d_0 from u0u_0 nodes to nn nodes, in the limit as nn 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.

Explore this paper’s authors, topics and related work.

Building this map preview

BZPEER is loading the nearby papers, people, topics and institutions for this page.

Reviews 0

Write a reviewWrite

No reviews yet.

Discussion 0

Add a commentWrite

No comments yet.