University thesis:
Dissertation, Universität Freiburg, 2018
Footnote:
Description:
Abstract: Many modern systems are built on top of large-scale networks such as the Internet, the world wide web, or sensor networks; complex networks also appear in nature, e.g., the human brain or society can be modeled as networks and the importance of networks is constantly growing. In all of these networks many 'entities', e.g., the human beings in our society or the neurons in the human brain, are connected through communication channels and use these to communicate and to interact with each other. <br>Despite the fact that entities can only talk to their direct neighbors in the network, i.e., the nodes' behavior is based on 'local information', usually the entirety of a system is supposed to come up with some kind of a 'global solution'. One of the core questions of this thesis is: "What global goals can be achieved based on only local information?"<br><br>To study algorithms in these networks we use the standard message passing model of distributed computing that is attributed to Linial [FOCS '87]: Nodes communicate in synchronous rounds, send messages of unbounded size and perform unbounded local computations. The model is called the LOCAL model as it focuses on the 'locality' of an algorithm, i.e., the number of rounds, and allows to study the previous core question in a precise mathematical sense.<br><br>In this thesis we improve on the state of the art localities for many classic distributed graph problems such as vertex coloring, edge coloring, degree splittings and the approximation of linear programs. Furthermore, we provide a lower bound on the locality to compute certain vertex colorings in a weak variant of the LOCAL model.<br><br>It has been known for a long time that randomization helps significantly in solving many of these problems. This is best illustrated by the vertex coloring problem where adjacent nodes need to output different colors. One obtains a simple and fast algorithm if, in every round, every uncolored node chooses a random color, keeps the color if no conflict occurs, otherwise it discards the color and repeats the process. Solving the problem is much harder without randomization and we study the following questions: "Can we characterize the problems for which randomization helps significantly and how randomization helps in solving them?"<br><br>We use a complexity theoretic approach to tackle the question. We show that the problem of 'rounding' fractional values to integers while satisfying some constraints is trivial in the randomized world but (so far) difficult for deterministic algorithm. Thus it can be seen as the main obstacle to fast deterministic algorithms. This is substantiated as the problem is 'complete' in the sense that any fast deterministic algorithm for 'rounding' would imply fast algorithms for many of the classic problems, including the 'maximal independent set problem'. Such an algorithm would answer one of the most important and oldest open questions in the area dating back to the definition of the model by Linial in [FOCS '87]