The locality of distributed symmetry breaking

DOI10.1145/2903137zbMATH Open1426.68020arXiv1202.1983OpenAlexW2467514673MaRDI QIDQ3177792FDOQ3177792

Authors:

Publication date: 2 August 2018

Published in: Journal of the ACM (Search for Journal in Brave)

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(lo{g}^{2}Delta+2^{O(sqrtloglogn)})$ 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 $lognllDeltall{2}^{sqrtlogn}$, and comes close to the $Omega(logDelta)$ lower bound of Kuhn, Moscibroda, and Wattenhofer. - A maximal matching algorithm running in $O(logDelta+lo{g}^{4}logn)$ 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(sqrtlogn)$-time maximal matching algorithm for graphs with arboricity up to $2^{sqrtlogn}$ and an $O(lo{g}^{2/3}n)$-time MIS algorithm for graphs with arboricity up to $2^{(logn{)}^{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$(logn)$-size graph.

Full work available at URL: https://arxiv.org/abs/1202.1983

Recommendations

• An Improved Distributed Algorithm for Maximal Independent Set
• Distributed \((\Delta+1)\)-coloring in sublogarithmic rounds
• Distributed Maximal Independent Set using Small Messages
• A new technique for distributed symmetry breaking
• MIS on trees

zbMATH Keywords

matchingvertex coloringdistributed networksMIS

Mathematics Subject Classification ID

Graph theory (including graph drawing) in computer science (68R10) Coloring of graphs and hypergraphs (05C15) Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70) Distributed systems (68M14)

Cited In (60)

• Sublogarithmic distributed MIS algorithm for sparse graphs using Nash-Williams decomposition
• The complexity of symmetry breaking in massive graphs
• Linial for lists
• Breaking the linear-memory barrier in \(\mathsf{MPC}\): fast \(\mathsf{MIS}\) on trees with strongly sublinear memory
• Distributed Minimum Vertex Coloring and Maximum Independent Set in Chordal Graphs
• Dynamic networks of finite state machines
• Distributed $(\Delta+1)$-Coloring via Ultrafast Graph Shattering
• Distributed backup placement in networks
• Distributed half-integral matching and beyond
• Exact distributed sampling
• Derandomizing local distributed algorithms under bandwidth restrictions
• A Fast Network-Decomposition Algorithm and Its Applications to Constant-Time Distributed Computation
• Local Algorithms for Bounded Degree Sparsifiers in Sparse Graphs
• (Delta+1) Coloring in the Congested Clique Model
• Distributed Local Approximation Algorithms for Maximum Matching in Graphs and Hypergraphs
• Loosely-Stabilizing Maximal Independent Set Algorithms with Unreliable Communications
• Distributed algorithms for the Lovász local lemma and graph coloring
• Distributed Graph Algorithms and their Complexity: An Introduction
• A Time Hierarchy Theorem for the LOCAL Model
• An Exponential Separation between Randomized and Deterministic Complexity in the LOCAL Model
• Improved distributed approximations for maximum independent set
• Time-optimal construction of overlay networks
• Nearly Optimal Local Broadcasting in the SINR Model with Feedback
• Distributed coloring of hypergraphs
• Symmetry breaking in the Congest model: time- and message-efficient algorithms for ruling sets
• Distributed half-integral matching and beyond
• Distributed Graph Coloring: Fundamentals and Recent Developments
• Distributed coloring and the local structure of unit-disk graphs
• Superfast coloring in CONGEST via efficient color sampling
• Superfast coloring in CONGEST via efficient color sampling
• Distributed MIS in O(log log n) Awake Complexity
• Distributed MIS with Low Energy and Time Complexities
• Distributed Symmetry Breaking on Power Graphs via Sparsification
• Optimal Message-Passing with Noisy Beeps
• Distributed graph problems through an automata-theoretic Lens
• Distributed minimum vertex coloring and maximum independent set in chordal graphs
• Improved distributed algorithms for coloring interval graphs with application to multicoloring trees
• Deterministic Subgraph Detection in Broadcast CONGEST.
• Can we locally compute sparse connected subgraphs?
• Distributed Lower Bounds for Ruling Sets
• Linear-in-\(\varDelta \) lower bounds in the LOCAL model
• Distributed graph problems through an automata-theoretic lens
• Title not available (Why is that?)
• What can be sampled locally?
• Node and edge averaged complexities of local graph problems
• Improved MPC algorithms for MIS, matching, and coloring on trees and beyond
• Title not available (Why is that?)
• Loosely-stabilizing maximal independent set algorithms with unreliable communications
• Title not available (Why is that?)
• Feedback from nature: simple randomised distributed algorithms for maximal independent set selection and greedy colouring
• Improved deterministic distributed matching via rounding
• Title not available (Why is that?)
• Network Decomposition and Distributed Derandomization (Invited Paper)
• Improved distributed \(\Delta\)-coloring
• Local computation algorithms for graphs of non-constant degrees
• Distributed Self-Stabilizing MIS with Few States and Weak Communication
• Improved dynamic colouring of sparse graphs
• Coloring fast without learning your neighbors' colors
• Local conflict coloring revisited: Linial for lists
• Luby's MIS algorithms made self-stabilizing

This page was built for publication: The locality of distributed symmetry breaking

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3177792)