We develop a simple and generic method to analyze randomized rumor spreading processes in fully connected networks. In contrast to all previous works, which heavily exploit the precise definition of the process under investigation, we only need to understand the probability and the covariance of the events that uninformed nodes become informed. This universality allows us to easily analyze the classic push, pull, and push-pull protocols both in their pure version and in several variations such as messages failing with constant probability or nodes calling a random number of others each round. Some dynamic models can be analyzed as well, e.g., when the network is a $G(n,p)$ random graph sampled independently each round [Clementi et al. (ESA 2013)]. Despite this generality, our method determines the expected rumor spreading time precisely apart from additive constants, which is more precise than almost all previous works. We also prove tail bounds showing that a deviation from the expectation by more than an additive number of $r$ rounds occurs with probability at most $\exp(-\Omega(r))$. We further use our method to discuss the common assumption that nodes can answer any number of incoming calls. We observe that the restriction that only one call can be answered leads to a significant increase of the runtime of the push-pull protocol. In particular, the double logarithmic end phase of the process now takes logarithmic time. This also increases the message complexity from the asymptotically optimal $\Theta(n \log\log n)$ [Karp, Shenker, Schindelhauer, V\"ocking (FOCS 2000)] to $\Theta(n \log n)$. We propose a simple variation of the push-pull protocol that reverts back to the double logarithmic end phase and thus to the $\Theta(n \log\log n)$ message complexity.
翻译:我们开发了一种简单通用的方法来分析全连接网络中的随机谣言传播过程。与以往的所有工作不同的是,我们只需要理解未知节点变为知情的事件的概率和协方差。这种普遍性使我们能够轻松分析经典的推动、拉动和推拉协议,包括它们的纯版本以及几种变体,例如消息随着恒定概率失败或节点每轮调用随机数量的其他节点。一些动态模型也可以进行分析,例如网络是独立抽样的$ G(n,p) $随机图每轮[Clementi等人(ESA 2013)]。尽管具有这种普遍性,我们的方法可以精确地确定预期的谣言传播时间,除了加性常数之外,这比几乎所有以前的工作都更精确。我们还证明了尾部限制,表明与期望值超过$r$轮的加性数字的偏差的概率不超过$\exp(-\Omega(r))$。我们进一步使用我们的方法来讨论节点可以回答任意数量的传入呼叫的常见假设。我们观察到只能回答一个呼叫的限制导致推拉协议的运行时间明显增加。特别是,这种双对数结束的过程现在需要对数时间。这也将消息复杂度从渐进最优的$\Theta (n\log \log n)$ [Karp, Shenker, Schindelhauer, Vocking (FOCS 2000)] 增加到$\Theta (n\log n)$。我们提出了一个简单的推拉协议变体,将其恢复到双对数结束阶段,因此恢复到$\Theta (n\log \log n)$消息复杂度。