论文标题
在渐近$ u_0 $ $ u_0 $指的洪水时间
On the Asymptotic $u_0$-Expected Flooding Time of Stationary Edge-Markovian Graphs
论文作者
论文摘要
考虑到$ u_0 $节点知道某些数据$ d_0 $。当节点之间的通信根据图形Markov模型$ \ OVILLINE {\ MATHCAL {g}} _ {N，{n，\ hat {p}} $，并带有可能性参数$ \ pame $ \ pame pam partimage，该说明将导出数据$ d_0 $的预期时间，以通过$ n $ nodes的网络传播。在此模型中，如果此边缘存在于$ k-1 $，并且具有概率$（1- \ hat {p}）$，则在离散时间$ k \ in \ mathbb {n}^+$之间存在两个节点之间的边缘，如果此边缘不存在，则如果此边缘不存在于$ k-1 $ k-1 $。每个边缘都被解释为双向通信链接，在该链接上共享了邻居之间的数据。假定初始通信图是带有参数$（n，\ hat {p}）$的ERDOS-RENYI随机图，因此我们考虑\ emph {stastary} Markov Markov Model $ \ overline {\ Mathcal {\ Mathcal {g}} _ { $ \ Overline {\ Mathcal {g}} _ {n，\ hat {p}} $的渐近“ $ u_0 $指望的洪水时间”定义为从$ u_0 $ nodes nodes $ n $ n $ n $ n lime niment Infience node $ u_0 $ nodes nodes $ d_0 $所需的预期迭代数。尽管图形Markov模型中渐近洪水时间的大多数结果都是\ emph {几乎确定}或\ emph {具有很高的概率}，但此处获得的界限是\ emph {在预期中}。但是，我们的界限更紧密，可能比以前的结果更完整。
Consider that $u_0$ nodes are aware of some piece of data $d_0$. This note derives the expected time required for the data $d_0$ to be disseminated through-out a network of $n$ nodes, when communication between nodes evolves according to a graphical Markov model $\overline{ \mathcal{G}}_{n,\hat{p}}$ with probability parameter $\hat{p}$. In this model, an edge between two nodes exists at discrete time $k \in \mathbb{N}^+$ with probability $\hat{p}$ if this edge existed at $k-1$, and with probability $(1-\hat{p})$ if this edge did not exist at $k-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,\hat{p})$, hence we consider a \emph{stationary} Markov model $\overline{\mathcal{G}}_{n,\hat{p}}$. The asymptotic "$u_0$-expected flooding time" of $\overline{\mathcal{G}}_{n,\hat{p}}$ is defined as the expected number of iterations required to transmit the data $d_0$ from $u_0$ nodes to $n$ nodes, in the limit as $n$ 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.
