PaperlayerView exact revision on arXiv

Source-linked AI summary

The Locality of Distributed Symmetry Breaking

Leonid Barenboim, Michael Elkin, Seth Pettie, Johannes Schneider

arXiv:1202.1983v3cs.DC

TL;DR

The paper asks how efficiently randomized distributed algorithms can solve fundamental symmetry breaking problems despite the union bound barrier. It uses randomized preprocessing followed by deterministic algorithms on poly(log n)-size components, obtaining improved results for MIS, maximal matching, coloring, and related problems. The conclusions identify this reduction strategy as a central tool while noting constraints from deterministic Phase II algorithms and graph parameters.

  • Problem

    Randomized symmetry breaking remains difficult because local failure probabilities can accumulate across many components, creating a union bound barrier.

  • Method

    The algorithms reduce n-node instances to disjoint poly(log n)-size components, using randomized Phase I experiments followed by deterministic Phase II algorithms.

  • Results

    The paper reports first significant general-graph improvements over classic 1980s MIS and maximal matching algorithms, with maximal matching provably optimal across broad parameter ranges.

  • Takeaways & Limitations

    The two-phase reduction provides a way to confront the union bound barrier by limiting randomized failure accumulation before deterministic symmetry breaking.

  • Takeaways & Limitations

    The MIS construction requires careful handling of deterministic Phase II because reduced components retain O(log n)-bit identifiers rather than O(log t)-bit identifiers.

Abstract

from arXiv · show

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Δ+ 2^{O(\sqrt{\log\log n})})$ time, where $Δ$ 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 Δ\ll 2^{\sqrt{\log n}}$, and comes close to the $Ω(\log Δ)$ lower bound of Kuhn, Moscibroda, and Wattenhofer. - A maximal matching algorithm running in $O(\logΔ+ \log^4\log n)$ time. This is the first significant improvement to the 1986 algorithm of Israeli and Itai. Moreover, its dependence on $Δ$ 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.

1 Introduction

The paper studies randomized symmetry breaking in the LOCAL model, focusing on MIS, maximal matching, ruling sets, and vertex coloring. Its algorithms address the union bound barrier through reductions to smaller components and yield improved bounds, including for low-arboricity graphs.

  • 1 Introduction: Four fundamental LOCAL-model tasks are studied: MIS, maximal matching, ruling sets, and vertex coloring.The LOCAL model places processors on the input graph and gives nodes local knowledge plus parameter upper bounds.
  • 1.2 The Union Bound Barrier: The union bound barrier arises because local failures can accumulate across many nodes, forcing Θ(log n) time in a representative random experiment.Existing randomized algorithms may not guarantee independent per-node success; their guarantees can instead concern an Ω(1)-fraction of edges.
  • 1.2 The Union Bound Barrier: The two-phase strategy first uses randomized experiments to shrink surviving components, then applies deterministic symmetry breaking on poly(log n)-size instances.After Phase I, surviving components have size poly(log n) or poly(∆) log n with high probability.
  • 1.3 New Results: A randomized reduction handles large gaps between arboricity λ and maximum degree ∆ by reducing to degree λ · 2^{log^γ n} in O(log^{1−γ} n) time.This enables sublogarithmic-in-n algorithms when the reduced low-degree instances admit polylogarithmic-in-∆ algorithms.
  • 1.3 New Results: O(log^2 ∆ + 2^{O(√log log n)}) time yields the paper’s primary MIS result, within a log ∆ factor of the KMW lower bound.The result improves on the 1986 randomized MIS algorithms over a broad degree range.
  • 1.3 New Results: O(log ∆ + log^4 log n) time gives a maximal matching algorithm with provably optimal dependence on ∆, including an O(√log n)-time consequence for suitable arboricity.The algorithm uses O(1)-size messages and therefore works in CONGEST; further reductions yield optimality over broad arboricity ranges.
  • 1.3 New Results: O(log ∆ + 2^{O(√log log n)}) time achieves (∆ + 1)-coloring and implies O(∆)-coloring in 2^{O(√log log n)} time, independent of ∆.The dependence on ∆ is not known to be optimal because the KMW lower bound does not apply to vertex coloring.

2 Preliminaries

The preliminaries define graph, distance, sparsity, directed-graph, network-decomposition, and ruling-set notation used throughout. They also state the ruling-set construction and its coloring-based corollary, together with standard parameter assumptions.

  • Graph parameters: n, Δ, and λ denote graph size, maximum degree, and arboricity; arboricity is the minimum number of forests covering the edges.Arboricity roughly measures subgraph density, satisfies λ ≤ Δ, and can be much smaller than maximum degree.
  • Graph parameters: Degeneracy d(H) is within a factor of two of arboricity: λ(H) ≤ d(H) ≤ 2λ(H) − 1.
  • Graph notation: Directed graphs use indegree, outdegree, and total degree; a pseudoforest is a directed graph in which every node has outdegree at most 1.
  • Graph notation: For integers 1 ≤ a ≤ b, H[a,b] denotes the graph connecting pairs whose distance in H lies in [a,b], with H_a = H[a,a].
  • Network decompositions: A network decomposition partitions vertices into bounded-diameter clusters whose contracted adjacency graph receives a proper coloring; Panconesi–Srinivasan compute one deterministically in 2^O(√log n) time.
  • Ruling sets: An (α, β)-ruling set covers U within distance β while placing distinct selected nodes at least α apart; given a proper K-coloring, it is computed in (α−1)⌈log K⌉ time.A maximal independent set is a (2, 1)-ruling set.

3 A Maximal Independent Set Algorithm

The algorithm first computes a large independent set while isolating a small collection of bad nodes, then deterministically completes the set on compact components. This yields a high-probability MIS algorithm with near-polylogarithmic dependence on n and polylogarithmic dependence on Δ.

  • Computing an Almost Maximal Independent Set: O(log^2 Δ) randomized time computes a large, though not necessarily maximal, independent set using the IndependentSet algorithm.The algorithm generalizes Luby’s randomized experiment across log Δ scales, each containing O(log Δ) Luby steps.
  • Computing an Almost Maximal Independent Set: (1 − e^-1/2)e^-1 ≈ 0.145 is the per-iteration probability that a sufficiently high-degree surviving node is eliminated.Elimination occurs when a node in the inclusive neighborhood selects 1 and all of its neighbors select 0.
  • Computing an Almost Maximal Independent Set: 1 − n^-c/5+11 probability guarantees that the bad-node components are small and contain no large well-separated subset of bad nodes.Specifically, components in the induced surviving graph have fewer than tΔ^4 nodes, where t = log_Δ n.
  • The MIS Algorithm: O(log Δ · exp(O(√log log n))) deterministic time extends the partial independent set to an MIS using network decomposition.The completion processes low-radius clusters in parallel and ends with a maximal independent set on the graph.
  • The MIS Algorithm: O(log^2 Δ + exp(O(√log log n))) time computes an MIS with high probability using messages of size O(Δ^5 log Δ n).The bound combines the randomized IndependentSet phase with deterministic completion on reduced-size components.
  • The MIS Algorithm: Deterministic Phase II cannot be applied naively because the components retain O(log n)-bit original IDs rather than O(log t)-bit labels.A generic recoloring step supplies locally distinct shorter IDs before invoking the deterministic algorithm.

4 An Algorithm for Maximal Matching

The maximal matching algorithm combines randomized proposal-based stages with deterministic processing of small unmatched components. It achieves a high-probability running time of O(log Δ + log^4 log n), improved to O(log Δ + log^3 log n) for 2-colored bipartite graphs.

  • Match procedure: Each unmatched node proposes uniformly to an unmatched neighbor, accepted proposals form directed paths and cycles, and random labels select matching edges.The proposal structure is a directed pseudoforest; path endpoints receive fixed labels while other nodes use random bits.
  • Phase I: Phase I uses O(log Δ) stages and two Match calls per stage to supplement the current matching.The stages classify nodes by degree and maintain bounds on degrees and neighborhood degree sums.
  • Phase I: After Phase I, every unmatched component has fewer than (c ln n)^9 nodes with probability 1 − n^−Ω(c).This reduces the remaining work to independent small components that can be processed deterministically.
  • Analysis: Lemma 4.1 guarantees the stage invariants for all nodes with probability 1 − 2n^−c/660+1 before the final high-degree regime.The analysis bounds degree and neighborhood quantities across the randomized stages.
  • Phase II: Phase II applies a deterministic O(log^4 log n)-time maximal matching algorithm to each poly(log n)-size component.The degree is reduced to at most (c ln n)^2 before the final component-size reduction and deterministic completion.
  • Overall result: Theorem 4.4 computes a maximal matching in O(log Δ + log^4 log n) time with high probability using O(1)-size messages.For 2-colored bipartite graphs, the bound improves to O(log Δ + log^3 log n).

5 Vertex Coloring

The coloring algorithm repeatedly applies a constant-time randomized procedure to shrink the uncolored structure, then deterministically colors the remaining poly(log n)-size components. This yields a (deg +1)-coloring bound of O(log Δ + exp(O(√log log n))).

  • Phase I: After O(log Δ) applications, every node has at most O(log n) uncolored neighbors that each have Ω(log n) uncolored neighbors.The remaining problem can then be split into two subproblems of maximum degree O(log n).
  • Phase II: Phase II applies the deterministic Panconesi–Srinivasan algorithm to the resulting poly(log n)-size uncolored components.This deterministic step completes the coloring after randomized degree and component reduction.
  • Overall result: A (deg +1)-coloring can be computed in O(log Δ + exp(O(√log log n))) time using poly(log n)-length messages.The result applies to graphs of maximum degree Δ.
  • OneShotColoring: Each uncolored node chooses a random remaining color and keeps it when it has the highest ID among conflicting neighbors.The algorithm maintains a proper partial coloring with colors from each node’s degree-plus-one palette.
  • OneShotColoring: Each OneShotColoring call colors any fixed uncolored node with probability greater than 1/4.This constant success probability drives the iterative reduction of the uncolored graph.
  • Small components: After 5 log^(4/3) Δ̂ iterations, all uncolored components have fewer than tΔ̂^2 nodes with probability 1 − n^−c.The proof uses distance-3 sets whose coloring events are independent.

6 Ruling Sets

The ruling-set algorithm repeatedly sparsifies the graph so that distances to the final independent set remain bounded while induced degrees decrease. It computes a (2, β)-ruling set in O(β log^(1/(β−1)) Δ + exp(O(√log log n))) time with high probability.

  • Sparsification: The algorithm constructs nested sets V(G) = R_0 ⊇ R_1 ⊇ ··· ⊇ R_β through β − 1 sparsification calls followed by MIS.Each sparsification preserves proximity to the next set while reducing the relevant degree.
  • Correctness: Property (i) ensures every node is within distance β of R_β, while Property (iii) makes R_β an independent set.Together these properties imply that R_β is a (2, β)-ruling set.
  • Sparsification: Sparsify computes U in O(log_f Δ) time so every graph node is within distance one of U and each U-node has degree at most 2cf ln n with probability n^−c+2.The degree guarantee follows from independent sampling and a tail bound.
  • Overall result: Theorem 6.2 computes a (2, β)-ruling set in O(β log^(1/(β−1)) Δ + exp(O(√log log n))) time with high probability.The construction uses the paper’s MIS algorithm for the final step.
  • Consequences: For (2, 2)-ruling sets, the paper obtains an O(log^(2/3) Δ + exp(O(√log log n))) upper bound and identifies a separation from (2, 1)-ruling sets.The cited lower bound for (2, 1)-ruling sets is Ω(log Δ).

7 Bounded Arboricity Graphs

For bounded-arboricity graphs, the paper reduces high-degree structure to lower-degree instances and then applies symmetry-breaking algorithms. This gives sublinear-time bounds for maximal matching, MIS, coloring, and ruling sets, alongside matching lower bounds on trees.

  • Arboricity framework: Arboricity λ measures graph density through the minimum number of edge-disjoint forests covering the edges, and may be much smaller than maximum degree Δ.Most sparse graph classes have constant arboricity even when their maximum degree is unbounded.
  • Degree reduction: Theorem 7.2 reduces maximum degree to tλ in O(log_t Δ) time while preserving a matching or independent set with probability at least 1 − n^−c.The parameter t must satisfy t ≥ max{(5λ)^8, (4(c+1) ln n)^7}.
  • Degree reduction: The reduction repeatedly eliminates good high-degree nodes by random MIS selection or proposal-based matching, shrinking their number by a t^Ω(1) factor.For matching, each good high-degree node receives a proposal with failure probability smaller than o(1/n^c+1).
  • Maximal matching: Maximal matching can be computed in O(√log n) time for arboricity up to 2^O(√log n), and the tree lower bound is Ω(√log n).The lower bound also gives c log Δ + o(√log n) hardness for every Δ.
  • MIS and coloring: The bounded-arboricity results extend to MIS and coloring, including an O(log^(2/3) n) MIS reduction and fast (Δ + O(λ))-coloring bounds.The coloring theorem gives multiple time–palette tradeoffs parameterized by λ.
  • Ruling sets: A (2, O(log λ + √log n))-ruling set can be computed deterministically in O(log λ + √log n) time.This result combines the cited bounded-arboricity algorithms with deterministic ruling-set construction.
  • Lower bounds: The tree lower-bound argument does not establish a corresponding lower bound for MIS on trees because the relevant line graphs have girth 3.The paper notes this as a limitation of the indistinguishability argument.

8 MIS in Trees and High Girth Graphs

The TreeIndependentSet procedure reduces degrees across scales while isolating rare bad nodes into small components, enabling TreeMIS to complete an MIS efficiently on trees and high-girth graphs.

  • TreeIndependentSet: Each scale maintains that no remaining node has too many neighbors whose degree exceeds the scale threshold.The invariant holds deterministically; nodes violating it are marked bad and excluded temporarily.
  • TreeIndependentSet: A node above the scale threshold is eliminated with probability greater than 0.22 in one iteration, even when one neighbor’s behavior is fixed arbitrarily.This bound drives the degree-reduction analysis across iterations.
  • TreeIndependentSet: Nodes enter the bad set with probability at most 1/Δ^2 per scale, supporting the bound that every connected bad component remains small with high probability.The probability bound is independent of one neighbor’s behavior.
  • TreeIndependentSet: O(log Δ log log Δ) time suffices for TreeIndependentSet, which returns an independent set and bad-node set with small bad components with high probability.The bad-node components have size at most c log_Δ n with probability 1 − n^−c/2.
  • TreeMIS: TreeMIS partitions the remaining graph into low- and high-degree parts, solves each deterministically, and then handles the small bad components.The resulting runtime is O(log Δ log log Δ + log log n log log log n) with failure probability below n^−c/2.
  • High-girth graphs: O(log Δ log log n + exp(O(√log log n))) time yields an MIS on graphs of girth greater than 6 with high probability.The analysis does not work for graphs of girth 4.

9 Conclusions

The paper advances randomized symmetry breaking with new tools and argues that poly(log n)-component reductions confront a union-bound barrier. It leaves optimal sublogarithmic algorithms and improved coloring bounds open.

  • Contributions: The paper reports first significant general-graph improvements over classic 1980s MIS and maximal matching algorithms.It also identifies the union bound barrier and develops tools for confronting it.
  • Union bound barrier: All algorithms reduce an n-node instance to disjoint poly(log n)-node components, beyond which known randomized strategies fail to achieve (log n)^o(1) running time.The barrier arises because even small per-component failure probabilities accumulate under a union bound.
  • Union bound barrier: The paper conjectures that avoiding this barrier essentially requires deterministic algorithms, tethering randomized complexities to deterministic counterparts.Under this conjecture, removing the 2^O(√log log n) terms would require faster deterministic algorithms.
  • Open problems: Open questions include optimal O(min{log Δ, √log n} + log* n)-time MIS and maximal matching algorithms and any o(log n)-time algorithm for these problems.The complexity of (Δ + 1)-coloring also remains unresolved, with an O(log n) upper bound and Ω(log* n − log* Δ) lower bound stated.

A Concentration Inequalities

The appendix surveys concentration tools used to bound randomized failures and deviations, including Chernoff, negative-correlation, Janson, and Azuma–Hoeffding inequalities.

  • Concentration tools: Chernoff bounds control sums of independent identically distributed 0/1 variables.They provide concentration estimates for randomized events in the algorithms.
  • Concentration tools: Negative-correlation bounds extend concentration analysis to sums whose variables are independent or negatively correlated.The theorem applies to bounded random variables.
  • Concentration tools: Janson’s inequality addresses sums of dependent random variables through the fractional chromatic number of their dependency graph.The dependency graph encodes which variables may fail to be independent.
  • Concentration tools: Azuma–Hoeffding bounds deviations of martingales with bounded differences.The appendix also derives a corollary for sums whose conditional expectations are exposed sequentially.
Loading 1202.1983v3…