Distributed network algorithms

分布式网络算法

• 批准号: RGPIN-2018-03899
• 负责人: Pelc, Andrzej
• 金额: $ 3.5万
• 依托单位: Québec en Outaouais
• 依托单位国家: 加拿大
• 项目类别: Discovery Grants Program - Individual
• 财政年份: 2020
• 资助国家: 加拿大
• 起止时间: 2020-01-01 至 2021-12-31
• 项目状态: 已结题
• 来源: https://www.nserc-crsng.gc.ca/ase-oro/Details-Detailles_eng.asp?id=711494
• 关键词: Distributed; network; algorithms

The subject of the proposed research is the design and analysis of distributed algorithms working in a network environment. Such algorithms are executed by individual entities, such as processors or mobile agents, without any central monitor controlling the execution. We investigate the impact of unreliable or incomplete information processed by distributed algorithms on their performance, and design algorithms working efficiently in the presence of faults, or in spite of incomplete knowledge of the network. We focus on the following topics: communication in (partially) unknown networks, computational tasks performed by mobile agents in networks, and network algorithms with advice. The main objectives of the research program are: 1. Construct efficient communication algorithms for such tasks as broadcasting and all-to-all communication, working in networks whose topology is (partially) unknown, in anonymous networks, and in networks some of whose components (nodes and/or links) may be faulty. 2. Construct efficient algorithms for such tasks as exploration and mapping of a (partially) unknown network by mobile agents, gathering all agents in one node of the network, finding a target by a team of mobile agents, detecting faults by mobile agents, and others, under various restrictions on perceptive and moving capabilities of the agents, on their communication capabilities and on their memory size. 3. Establish trade-offs between the amount of information about the network (called advice) supplied to nodes or mobile agents, and the efficiency of performing a given task in the network, such as communication, leader election, network exploration, or gathering of agents. The advice paradigm permits to measure the minimum amount of information sufficient for a given task, regardless of the type of this information, which can concern numerical parameters of the network, such as the diameter or the size, or provide knowledge about network topology. In our research, networks are modeled as graphs whose nodes represent processors, and edges represent communication links. The methodology we propose is two-fold: conjectures concerning algorithm performance will be formulated using computer simulations, and subsequently proved using techniques from combinatorial mathematics, graph theory and probabilistic analysis. The novelty of our approach is in focusing on trade-offs between the amount of information available to network entities executing a distributed algorithm and the efficiency of accomplishing a computational task. We want to design the best methods of performing distributed computations in a network, under a given amount and type of available knowledge. The significance of this research is in showing efficient ways of coping with incomplete information and of handling faults of components, while performing computations in various network computing environments.

提出的研究主题是工作在网络环境中的分布式算法的设计和分析。这样的算法由诸如处理器或移动代理的单个实体执行，而不需要任何中央监视器来控制执行。我们研究了分布式算法处理的不可靠或不完全信息对其性能的影响，并设计了在存在故障或不完全了解网络的情况下有效工作的算法。我们关注以下主题：(部分)未知网络中的通信，网络中移动代理执行的计算任务，以及带建议的网络算法。该研究计划的主要目标是： 1.为广播和全对全通信等任务构建高效的通信算法，工作在(部分)拓扑未知的网络、匿名网络和某些组件(节点和/或链路)可能有故障的网络中。 2.在移动代理的感知能力、移动能力、通信能力和内存大小等各种约束下，构造高效的算法，用于移动代理对(部分)未知网络的探测和映射，将所有代理聚集在网络的一个节点上，由一组移动代理寻找目标，由移动代理检测故障等。 3.在提供给节点或移动代理的关于网络的信息量(称为建议)和在网络中执行给定任务的效率之间建立权衡，例如通信、领导者选举、网络探索或代理的聚集。建议范例允许测量对于给定任务足够的最小信息量，而不考虑该信息的类型，该信息可以涉及网络的数字参数，例如直径或大小，或者提供关于网络拓扑的知识。 在我们的研究中，网络被建模为图，其节点代表处理器，边代表通信链路。我们提出的方法是双重的：关于算法性能的猜测将使用计算机模拟来制定，并随后使用组合数学、图论和概率分析的技术来证明。我们方法的新奇之处在于关注执行分布式算法的网络实体可用的信息量与完成计算任务的效率之间的权衡。我们希望在给定的可用知识数量和类型下，设计在网络中执行分布式计算的最佳方法。这项研究的意义在于展示了在各种网络计算环境中处理不完全信息和处理组件故障的有效方法。