Distributed network algorithms

点击翻译按钮获取中文摘要

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.