TCS+ Talk
We revisit the complexity of graph problems in the well-studied LOCAL
model of distributed computing, introduced by Linial [FOCS '87]. It is widely known
that for many of the classic distributed graph problems (including maximal independent
set (MIS) and $(\Delta+1)$-vertex coloring), the randomized complexity is at most
polylogarithmic in the size $n$ of the network, while the best known deterministic
complexity is typically $2^{O(\sqrt{\log n})}$. Understanding and potentially narrowing
down this exponential gap is one of the central long-standing open questions in the
area of distributed graph algorithms.
We investigate this question by introducing a complexity-theoretic framework, which
allows us to shed some light on the role of randomness in the LOCAL model. In particular,
we prove completeness results which, roughly speaking, show that some rather rudimentary-looking problems are ``complete" for essentially all the classic local distributed problems. In other words, if any of these complete problems can be solved deterministically in $\poly\log n$ rounds in the LOCAL model, we can deterministically solve essentially all the classic LOCAL-problems (including MIS and $(\Delta+1)$-coloring) in $\poly\log n$ rounds.
Perhaps the most surprising complete problem is the following: Color the nodes of the graph red or blue such that each node of a sufficiently large polylogarithmic degree has at least one neighbor of each color. The problem admits a trivial zero-round randomized algorithm, simply color each node randomly. This completeness result can be viewed as showing that the only obstacle to getting efficient deterministic algorithms in the LOCAL model is an efficient algorithm to round fractional values into integer values, while approximately preserving some linear constraints.
This talk is based on a joint work with Fabian Kuhn and Yannic Maus.
A version of the paper can be found here: https://arxiv.org/abs/1611.