Jukka Suomela

Local coordination and symmetry breaking

Bulletin of the EATCS · volume 115, pages 83–110, February 2015

author’s version publisher’s version


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.


This material is presented to ensure timely dissemination of scholarly and technical work. Copyright and all rights therein are retained by authors or by other copyright holders. All persons copying this information are expected to adhere to the terms and constraints invoked by each author’s copyright. In most cases, these works may not be reposted without the explicit permission of the copyright holder.