Abstract
Symmetry breaking problems are among the most well studied in the field of distributed computing and yet the most fundamental questions about their complexity remain open. In this paper we work in the LOCAL model (where the input graph and underlying distributed network are identical) and study the randomized complexity of four fundamental symmetry breaking problems on graphs: computing MISs (maximal independent sets), maximal matchings, vertex colorings, and ruling sets. A small sample of our results includes - An MIS algorithm running in $O(\log^2\Delta + 2^{O(\sqrt{\log\log n})})$ time, where $\Delta$ is the maximum degree. This is the first MIS algorithm to improve on the 1986 algorithms of Luby and Alon, Babai, and Itai, when $\log n \ll \Delta \ll 2^{\sqrt{\log n}}$, and comes close to the $\Omega(\log \Delta)$ lower bound of Kuhn, Moscibroda, and Wattenhofer.
- A maximal matching algorithm running in $O(\log\Delta + \log^4\log n)$ time. This is the first significant improvement to the 1986 algorithm of Israeli and Itai. Moreover, its dependence on $\Delta$ is provably optimal.
- A method for reducing symmetry breaking problems in low arboricity/degeneracy graphs to low degree graphs. (Roughly speaking, the arboricity or degeneracy of a graph bounds the density of any subgraph.) Corollaries of this reduction include an $O(\sqrt{\log n})$-time maximal matching algorithm for graphs with arboricity up to $2^{\sqrt{\log n}}$ and an $O(\log^{2/3} n)$-time MIS algorithm for graphs with arboricity up to $2^{(\log n)^{1/3}}$. Each of our algorithms is based on a simple, but powerful technique for reducing a randomized symmetry breaking task to a corresponding deterministic one on a poly$(\log n)$-size graph.
Introduction: Breaking the Symmetry Stalemate
In distributed systems, nodes often begin in identical states. To perform coordinated tasks, they must "break symmetry"—for instance, by electing a set of non-adjacent leaders (a Maximal Independent Set, or MIS) or pairing up neighbors (a Maximal Matching). For nearly 30 years, the fastest randomized algorithms for these problems were stuck at $O(\log n)$ rounds, where $n$ is the number of nodes. This limitation, known as the "union bound barrier," arises because ensuring global success with high probability typically requires communication rounds proportional to $\log n$.
This paper bypasses this barrier, introducing algorithms whose runtimes depend primarily on the local maximum degree ($\Delta$) rather than the global network size ($n$). By doing so, it achieves the first major speedups for these fundamental problems since the 1980s.
The Two-Phase Framework
The core innovation is a powerful two-phase strategy that bridges randomized and deterministic techniques:
- Phase I: Iterated Randomized Experiment. Nodes execute a randomized symmetry-breaking process for a number of rounds depending only on $\Delta$ (e.g., $O(\log \Delta)$). While this doesn't solve the problem for the entire graph, it ensures that any remaining "unsolved" parts are reduced to small, disconnected components of size at most $\text{poly}(\log n)$.
- Phase II: Deterministic Cleanup. Because the remaining components are small, the algorithm switches to a deterministic approach. Deterministic algorithms are not subject to the union bound barrier. By running them on $\text{poly}(\log n)$-sized instances, their complexity—which usually depends on the number of nodes—becomes negligible relative to the original $n$.
Additionally, the authors introduce a degree-reduction method for "low-arboricity" graphs. Arboricity ($\lambda$) measures global sparsity even when local degrees are high. This method allows reducing high-degree problems to lower-degree ones, further accelerating symmetry breaking in sparse networks.
Key Results and Improvements
The paper establishes several new upper bounds that significantly improve upon decades of prior work. The following comparisons highlight the performance gains across different graph classes.
Maximal Independent Set (MIS)
The new MIS algorithm achieves a runtime of $O(\log^2 \Delta + 2^{O(\sqrt{\log \log n})})$. This represents the first significant improvement over the classic 1986 algorithms by Luby and Alon et al. for a wide range of parameters.
Maximal Matching
For Maximal Matching, the paper delivers an $O(\log \Delta + \log^4 \log n)$ time algorithm. This is the first major improvement over the 1986 Israeli-Itai algorithm, and its dependence on $\Delta$ is provably optimal, matching established lower bounds.
Vertex Coloring and Ruling Sets
The paper also improves $(\Delta + 1)$-coloring to $O(\log \Delta + 2^{O(\sqrt{\log \log n})})$ time and establishes a provable complexity gap between computing an MIS and a $(2, 2)$-ruling set.
Conclusion and Future Directions
The results demonstrate that the randomized complexity of symmetry breaking is "tethered" to deterministic counterparts. Any future improvement in deterministic network decomposition for small graphs will automatically accelerate these randomized algorithms. While this work significantly closes the gap, open questions remain regarding the true optimal complexity of $(\Delta+1)$-coloring and whether algorithms can match the $\Omega(\min\{\log \Delta, \sqrt{\log n}\})$ lower bounds across all graph classes.
Summary updated