The goal of this project is to advance the state of the art in the design and analysis of efficient distribution approximation algorithms for various important network optimization problems. The emerging area of distributed approximation algorithms lies at the intersection of two well-established theoretical computer science areas: distributed computing and approximation algorithms. Distributed approximation algorithms tradeoff optimality of the solution for the amount of resources consumed by the distributed algorithm. Besides a fundamental theoretical interest in understanding the algorithmic complexity of distributed approximation, there is also a practical motivation in studying distributed approximation algorithms. Emerging networking technologies such as ad hoc wireless sensor networks and peer-to-peer networks operate under inherent resource constraints such as energy, bandwidth etc. A distributed algorithm which exchanges a large number of messages and takes a lot of time can consume a relatively large amount of resources, and is not suitable in a resource-constrained network. Also, the topology of these networks can change dynamically. Communication cost and running time is especially crucial in a dynamic setting. Hence it becomes necessary to design efficient distributed algorithms for various network optimization problems that have low communication and time complexity, even possibly at the cost of a reduced quality of solution.
The intellectual merit of this project lies in the development and analysis of new efficient distributed approximation algorithms for important network optimization problems including the minimum spanning tree and other spanning substructures, the minimum Steiner tree and related problems, the shortest paths problem etc. These are fundamental problems in distributed computing and are widely used primitives in distributed communication networks.
The first part of the project focuses on static networks, i.e., networks whose topology doesn't change with time. The project will design and analyze distributed approximation algorithms that give efficient performance, in terms of both time and message complexity, for a given approximation ratio. An important ingredient of the research is identifying appropriate graph parameters that capture the distributed complexity of the problem at hand. Such parameters serve as natural lower bounds and facilitate the design of optimal algorithms. An overarching goal is to develop uniform approaches to design efficient distributed approximation algorithms for a wide variety of problems.
The second part of the project focuses on design and analysis of distributed algorithms for dynamic networks, i.e., networks whose topology changes dynamically. The goal is to study efficient distributed dynamic algorithms to construct and maintain near-optimal solutions for important spanning substructure problems. The algorithms will exploit locality and will be designed to work well on dynamic network models.
The broader impact of this project is the potential to impact algorithm design in emerging communication networks, in particular, sensor networks and peer-to-peer networks. The project will yield efficient and scalable distributed algorithms with provable performance guarantees. The PI will collaborate with applied researchers to maximize the impact of the theoretical results to practical applications. The proposed research is a great opportunity for theory to continue to have a practical impact, and a valuable addition to the curricula in both algorithms and networks. The PI will develop a new course on distributed approximation algorithms that is closely related to the research. The course will also aid in disseminating mathematical tools and techniques needed for this research to a wider audience. The PI's research group, Network Algorithms and Analysis Laboratory, will train both graduate and undergraduate students to tackle a variety of algorithmic problems that arise in distributed networks, emphasizing use of randomization in designing efficient distributed algorithms, and probabilistic modeling and analysis of networks.
