Grant: Discovery Grants Program - Individual

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.