The Locality of Distributed Symmetry Breaking

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.

In submission to J. ACM

References in corpus (3)

• Fast Local Computation Algorithms
• Local Computation: Lower and Upper Bounds
• Toward more localized local algorithms: removing assumptions concerning global knowledge

Cited by in corpus (18)

• Simple dynamic algorithms for Maximal Independent Set and other problems
• Lessons from the Congested Clique Applied to MapReduce
• Dynamic Networks of Finite State Machines
• A Lower Bound for the Distributed Lovász Local Lemma
• Locally-Iterative Distributed (Delta + 1)-Coloring below Szegedy-Vishwanathan Barrier, and Applications to Self-Stabilization and to Restricted-Bandwidth Models
• A Fast Network-Decomposition Algorithm and its Applications to Constant-Time Distributed Computation
• New Techniques and Tighter Bounds for Local Computation Algorithms
• Polynomial Lower Bound for Distributed Graph Coloring in a Weak LOCAL Model
• Simple and Near-Optimal Distributed Coloring for Sparse Graphs
• The Family Holiday Gathering Problem or Fair and Periodic Scheduling of Independent Sets
• Improved Massively Parallel Computation Algorithms for MIS, Matching, and Vertex Cover
• Deterministic Distributed Edge-Coloring via Hypergraph Maximal Matching
• Local Computation Algorithms for Graphs of Non-Constant Degrees
• On the Complexity of Local Distributed Graph Problems
• Can We Break Symmetry with o(m) Communication?
• When Algorithms for Maximal Independent Set and Maximal Matching Run in Sublinear-Time
• Feedback from Nature: Simple Randomised Distributed Algorithms for Maximal Independent Set Selection and Greedy Colouring
• Optimal Dynamic Distributed MIS