Communication-Efficient Distributed Algorithms for Modern Networks

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

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

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