Distributed Algorithms: The Role of Bandwidth Restrictions

With the fast growth of networks and the rapid increase of the size of our data, distributed algorithms in networks will play a crucial role in our future and will be relevant in almost all aspects of life. This project aims at advancing our understanding of the foundational aspects of these areas. Algorithms operating in such settings have to deal with different forms of communication restriction, e.g., caused by large distances between computers in a network or bandwidth restrictions of communication links. The main goal of this project is to provide a fundamental theory and to significantly extend the understanding of the role of communication restrictions for distributed computations. Thus, in this project, we aim at developing new communication-efficient distributed algorithms for central problems in the area. An example problem that we study is the problem of assigning frequencies in a sensor network such that the frequencies can be used for interference-free communication. Hence, the objective is to use few frequencies and to not assign the same frequency to close-by sensors. Often it is much easier to solve these problems if the computers can make so-called random decisions. In principle this means that the computers can roll a dice to decide on the next step. In parts of this project we aim at designing fast algorithms that do not rely on such random decisions. The benefit of these algorithms is that they are more reliable and never err. Another set of problems that we study are optimization problems, e.g., the placement of servers in a network to roll out an update. Here the objective is to use few servers and to ensure that every computer of the network has a server in its vicinity. It seems that it is much more difficult to solve these problems with limited bandwidth in the communication between computers and we investigate to which extent and why this is the case. All problems considered in this project serve as essential building blocks in other algorithms.