Communication-Efficient Distributed Algorithms for Modern Networks

现代网络的通信高效分布式算法

• 批准号: RGPIN-2018-06322
• 负责人: Robinson, Peter
• 金额: $ 2.04万
• 依托单位: McMaster University
• 依托单位国家: 加拿大
• 项目类别: Discovery Grants Program - Individual
• 财政年份: 2018
• 资助国家: 加拿大
• 起止时间: 2018-01-01 至 2019-12-31
• 项目状态: 已结题
• 来源: https://www.nserc-crsng.gc.ca/ase-oro/Details-Detailles_eng.asp?id=663516
• 关键词: Communication; Efficient; Distributed; Algorithms; Modern

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.

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