The locality of distributed symmetry breaking

DOI10.1145/2903137MaRDI QIDQ3177792zbMATH OpenOpenAlexFDO

Authors

Publication date 2 August 2018

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

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

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)

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.

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

Cited in

(90)

• Symmetry breaking depending on the chromatic number or the neighborhood growth
• Brief announcement: Symmetry breaking in the \textsc{Congest} model: time- and message-efficient algorithms for ruling sets
• Sublogarithmic distributed MIS algorithm for sparse graphs using Nash-Williams decomposition
• Linial for lists
• Breaking the linear-memory barrier in \(\mathsf{MPC}\): fast \(\mathsf{MIS}\) on trees with strongly sublinear memory
• The complexity of symmetry breaking in massive graphs
• Distributed Minimum Vertex Coloring and Maximum Independent Set in Chordal Graphs
• Sampling and output estimation in distributed algorithms and LCAs
• Brief announcement: Massively parallel ruling set made deterministic
• Brief announcement: Simpler and more general distributed coloring based on simple list defective coloring algorithms
• (+1) vertex coloring in O(n) communication
• Distributed backup placement in networks
• Nearly optimal local broadcasting in the SINR model with feedback
• Distributed half-integral matching and beyond
• Exact distributed sampling
• Derandomizing local distributed algorithms under bandwidth restrictions
• MIS on trees
• Distributed symmetry-breaking algorithms for congested cliques
• A new technique for distributed symmetry breaking
• ( + 1) vertex coloring in O(n) communication
• Sublogarithmic distributed \textsc{MIS} algorithm for sparse graphs using Nash-Williams decomposition
• Toward more localized local algorithms, removing assumptions concerning global knowledge
• Loosely-Stabilizing Maximal Independent Set Algorithms with Unreliable Communications
• Distributed algorithms for the Lovász local lemma and graph coloring
• Deterministic subgraph detection in broadcast CONGEST
• Exponentially faster massively parallel maximal matching
• Improved distributed approximations for maximum independent set
• When Algorithms for Maximal Independent Set and Maximal Matching Run in Sublinear Time
• Sample-and-gather: fast ruling set algorithms in the low-memory MPC model
• Narrowing the \textsf{LOCAL-CONGEST} gaps in sparse networks via expander decompositions
• Distributed MIS in O( n) awake complexity
• Distributed (+1)-coloring via ultrafast graph shattering
• Distributed coloring of hypergraphs
• Local coordination and symmetry breaking
• Graph coloring via degeneracy in streaming and other space-conscious models
• 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
• Locally computing edge orientations
• 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
• 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
• Optimal bit complexity randomised distributed MIS and maximal matching algorithms for anonymous rings
• Towards distributed two-stage stochastic optimization
• 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
• Can we locally compute sparse connected subgraphs?
• Local algorithms for bounded degree sparsifiers in sparse graphs
• \((\Delta+1)\) coloring in the congested clique model
• Efficient asynchronous distributed symmetry breaking
• Distributed graph algorithms and their complexity: an introduction
• Linear-in- lower bounds in the LOCAL model
• Distributed Lower Bounds for Ruling Sets
• Super-fast 3-ruling sets
• Improved dynamic colouring of sparse graphs
• Distributed graph problems through an automata-theoretic lens
• scientific article; zbMATH DE number 7559119 (Why is no real title available?)
• The message complexity of distributed graph optimization
• The distributed complexity of locally checkable labeling problems beyond paths and trees
• Mobile agents on chordal graphs: maximum independent set and beyond
• What can be sampled locally?
• Distributed symmetry breaking on power graphs via sparsification
• Optimal message-passing with noisy beeps
• A time hierarchy theorem for the LOCAL model
• Node and edge averaged complexities of local graph problems
• Coloring fast without learning your neighbors' colors
• Local conflict coloring revisited: Linial for lists
• Improved MPC algorithms for MIS, matching, and coloring on trees and beyond
• Luby's MIS algorithms made self-stabilizing
• scientific article; zbMATH DE number 3967924 (Why is no real title available?)
• Toward more localized local algorithms: removing assumptions concerning global knowledge
• A fast network-decomposition algorithm and its applications to constant-time distributed computation (extended abstract)
• Loosely-stabilizing maximal independent set algorithms with unreliable communications
• Feedback from nature: simple randomised distributed algorithms for maximal independent set selection and greedy colouring
• Brief announcement: An exponential separation between randomized and deterministic complexity in the LOCAL model
• Locally-iterative (+1)-coloring in sublinear (in ) rounds
• scientific article; zbMATH DE number 7525452 (Why is no real title available?)
• Improved deterministic distributed matching via rounding
• An exponential separation between randomized and deterministic complexity in the LOCAL model
• Improved distributed \(\Delta\)-coloring
• scientific article; zbMATH DE number 5010828 (Why is no real title available?)
• Network Decomposition and Distributed Derandomization (Invited Paper)
• Local computation algorithms for graphs of non-constant degrees

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)