Communication-Efficient Distributed Algorithms for Modern Networks

该研究项目的总体目标是显著推进通信高效分布式计算算法基础的最新发展。无处不在的移动电话和“智能”联网日常物品的出现导致了大型分散（移动）网络的创建。由于它们的临时性质，这些网络本质上是资源受限的，并且非常动态，因为网络拓扑和参与节点的集合可能会随着时间的推移而变化。用于资源受限设备的分布式算法必须通过发送少而短的消息来实现通信效率，因为可用的通信带宽通常仅随网络大小呈对数增长。通信效率对于优化设备的电池使用也至关重要，因为移动节点的能耗与无线电收发器的使用直接相关（c.f. Chang等人：the energy Complexity of Broadcast， 2017）。******现代网络通常是“无许可的”，也就是说任何节点都可以加入网络，这就要求分布式算法能够抵御网络中的恶意代理。在这些挑战的激励下，本研究的一个目标是设计容错和通信高效的算法，在ad hoc网络模型中实现分布式共识，这要求网络中的节点在每个节点开始时都有一些输入值时输出一个公共值。一个相关的目标是开发针对对抗性攻击和恶意对等体存在时维护网络连接属性的方法。******通信效率对于在大规模网络中执行分布式图计算也是至关重要的。为海量图获取高效的分布式算法是该研究项目在许多应用领域（例如生物网络）的另一个目标。此外，特定的图结构可以作为信息传播的稀疏通信骨干，这是有效解决共识等问题的先决条件。为了扩大理论结果的影响，本研究计划的第三个目标是对开发的分布式算法进行实验评估。******这项研究的结果可以使弹性和通信高效的分布式软件系统的发展成为可能。新兴技术的潜在应用有很多；从适用于资源受限设备的大型网络的改进的数字分类账和加密货币，到在物联网背景下提供更安全的分布式计算。本研究设计的图算法还可以在海量图数据集上实现更高效的分布式计算，这有可能改善大数据分析，并导致更好的数据驱动政策制定。

The overarching goal of this program of research is to significantly advance the state of the art in the algorithmic foundations of communication-efficient distributed computing. The ubiquity of mobile phones and the emergence of "smart" networked day-to-day objects have resulted in the creation of large decentralized (mobile) networks. Due to their ad hoc nature, these networks are inherently resource-constrained and very dynamic, as the network topology and the set of participating nodes might change over time. Distributed algorithms for resource-restricted devices must be communication-efficient by sending few and short messages, as the available communication bandwidth typically scales only logarithmically with the network size. Communication-efficiency is also crucial for optimizing battery-usage of devices, since the energy consumption of mobile nodes is directly related to radio transceiver usage (c.f. Chang et al: The Energy Complexity of Broadcast, 2017).******Modern networks are often "permissionless", in the sense that any node can join the network, which requires distributed algorithms to be resilient against malicious agents in the network. Motivated by these challenges, one goal of this research is the design of fault-tolerant and communication-efficient algorithms that achieve distributed consensus in ad hoc network models, which requires the nodes in a network to output a common value when each node starts out with some input value. A related objective is the development of methods for maintaining the network connectivity properties against adversarial attacks and in the presence of malicious peers. ******Communication-efficiency is also crucial for performing distributed graph computations in large-scale networks. Obtaining efficient distributed algorithms for massive graphs is another goal of this program of research with many application domains (e.g., biological networks). Moreover, certain graph structures can serve as sparse communication backbones for information dissemination, which makes them a prerequisite for solving problems such as consensus efficiently. To broaden the impact of the theoretical results, a third aim of this research program is the experimental evaluation of the developed distributed algorithms.******The outcomes of this research can enable the development of resilient and communication-efficient distributed software systems. The potential applications to emergent technologies are numerous; ranging from improved digital ledgers and crypto-currencies suitable for large networks of resource-restricted devices to providing more secure distributed computation in the context of the Internet of Things. The graph algorithms designed in this research can also lead to more efficient distributed computation on massive graph data sets, which has the potential to improve big data analytics and lead to better data-driven policy making.