Local and Global Problems in Decentralized Computing

In the last decade, the theory of both distributed and massively parallel algorithms has undergone an incredible development. The wealth of recent results for local and global graph problems and the appearance of new algorithmic techniques whose potential is far from exhausted lead to many research opportunities that we describe below and pursue with this proposal. In this proposal, we study foundational aspects of algorithms in the areas of distributed and massively parallel computing. 1) Our first goal is to initiate the development of a distributed complexity theory that goes far beyond the severe restrictions of current distributed complexity theory for local graph problems. A fully developed distributed complexity theory would have massive implications on the state of the art for many of the problems central to distributed computation. 2) We aim to leverage the power of techniques developed in the context of local problems---which have been the object of a thorough study in recent years---for (global) optimization problems where the impact of these techniques has been very limited. Additionally, we will initiate the development of a distributed complexity theory for optimization problems. 3) We aim to develop a massively parallel complexity theory for local graph problems and optimization problems. 4) In each of these directions, we aim to significantly improve known algorithms and impossibility results for fundamental problems, such as load balancing problems, graph coloring problems, maximal matchings, maximum matching approximations, or minimum vertex cover approximations. One core novelty of our approach is that we study distributed and parallel algorithms simultaneously from a complexity-theoretic, a problem-centric, and a model-centric viewpoint. For example, in the model-centric viewpoint we will develop methods to automate the knowledge transfer between distributed and massively parallel computation, aiming for generic approaches that---in contrast to previous work---will allow knowledge transfer for large classes of problems at once. The proposed structured and complexity-theoretic approaches are new for the studied settings. In particular, the approach of leveraging techniques for local problems to solve global problems has not been studied in a systematic manner. The combination of the different viewpoints---whose interplay we expect to profit from significantly---is also new. The research team consists of the PIs (Dr. Sebastian Brandt, Univ. Prof. Dr. Yannic Maus) and three PhD students funded by the proposed project. The proposal builds on the unique combination of the individual expertise of the two PIs.