AF: Small: Distributed Algorithms for Near-Planar Networks

Carnegie Mellon University, Pittsburgh PA

Investigators

Abstract

The goal of this project is the development of an algorithmic toolbox to design efficient distributed algorithms for planar and near-planar networks. (Informally, a planar network is one that can be drawn on a two-dimensional surface without any lines crossing.) Many real-world networks and optimization problem instances have a near-planar structure that allows for simpler, more efficient, and often more practical algorithms. The study of such network structures and their algorithmic implications has been a very successful endeavor with a rich theory, many versatile tools, significant algorithmic advances, and drastic performance improvements on problem instances of interest. While modern systems become increasingly larger and more distributed, little is known about how distributed algorithms can be improved on near-planar instances. This project aims to change this and to bring similar improvements to the distributed setting. While its scope is primarily theoretical, the algorithms and general principles to be developed have the potential of laying the groundwork for practical algorithms with real-world impacts. The project will also have a broad educational impact. Much of the research will be done by or in collaboration with graduate students. Furthermore, the proposed research direction features many theoretical questions suitable for undergraduate students without extensive background knowledge and also provides opportunities for experiments and implementation projects. Lastly, the interdisciplinary nature of the problem will likely foster many collaborations between the PI and other researchers in different fields. Any tools and algorithms developed will be shared publicly. This project will initiate the principled study of distributed algorithms for planar and near-planar networks. In particular, for networks with diameter D and standard bandwidth-limitations (CONGEST model), the project aims at obtaining efficient distributed algorithms running in O(D) synchronous rounds for important standard optimization problems like maximum flow, minimum spanning tree, and various shortest path problems. This approach very timely connects to recent, far-reaching, distributed lower bounds which show that in general (sparse) graphs many optimization problems cannot be computed or even crudely approximated in less than Omega(sqrt(n))-rounds. The PI believes that this proposal provides an exciting new direction for the theory of distributed network optimization algorithms and gives a new perspective on the algorithmic study of planar and near-planar graphs. The expectation is that this broader research direction and the concrete initial results coming out of this project will spark the interest of the community and serve as a basis for a larger and more extensive investigation.