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

(72)

• Exact distributed sampling
• Distributed half-integral matching and beyond
• Improved dynamic colouring of sparse graphs
• 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
• Coloring fast without learning your neighbors' colors
• Local conflict coloring revisited: Linial for lists
• Distributed coloring of hypergraphs
• Luby's MIS algorithms made self-stabilizing
• Brief announcement: An exponential separation between randomized and deterministic complexity in the LOCAL model
• Distributed half-integral matching and beyond
• Sublogarithmic distributed MIS algorithm for sparse graphs using Nash-Williams decomposition
• MIS on trees
• Deterministic subgraph detection in broadcast CONGEST
• Symmetry breaking depending on the chromatic number or the neighborhood growth
• Distributed graph problems through an automata-theoretic lens
• Improved deterministic distributed matching via rounding
• Symmetry breaking in the Congest model: time- and message-efficient algorithms for ruling sets
• Local coordination and symmetry breaking
• Distributed symmetry-breaking algorithms for congested cliques
• Can we locally compute sparse connected subgraphs?
• scientific article; zbMATH DE number 3967924 (Why is no real title available?)
• Improved distributed approximations for maximum independent set
• 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
• Linear-in-\(\varDelta \) lower bounds in the LOCAL model
• Distributed graph algorithms and their complexity: an introduction
• Distributed Lower Bounds for Ruling Sets
• scientific article; zbMATH DE number 7525452 (Why is no real title available?)
• scientific article; zbMATH DE number 5010828 (Why is no real title available?)
• Distributed backup placement in networks
• Loosely-Stabilizing Maximal Independent Set Algorithms with Unreliable Communications
• scientific article; zbMATH DE number 7559119 (Why is no real title available?)
• Network Decomposition and Distributed Derandomization (Invited Paper)
• Improved distributed \(\Delta\)-coloring
• Optimal bit complexity randomised distributed MIS and maximal matching algorithms for anonymous rings
• Efficient asynchronous distributed symmetry breaking
• The complexity of symmetry breaking in massive graphs
• Brief announcement: Symmetry breaking in the \textsc{Congest} model: time- and message-efficient algorithms for ruling sets
• Sublogarithmic distributed \textsc{MIS} algorithm for sparse graphs using Nash-Williams decomposition
• What can be sampled locally?
• Distributed \((\Delta+1)\)-coloring via ultrafast graph shattering
• Distributed graph problems through an automata-theoretic Lens
• Toward more localized local algorithms, removing assumptions concerning global knowledge
• Linial for lists
• Feedback from nature: simple randomised distributed algorithms for maximal independent set selection and greedy colouring
• A new technique for distributed symmetry breaking
• A fast network-decomposition algorithm and its applications to constant-time distributed computation (extended abstract)
• Local computation algorithms for graphs of non-constant degrees
• Local algorithms for bounded degree sparsifiers in sparse graphs
• \((\Delta+1)\) coloring in the congested clique model
• Super-fast 3-ruling sets
• Distributed minimum vertex coloring and maximum independent set in chordal graphs
• A time hierarchy theorem for the LOCAL model
• Distributed Minimum Vertex Coloring and Maximum Independent Set in Chordal Graphs
• Derandomizing local distributed algorithms under bandwidth restrictions
• Node and edge averaged complexities of local graph problems
• Breaking the linear-memory barrier in \(\mathsf{MPC}\): fast \(\mathsf{MIS}\) on trees with strongly sublinear memory
• Toward more localized local algorithms: removing assumptions concerning global knowledge
• Nearly optimal local broadcasting in the SINR model with feedback
• Distributed Graph Coloring: Fundamentals and Recent Developments
• When Algorithms for Maximal Independent Set and Maximal Matching Run in Sublinear Time
• Improved MPC algorithms for MIS, matching, and coloring on trees and beyond
• An exponential separation between randomized and deterministic complexity in the LOCAL model
• Distributed coloring and the local structure of unit-disk graphs
• Superfast coloring in CONGEST via efficient color sampling
• Improved distributed algorithms for coloring interval graphs with application to multicoloring trees
• Superfast coloring in CONGEST via efficient color sampling

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)