Locality of Distributed Graph Problems

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.PhDComputer Science & EngineeringUniversity of Michigan, Horace H. Rackham School of Graduate Studieshttps://deepblue.lib.umich.edu/bitstream/2027.42/149872/1/cyijun_1.pd