Distributed Algorithms for Fundamental Graph Problems

This project on distributed network algorithms is part of the larger research area Theory of Algorithms. In general, this area of foundational research deals with efficient methods of computation. Efficient here means that the goal is to minimize the consumption of resources such as time, space, or energy. The theoretical research in algorithms starts where no significant progress can be achieved anymore by mere programming skills. Instead, improvements are usually obtained with mathematical know-how. This project draws its motivation from huge decentral computer networks like the Internet of Things. Our goal is to develop algorithms for networks that are so large that each component participating in the network only knows its local environment. This is called a distributed network and computation in such networks has to be carried out in a way that only performs communication of each component with its direct neighbors. Note that this model of computation can be made mathematically precise. Despite this limitation to local communication, we aim at developing algorithms for global problems in this project. In a nutshell, this means: Think globally, act locally! In particular, we will work on algorithms for finding the fastest connections in a network and for the optimal transport of goods. The methodological contribution of this project is the systematic application of methods from numerical optimization to distributed algorithms. Starting with the award-winning work of Spielman and Teng (Gödel Prize 2015), several methods have been developed for quickly computing approximate solutions to certain classes of systems of equations. Furthermore, it has been shown that these systems of equations are useful for computing solutions to network problems; this may sound surprising at first because equations and networks are two very different mathematical objects. However, prior work on numerical optimization techniques for networks mostly deals with non-local computation and is therefore often not directly applicable to distributed networks. In this project, we will extend the existing methods in a way that makes them applicable to the design of distributed algorithms.

This project on distributed network algorithms is part of the larger research area Theory of Algorithms. In general, this area of foundational research deals with efficient methods of computation. 'Efficient' here means that the goal is to minimize the consumption of resources such as time, space, or energy. The theoretical research in algorithms starts where no significant progress can be achieved anymore by mere programming skills. Instead, improvements are usually obtained by mathematical know-how. This project drew its motivation from huge decentralized computer networks like the Internet of Things. Our goal was to develop algorithms for networks that are so large that each component participating in the network only knows its local environment. This is called a distributed network and computation in such networks has to be carried out in a way that only performs communication of each component with its direct neighbors. Despite this limitation to local communication, we have developed algorithms for global problems in this project. In a nutshell, this means: "Think globally, act locally!" Starting with the award-winning work of Spielman and Teng (Gödel Prize 2015), several methods have previously been developed for quickly computing approximate solutions to certain classes of systems of equations. Furthermore, it has been shown that these systems of equations are useful for computing solutions to network problems. However, prior work on numerical optimization techniques for networks has mostly dealt with non-local computation and was therefore often not directly applicable to distributed networks. In this project, we have extended the existing methods in a way that made them applicable to the design of distributed algorithms. Further key results were achieved in the development of simple protocols for decision making and the dissemination of information, some of which have links to graph neural networks. Furthermore, a general method was developed to extend "centralized" quantum algorithms to entire quantum networks in which the messages exchanged between neighbors consist of qubits instead of classical bits. As usual in this type of research, numerous mathematical structures on networks have additionally been studied and improved "along the way", which has also led to improvements for algorithms outside the realm of distributed networks. This in particular concerns structures that approximate central properties of a network with small subnetworks.