FWF - Bandwidth - 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. Objectives. 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. Approach & Level of Originality. Our approach is two-fold: On the one hand, we aim at developing new communication efficient distributed algorithms addressing central open questions in the area, such as under-standing the role of randomness. This requires us to go well beyond the current state-of-the-art, which we, for example, achieve via novel methods for derandomization and new graph decompositions that are optimized for bandwidth restricted settings. On the other hand, we aim at determining the limits of distributed computation. A core goal is to identify universal underlying reasons for the hardness of distributed optimization. While such central points of hardness are well-known in the centralized world, such a result would be novel in the distributed setting. Besides, we aim at solving a number of smaller, easier problems that would serve as stepping stones towards these bigger goals. Communication efficient algorithms are often robust in the sense that they yield solutions in different computational models. Hence, in the long term, this project will also impact other areas such as massively parallel computation algorithms, sublinear algorithms, streaming, and local computation algorithms. Primary researchers involved. The research team consists of the PI (Ass. Prof. Yannic Maus, TU Graz) and two PhD students funded by this project. Additionally, we aim to continue established collaborations with international experts useful to our project and also to extend our collaboration network.