Locality of Distributed Graph Problems

Abstract

Locality is one of the central themes in distributed computing. Suppose in a network each node only has direct communication with its local neighbors, how efficiently can a global task be solved? We aim to investigate the locality of fundamental distributed graph problems. Toward this goal, we consider the following three basic abstract models of distributed computing.

• LOCAL: each device has direct communication links with its neighbors, there is no message size constraint.

• CONGEST: each device has direct communication links with its neighbors, the size of each message is at most O(log n) bits.

• CONGESTED-CLIQUE: each device has direct communication links with all other devices, the size of each message is at most O(log n) bits.

A brief summary of our results is as follows.

1. Complexity Theory for the LOCAL Model: We study the spectrum of natural problem complexities that can exist in the LOCAL model. We provide answers 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 a classical and well-studied problem in distributed computing. 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 art.

3. Bandwidth Constraint: We develop a new framework for algorithm design based on expander decompositions that allows us to apply CONGESTED-CLIQUE techniques to the CONGEST model. Using this approach, we provide improved algorithms for the triangle detection and enumeration problem in CONGEST.