Reliable Broadcasting in Random Networks and the Effect of Density
Reliable Broadcasting in Random Networks and the Effect of Density
复制标题
随机网络中的可靠广播和密度的影响
DOI：
--
复制
发表时间：
2010
期刊：
影响因子：
--
通讯作者：
K. Panagiotou
中科院分区：
文献类型：
--
作者：
N. Fountoulakis;Anna Huber;K. Panagiotou
广播算法对于分布式系统工程至关重要。在本文中，我们重新审视了经过充分研究的经典消息广播推送协议，并研究了它的错误版本。假设最初只有一个节点拥有一些信息，在每一阶段，每个被通知的节点都会随机且独立地选择其邻居之一，并以某种概率 q 将消息传递给它，也就是说，它以 1-q 的概率失败。推送协议在完全连接的网络上的性能很好理解，其中每个节点都通过到每个其他节点的链接连接，且 q=1。特别是，Frieze 和 Grimmett 证明，推送协议以 1-o(1) 的概率在 (1±ε) (log_2 n + ln n) 阶段内完成消息的广播，其中 n 是网络中的节点数量。然而，在比完整图稀疏得多的网络上，广播时间没有严格限制。在这项工作中，我们考虑 n 个节点上的随机网络，其中每条边都以概率 p 存在，独立于所有其他边。我们证明，如果 p≥ α(n)ln n/n，其中 α(n) 是随着 n 增长而趋于无穷大的任意函数，则传输错误的推送协议会在 (1±±ε)(log_{1+q} n + 1/q ln n) 阶段内以 1-o(1) 的概率广播消息。换句话说，在几乎每个密度为 d 且 d ≥ α(n) ln n 的网络中，推送协议广播消息的速度与在全连接网络中一样快，并且速度仅受成功概率 q 的影响。这是相当令人惊讶的，因为所需的时间基本上不受大多数链接丢失这一事实的影响。我们的结果附有实验评估。
Broadcasting algorithms are of fundamental importance for distributed systems engineering. In this paper we revisit the classical and well-studied push protocol for message broadcasting and we investigate a faulty version of it. Assuming that initially only one node has some piece of information, at each stage every one of the informed nodes chooses randomly and independently one of its neighbors and passes the message to it with some probability q that is, it fails to do so with probability 1-q. The performance of the push protocol on a fully connected network, where each node is joined by a link to every other node, with q=1 is very well understood. In particular, Frieze and Grimmett proved that with probability 1-o(1) the push protocol completes the broadcasting of the message within (1±ε) (log_2 n + ln n) stages, where n is the number of nodes in the network. However, there are no tight bounds for the broadcast time on networks that are significantly sparser than the complete graph. In this work we consider random networks on n nodes, where every edge is present with probability p, independently of every other edge. We show that if p≥ α(n)ln n/n, where α(n) is any function that tends to infinity as n grows, then the push protocol with faulty transmissions broadcasts the message within (1±±ε)(log_{1+q} n + 1/q ln n) stages with probability 1-o(1). In other words, in almost every network of density d such that d ≥ α(n) ln n, the push protocol broadcasts a message as fast as in a fully connected network and the speed is only affected by the success probability q. This is quite surprising in the sense that the time needed remains essentially unaffected by the fact that most of the links are missing. Our results are accompanied by experimental evaluation.