An "anonymous dynamic network" is a network of indistinguishable processes whose communication links may appear or disappear unpredictably over time. Previous research has shown that deterministically computing an arbitrary function of a multiset of input values given to these processes takes only a linear number of communication rounds. However, fast algorithms for anonymous dynamic networks rely on the construction and communication of large data structures called "history trees", whose size is polynomial in the number of processes. This approach is unfeasible if the network is "congested", and only messages of logarithmic size can be sent though its links. Observe that sending a large message piece by piece over several rounds is not in itself a solution, due to the anonymity of the processes combined with the dynamic nature of the network. Moreover, it is known that certain basic tasks such as all-to-all token dissemination (by means of single-token forwarding) require $\Omega(n^2/\log n)$ rounds in congested networks. In this work, we develop a series of practical and efficient techniques that make it possible to use history trees in congested anonymous dynamic networks. Among other applications, we show how to compute arbitrary functions in such networks in $O(n^3)$ communication rounds, greatly improving upon previous state-of-the-art algorithms for congested networks.

翻译：“ 匿名动态网络” 是一个无法区分的流程网络, 其通信联系可能出现或长期无法预测地消失。 先前的研究显示, 确定地计算给这些流程的多个输入值的任意功能仅需要线性数循环。 然而, 匿名动态网络的快速算法依赖于被称为“ 历史树” 的大型数据结构的构建和通信, 其大小在进程数量上是多式的。 如果网络“ 混在一起”, 并且只有对数大小的信息才能通过链接发送。 观察通过几轮发送一小块的大型信息本身并不是一个解决方案, 因为这些进程与网络的动态性质结合在一起的匿名性。 此外, 众所周知, 某些基本任务, 如所有到所有象征的传播( 单向转发手段), 其规模在多个进程中需要$- Omega (n2/\log n) 。 如果网络是“ 混在一起”, 并且只有对数大小的信息才能发送 。 在这项工作中, 我们开发了一系列实用和高效的技术, 将匿名通信网络发送成一小片段, 将它本身不是一种解决方案的解决方案, 。 。 此外, 在历史树中可以大量地展示其他的网络 。