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.