Bulletin of the EATCS · volume 115, pages 83–110, February 2015
This article gives a short survey of recent lower bounds for distributed graph algorithms. There are many classical graph problems (e.g., maximal matching) that can be solved in $O(\Delta + \log^* n)$ or $O(\Delta)$ communication rounds, where $n$ is the number of nodes and $\Delta$ is the maximum degree of the graph. In these algorithms, the key bottleneck seems to be a form of local coordination, which gives rise to the linear-in-$\Delta$ term in the running time. Previously it has not been known if this linear dependence is necessary, but now we can prove that there are graph problems that can be solved in time $O(\Delta)$ independently of $n$, and cannot be solved in time $o(\Delta)$ independently of $n$. We will give an informal overview of the techniques that can be used to prove such lower bounds, and we will also propose a roadmap for future research, with the aim of resolving some of the major open questions of the field.