Broadcast and consensus are most fundamental tasks in distributed computing. These tasks are particularly challenging in dynamic networks where communication across the network links may be unreliable, e.g., due to mobility or failures. Indeed, over the last years, researchers have derived several impossibility results and high time complexity lower bounds (i.e., linear in the number of nodes $n$) for these tasks, even for oblivious message adversaries where communication networks are rooted trees. However, such deterministic adversarial models may be overly conservative, as many processes in real-world settings are stochastic in nature rather than worst case. This paper initiates the study of broadcast and consensus on stochastic dynamic networks, introducing a randomized oblivious message adversary. Our model is reminiscent of the SI model in epidemics, however, revolving around trees (which renders the analysis harder due to the apparent lack of independence). In particular, we show that if information dissemination occurs along random rooted trees, broadcast and consensus complete fast with high probability, namely in logarithmic time. Our analysis proves the independence of a key variable, which enables a formal understanding of the dissemination process. More formally, for a network with $n$ nodes, we first consider the completely random case where in each round the communication network is chosen uniformly at random among rooted trees. We then introduce the notion of randomized oblivious message adversary, where in each round, an adversary can choose $k$ edges to appear in the communication network, and then a rooted tree is chosen uniformly at random among the set of all rooted trees that include these edges. We show that broadcast completes in $O(k+\log n)$ rounds, and that this it is also the case for consensus as long as $k \le 0.1n$.
翻译:广播和共识是分布式计算中最基本的任务。 这些任务在动态网络中特别具有挑战性, 因为网络联系的随机性可能是不可靠的, 例如由于流动性或失败。 事实上, 过去几年里, 研究人员为这些任务得出了数种不可能的结果和高时间复杂性的下限( 即节点数的线性), 甚至对于那些通信网络根植于树的模糊信息对手来说也是如此。 然而, 这种确定性的对立模式可能过于保守, 因为现实世界环境中的许多进程在性质上是随机的,而不是最坏的。 本文启动了对随机性动态网络的广播和共识的研究, 引入了一个随机的模糊信息。 然而, 我们的模式在流行病中, 也让人想起了SI 模式的循环性循环( 也就是由于明显缺乏独立性, 使得分析更加困难 ) 。 具体地说, 如果信息传播与随机性的树一起进行, 广播和共识的完整且具有很高的概率, 也就是在对数时间上。 我们的分析证明了一个关键变量的独立性, 使得正式理解传播网络的正确性 。