Grant: Discovery Grants Program - Individual

Our goal is the design and analysis of distributed algorithms working in networks. Such algorithms are executed by network components, such as processors or mobile agents, without any central monitor controlling the execution. A difficulty in the design of distributed algorithms in networks is the incompleteness of information available to executing entities. They often do not know the topology of the network or bounds on message delivery time. Available data may be unreliable, due to failures of network components: information may be corrupted by malicious faults. We want to study the impact of unreliable or incomplete information processed by distributed network algorithms on their correctness and performance. The aim is to design algorithms working efficiently in the presence of faults, or in spite of incomplete knowledge. We focus on three topics: communication in (partially) unknown networks, computational tasks performed by mobile agents in networks, and network algorithms with advice. The objectives of our research are: 1. Construct efficient algorithms for such communication tasks as broadcasting and gossiping, working in (partially) unknown networks, and in networks with faulty components. Establish the impact of asynchrony and of the presence of faults on feasibility and efficiency of communication tasks. 2. Design efficient algorithms for such tasks as network exploration by mobile agents, or gathering all agents in one node, under various restrictions on capabilities of agents. Study the impact of restrictions on information available to agents and of faults in their functioning, on the feasibility and performance of network tasks. In applications, agents can be mobile robots circulating through corridors of a mine, or software agents navigating in a computer network. 3. Establish trade-offs between the amount of information about the network (called advice) supplied to nodes or mobile agents, and the feasibility and efficiency of performing network tasks, such as communication, network exploration, or gathering of agents. In our research, networks are modelled as graphs whose nodes are processors and edges are communication links. The methodology we propose is two-fold: conjectures concerning algorithm performance will be formulated by testing them on typical (often computer generated) examples, 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 and the efficiency of accomplishing a distributed task in networks. Our goal is to design the best possible 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 and unreliable information, while performing distributed computations in network environments.