Locality of Distributed Graph Problems

Locality is one of the central themes in the theory of distributed computing. In this thesis, we investigate the following three aspects of the locality of distributed graph problems.

1. Complexity Theory for the LOCAL Model:
One of the main goals of this thesis is to understand the spectrum of natural problem complexities that can exist in the LOCAL (local communication + no bandwidth constraint) model. We provide answer to the following fundamental questions regarding the nature of the LOCAL model: (i) How to classify the distributed problems according to their complexities? (ii) How much does randomness help? (iii) Can we solve more problems given more time?

2. Complexity of Distributed Coloring:
The coloring problem is one of the most well-studied classical problem in distributed computing. In this thesis, we devise distributed algorithms for the edge-coloring problem and the vertex-coloring problem in the LOCAL model that improve upon the previous state-of-the-arts.

3. Bandwidth Constraint:
In this thesis, we develop a framework for distributed algorithm design based on expander decompositions that allows us to apply CONGESTED-CLIQUE (all-to-all communication + with bandwidth constraint) algorithms to the CONGEST (local communication + with bandwidth constraint) model. Using this approach, we improve the the state-of-the-art upper bound for the triangle detection and enumeration problem in CONGEST.