Locality in Distributed Graph Algorithms

TLDR

The paper studies distributed solutions to various graph algorithmic problems. The goal is to determine how much of a global solution can be derived from local information in distributed graph processing. The model assigns each graph node to a processor with a unique ID, allowing each processor to gather information from nodes within t hops in t time units while having unlimited computational power otherwise. The authors prove that 3‑coloring an n‑cycle requires Ω(log* n) time (tight), that any algorithm coloring a d‑regular tree of radius r in ≤2r/3 steps requires Ω(√d) colors, and that an O(Δ²)-coloring of an n‑vertex graph with maximum degree Δ can be achieved in O(log* n) time.

Abstract

This paper concerns a number of algorithmic problems on graphs and how they may be solved in a distributed fashion. The computational model is such that each node of the graph is occupied by a processor which has its own ID. Processors are restricted to collecting data from others which are at a distance at most t away from them in t time units, but are otherwise computationally unbounded. This model focuses on the issue of locality in distributed processing, namely, to what extent a global solution to a computational problem can be obtained from locally available data. Three results are proved within this model: • A 3-coloring of an n-cycle requires time $\Omega (\log ^ * n)$. This bound is tight, by previous work of Cole and Vishkin. • Any algorithm for coloring the d-regular tree of radius r which runs for time at most $2r/3$ requires at least $\Omega (\sqrt d )$ colors. • In an n-vertex graph of largest degree $\Delta $, an $O(\Delta ^2 )$-coloring may be found in time $O(\log ^ * n)$.