Dissertation
On the role of congestion in distributed complexity
University of Iowa
Doctor of Philosophy (PhD), University of Iowa
Spring 2021
DOI: 10.17077/etd.005813
Abstract
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.
Details
- Title: Subtitle
- On the role of congestion in distributed complexity
- Creators
- Shreyas Pai
- Contributors
- Sriram Pemmaraju (Advisor)Bijaya Adhikari (Committee Member)Keren Censor-Hillel (Committee Member)Omar Chowdhury (Committee Member)Kasturi Varadarajan (Committee Member)
- Resource Type
- Dissertation
- Degree Awarded
- Doctor of Philosophy (PhD), University of Iowa
- Degree in
- Computer Science
- Date degree season
- Spring 2021
- DOI
- 10.17077/etd.005813
- Publisher
- University of Iowa
- Number of pages
- xv, 294 pages
- Copyright
- Copyright 2021 Shreyas Kiran Pai
- Language
- English
- Description illustrations
- illustrations
- Description bibliographic
- Includes bibliographical references (pages 272-294)
- Public Abstract (ETD)
Thanks to the technological advances in the past three decades, networks are everywhere around us, from social networks like facebook and twitter to physical networks like the Internet. The way a distributed algorithms researcher views a network is very much like how the Internet is set up: there are machines (e.g., a computer or mobile device) spread over vast physical distances and they communicate with each other through some communication network.
Networks interpreted in this manner are called distributed models of computation and these have been very successful in recent years for various applications in Computer Science. This success is partially due to the massive amounts of data that are processed by tech companies like Google, Facebook, Amazon, etc. These datasets are so massive that traditional methods of computing quickly become infeasible.
Distributed algorithms shine in such cases because they can partition a large dataset across multiple machines and these machines can interact with each other to process the entire dataset collaboratively. While this approach leads to very efficient processing, there are challenges unique to distributed computing that arise, which sometimes form an obstacle to designing efficient algorithms.
In this dissertation we explore the power and limitations of several distributed computing models by developing fast algorithms that get around these obstacles or by showing impossibility results, that is showing that no algorithm can ever get around the obstacles. We hope to eventually get fast implementations of the algorithms we design to solve problems in practice, whereas our impossibility results tell us when we should stop investing our efforts into designing faster algorithms.
- Academic Unit
- Computer Science
- Record Identifier
- 9984097477802771
Metrics
30 File views/ downloads
107 Record Views