Designing and finding very fast distributed algorithms for bounded-degree graphs

Abstract

Distributed computing studies models where computation is split between multiple interconnected entities which can communicate with each other to achieve a common goal. In this thesis we look at the setting where the communication network is sparse, i.e., it has a bounded degree.

We first study a family of problems that can be characterized by a fact that their solutions can be locally checked for correctness. This rich family is called locally checkable labeling (LCL) problems and contains, for example, the problems of computing proper colorings, maximal independent set, maximal matching and orientation problems. The aim is to completely characterize these LCL problems in a given network topology and be able to automatically synthesize an asymptotically optimal algorithm given any LCL problem. We have achieved a complete characterization and synthesis for the following graph families: paths, cycles and regular rooted trees and a partial characterization for regular undirected trees. The results are complemented by unified implementations of all classifiers for asymptotic round complexity. Some of the results are using a newly discovered connection to automata theory while others use a novel concept of certificates of solvability.

In the second part of the thesis we focus on a specific problem of sparse matrix multiplication in a setting of low-bandwidth communication. We show that in the case of uniformly sparse matrices where each row and column has at most d non-zeroes we can break the quadratic barrier with respect to d and obtain a faster algorithm. One of the techniques used is to iteratively find regions that are locally dense and use more efficient dense multiplication algorithms for computing those parts.