Distributed network algorithms

本研究的主题是网络环境下分布式算法的设计与分析。这种算法由网络中的单个实体（如处理器或移动代理）执行，没有任何中央监视器控制执行。我们研究了分布式算法处理的不完整或不可靠信息对其性能的影响，并设计了在存在故障或不完全了解网络的情况下有效工作的算法。我们关注以下主题：（部分）未知网络中的通信，网络中移动代理执行的计算任务，以及带有建议的网络算法。研究计划的目标是：1。对于拓扑未知或仅部分已知的网络，以及某些组件（节点和/或链路）可能存在故障的网络，构建有效的通信算法（用于广播和全对全通信等任务）。2. 在智能体感知和移动能力、通信能力和内存大小的各种限制下，为移动智能体对（部分）未知网络的探索和映射、将所有智能体聚集在网络的一个节点、移动智能体检测网络中的故障等任务构建高效的算法。3. 在提供给节点或移动代理的有关网络的信息量（建议）与在网络中执行给定任务（如通信、图形着色、网络探索或收集）的效率之间建立权衡。我们方法的新颖之处在于关注执行分布式算法的网络实体可用的信息量与完成计算任务的效率之间的权衡。本研究的意义在于展示了在各种网络计算环境下进行计算时处理不完全信息和处理故障的有效方法。

The subject of this research is the design and analysis of distributed algorithms working in a network environment. Such algorithms are executed by individual entities in the network, such as processors or mobile agents, without any central monitor controlling the execution. We investigate the impact of incomplete or unreliable 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 objectives of the research program are: 1. Construct efficient communication algorithms (for such tasks as broadcasting and all-to-all communication) for networks whose topology is unknown or known only partially, and for 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, detecting faults in the network by mobile agents, and others, under various restrictions on perceptive and moving capabilities of the agents, on their communication capacities and on their memory size. 3. Establish trade-offs between the amount of information about the network (advice) supplied to nodes or mobile agents and the efficiency of performing a given task in the network, such as communication, graph coloring, network exploration, or gathering. 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. The significance of this research is in showing efficient ways of coping with incomplete information and of handling faults while performing computations in various network computing environments.