Distributed Algorithms for Fundamental Graph Problems

Two ongoing trends in computing are big data and parallelization. To incorporate these developments, the classic RAM model is not sufficient anymore for the design and analysis of algorithms. Many alternative models of computation have been proposed in the literature, each highlighting a different aspect of computation. The CONGEST model, a synchronous message-passing model with bounded message size, is a well-studied computational model that highlights the communication aspect between distributed processors. Many classic graph problems have been studied in this model, but so far close-to-optimal algorithms have been found for only some of these problems. The goal of this project is to significantly improve upon this state of the art in the CONGEST model.

The objective of this project is to make algorithmic progress on certain fundamental graph problems such as shortest paths, maximum flow, electrical flow, and sparsification in the CONGEST model. To achieve this goal, we will employ the powerful techniques that have recently been developed in the RAM model to obtain remarkable algorithmic results, in particular methods from continuous optimization and applications of spectral graph theory. These techniques are not yet well understood in the distributed algorithms community. Therefore this is a natural approach for making progress on the proposed problems.
Additionally we will use prototyping and visualization methods to observe the behavior of preliminary algorithmic approaches and to generate new hypotheses and ideas.