On the role of congestion in distributed complexity
Shreyas Pai, Sriram V. Pemmaraju, Bijaya Adhikari, Keren Censor-Hillel, Omar Chowdhury, Kasturi Varadarajan · 2021
The size of data sets is increasing to the point where we cannot store all data in a single machine (e.g., a computer or mobile device). This is a problem for algorithms which assume that a single machine has access to the entire input, a very standard assumption in algorithms research. Distributed algorithms shine in such cases because they do not require a single machine to store the entire input. There are many situations where the input is naturally distributed among various machines. A common example is the Internet, where one wants to compute shortest paths to find efficient routes on the entire input, but each machine or router has only knowledge of its immediate neighbors in the communication network. This has resulted in renewed attention towards many models of distributed computing like the classic Local and Congest models and newer models like Congested Clique, k-machine, and Massively Parallel Computation. In all of these models, we have a collection of machines connected to each other via an underlying communication network and the input is partitioned across the machines. The goal for the machines is to compute some function of the entire input in an “efficient” manner, that is, using as few resources as possible. For example, when the input is an undirected graph, we would like to compute certain graph structures like Maximal Independent Set, Minimum Vertex Cover, Minimum Spanning Tree, etc. using as little communication as possible. In the models we consider in this dissertation, the communication network is subject to bandwidth constraints, which leads to congestion. This turns out to be an important obstacle to designing fast algorithms in these models. On the other hand, we can exploit these bandwidth constraints to prove lower bounds. In this dissertation, we explore the power and limitations of several distributed computing models by developing fast algorithms and showing unconditional lower bounds for three classes of problems: (1) Symmetry Breaking Problems, (2) Connectivity Problems, and (3) Optimization Problems. Our hope is that the algorithms we design will lead to practical implementations or that the algorithmic techniques we design/use will have wide-spread use in solving other problems efficiently. On the other hand the lower bounds we prove tell us whether it is worth investing more effort in designing more efficient algorithms. In many cases our algorithms and lower bounds are tight, that is, they are the same, up to small factors. This means that the algorithms achieve the best complexity one can hope for, and the lower bounds are optimal.