Understanding the Distributed Complexity of Infinite Problems

Abstract

Distributed computing refers to the method where multiple computers on a communication network work together to solve some common problem. The underlying network can be viewed as a graph $G=(V,E)$ where the computers act as vertices, and the communication links between the computers act as edges. In order to solve a specific problem, all the computers, in parallel, run their own version of the algorithm. An example of a problem studied in distributed computing is the problem of finding a maximal matching of the underlying network. In this problem, we need to pick a set of edges $M$ which satisfies two properties: (1)\ no two edges in $M$ can share a vertex, and (2)\ no more edges can be added to $M$ so that property (1) is still maintained. The problem can also be viewed as computing a function $f\colon E \rightarrow \{0,1\}$ such that for a given edge $e$, $f(e) = 1$ if and only if $e \in M$.

In this thesis, I am interested in understanding infinite problems in the distributed setting. An infinite problem refers to a problem whose solution space is infinite. An example of such a problem is the problem of finding a maximal fractional matching. It is the fractional relaxation of the maximal matching problem, and allows for the function $f$ to take any fractional value from $0$ and $1$. While finite problems (problems with finite solution space) have been studied extensively in the distributed setting, relatively little work has been done to formalize the notion of infinite problems.

This thesis provides a definition for infinite problems, in a way that it can be represented using finite description. After defining infinite problems, one question arises naturally: can a given infinite problem be solved without any communication (i.e.,\ in $0$ rounds)? This problem is well understood for finite problems; there exists an algorithm that decides whether a given finite problem can be solved using $0$ rounds or not. In this thesis, I give an algorithm that answers the same for infinite problems.

Moreover, I also investigate automatic tools to derive lower bounds for infinite problems. In particular, I focus on round elimination for the maximal fractional matching problem. Round elimination is a technique that has been used successfully for obtaining tight lower bounds for finite problems such as maximal matching and sinkless orientation. However, the same technique has not been used for infinite problems. I study the application of round elimination for the fractional variant of maximal matching and develop techniques that help to analyze the result of round elimination on maximal fractional matching.