Distributed network algorithms

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

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.