论文标题
匿名动态网络中的计算是线性的
Computing in Anonymous Dynamic Networks Is Linear
论文作者
论文摘要
我们为匿名1个间隙连接的动态网络的过程提供了第一个线性时间计数算法。作为副产品，我们能够以$ 3n $的圆回计算每个在此类网络中可确定性计算的功能。如果不需要显式终止，则运行时间将提高到$ 2N $回合，我们表明这是最佳的添加剂（这也是第一个非平淡的下限）。作为我们的主要调查工具，我们引入了一种称为“历史树”的组合结构，该结构具有独立的兴趣。这使我们的论文完全独立，我们的证明优雅而透明，我们的算法直接实施。 近年来，已经大量努力致力于与领导者的匿名1间隔离连接网络计数算法的设计和分析。最近，一系列越来越复杂的作品，主要基于经典的批量分布技术，最近导致了$ o（{n^{4+ε}} \ log^{3}（n））$ rounds的著名计数算法（{n^{4+ε}} \ log^{3}（n））$ rounds（$ε> 0 $），这是本文前的艺术品的状态。我们的贡献不仅为历史树的应用开辟了一系列有希望的研究，而且还表明，匿名动态网络中的计算实际上是可行的，并且要求的要求远低于以前的猜想。
We give the first linear-time counting algorithm for processes in anonymous 1-interval-connected dynamic networks with a leader. As a byproduct, we are able to compute in $3n$ rounds every function that is deterministically computable in such networks. If explicit termination is not required, the running time improves to $2n$ rounds, which we show to be optimal up to a small additive constant (this is also the first non-trivial lower bound for counting). As our main tool of investigation, we introduce a combinatorial structure called "history tree", which is of independent interest. This makes our paper completely self-contained, our proofs elegant and transparent, and our algorithms straightforward to implement. In recent years, considerable effort has been devoted to the design and analysis of counting algorithms for anonymous 1-interval-connected networks with a leader. A series of increasingly sophisticated works, mostly based on classical mass-distribution techniques, have recently led to a celebrated counting algorithm in $O({n^{4+ ε}} \log^{3} (n))$ rounds (for $ε>0$), which was the state of the art prior to this paper. Our contribution not only opens a promising line of research on applications of history trees, but also demonstrates that computation in anonymous dynamic networks is practically feasible, and far less demanding than previously conjectured.
