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 (72)

• Symmetry breaking depending on the chromatic number or the neighborhood growth
• 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
• Distributed backup placement in networks
• Nearly optimal local broadcasting in the SINR model with feedback
• Distributed half-integral matching and beyond
• Derandomizing local distributed algorithms under bandwidth restrictions
• MIS on trees
• A new technique for distributed symmetry breaking
• Distributed symmetry-breaking algorithms for congested cliques
• Loosely-Stabilizing Maximal Independent Set Algorithms with Unreliable Communications
• Sublogarithmic distributed \textsc{MIS} algorithm for sparse graphs using Nash-Williams decomposition
• Toward more localized local algorithms, removing assumptions concerning global knowledge
• Distributed algorithms for the Lovász local lemma and graph coloring
• Deterministic subgraph detection in broadcast CONGEST
• Improved distributed approximations for maximum independent set
• When Algorithms for Maximal Independent Set and Maximal Matching Run in Sublinear Time
• Distributed \((\Delta+1)\)-coloring via ultrafast graph shattering
• Local coordination and symmetry breaking
• Symmetry breaking in the Congest model: time- and message-efficient algorithms for ruling sets
• 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 graph problems through an automata-theoretic Lens
• Optimal bit complexity randomised distributed MIS and maximal matching algorithms for anonymous rings
• Distributed minimum vertex coloring and maximum independent set in chordal graphs
• Improved distributed algorithms for coloring interval graphs with application to multicoloring trees
• Distributed local approximation algorithms for maximum matching in graphs and hypergraphs
• Local algorithms for bounded degree sparsifiers in sparse graphs
• \((\Delta+1)\) coloring in the congested clique model
• Can we locally compute sparse connected subgraphs?
• Distributed graph algorithms and their complexity: an introduction
• Efficient asynchronous distributed symmetry breaking
• Distributed Lower Bounds for Ruling Sets
• Linear-in-\(\varDelta \) lower bounds in the LOCAL model
• Super-fast 3-ruling sets
• Distributed graph problems through an automata-theoretic lens
• Title not available (Why is that?)
• What can be sampled locally?
• A time hierarchy theorem for the LOCAL model
• 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?)
• A fast network-decomposition algorithm and its applications to constant-time distributed computation (extended abstract)
• Toward more localized local algorithms: removing assumptions concerning global knowledge
• Brief announcement: An exponential separation between randomized and deterministic complexity in the LOCAL model
• 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
• An exponential separation between randomized and deterministic complexity in the LOCAL model
• Improved deterministic distributed matching via rounding
• Title not available (Why is that?)
• Network Decomposition and Distributed Derandomization (Invited Paper)
• Improved distributed \(\Delta\)-coloring
• Brief announcement: Symmetry breaking in the \textsc{Congest} model: time- and message-efficient algorithms for ruling sets
• Local computation algorithms for graphs of non-constant degrees
• Exact distributed sampling
• Distributed coloring of hypergraphs
• Distributed half-integral matching and beyond
• 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
• Distributed Self-Stabilizing MIS with Few States and Weak Communication
• Optimal Message-Passing with Noisy Beeps
• 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)