PaperlayerView exact revision on arXiv

Source-linked AI summary

On Derandomizing Local Distributed Algorithms

Mohsen Ghaffari, David G. Harris, Fabian Kuhn

arXiv:1711.02194v4cs.DScs.DC

TL;DR

The paper tackles the longstanding gap between randomized and deterministic local distributed algorithms. It introduces a generic derandomization recipe and applies it to hypergraph matching and the Lovász Local Lemma, while also identifying conditional barriers to derandomization.

  • Problem

    The central problem is the longstanding gap between randomized and deterministic LOCAL algorithms, including the open challenge of developing general derandomization techniques.

  • Method

    The paper derandomizes randomized LOCAL algorithms through deterministic SLOCAL algorithms and network-decomposition-based transformations, and develops improved distributed LLL algorithms.

  • Results

    The approach improves deterministic hypergraph maximal matching and derived edge-coloring, maximum-matching approximation, and low-out-degree orientation algorithms, while improved LLL algorithms support k-SAT and defective coloring.

  • Takeaways & Limitations

    The results provide a general derandomization recipe, stronger distributed algorithms for several problems, and conditional evidence that some derandomization tasks are at least as hard as MIS.

  • Takeaways & Limitations

    The derandomization method incurs network-decomposition overhead, and the distributed LLL algorithm has a pLLL criterion and a degree restriction Δ≤2^O(√log n).

Abstract

from arXiv · show

The gap between the known randomized and deterministic local distributed algorithms underlies arguably the most fundamental and central open question in distributed graph algorithms. In this paper, we develop a generic and clean recipe for derandomizing LOCAL algorithms. We also exhibit how this simple recipe leads to significant improvements on a number of problem. Two main results are: - An improved distributed hypergraph maximal matching algorithm, improving on Fischer, Ghaffari, and Kuhn [FOCS'17], and giving improved algorithms for edge-coloring, maximum matching approximation, and low out-degree edge orientation. The first gives an improved algorithm for Open Problem 11.4 of the book of Barenboim and Elkin, and the last gives the first positive resolution of their Open Problem 11.10. - An improved distributed algorithm for the Lovász Local Lemma, which gets closer to a conjecture of Chang and Pettie [FOCS'17], and moreover leads to improved distributed algorithms for problems such as defective coloring and $k$-SAT.

1 Introduction and Related Work

The paper addresses the central gap between randomized and deterministic LOCAL algorithms with a generic derandomization recipe, then applies it to matching, coloring, orientation, and the Lovász Local Lemma.

  • Derandomization: The paper gives a generic derandomization recipe that transforms any r-round randomized LOCAL algorithm for a locally checkable problem into deterministic SLOCAL locality O(r), followed by deterministic LOCAL algorithms.The LOCAL complexity is Δ^O(r) + O(r log*n), or r · 2^O(√log n) using network decompositions.
  • Hypergraph maximal matching: The improved hypergraph maximal matching algorithm runs in O(r^2 log(nΔ) log n log^4 Δ) rounds and is efficient for hypergraphs with rank r = polylog n.This improves the prior rank dependence, which was efficient essentially only for constant-rank hypergraphs.
  • Applications: The matching result yields deterministic algorithms for (2Δ−1)-list-edge-coloring, (1−ε)-approximate maximum matching, and arboricity-λ orientation with maximum out-degree at most (1+ε)λ.Their round complexities are O(log^4 Δ log^2 n), O(log^2 n log^5 Δ/ε^9), and O(log^10 n log^5 Δ/ε^9), respectively.
  • Applications: The edge-coloring algorithm improves on the O(log^8 n) algorithm of Fischer et al., while the orientation result gives the first positive resolution of Open Problem 11.10.The stronger maximum-matching approximation is critical for these consequences.
  • Lovász Local Lemma: The paper develops improved distributed LLL algorithms that reduce degree dependence, approach the Chang–Pettie conjecture, and support applications to k-SAT and defective coloring.The results include a randomized k-SAT algorithm in 2^O(√log log m) rounds under the stated intersection bound and an h-defective k-coloring algorithm in 2^O(√log log n) rounds.

2 Model and Definitions

The paper formalizes deterministic, randomized, and sequential distributed-computing models, together with graph decompositions and complexity classes used to compare them. It also distinguishes Monte Carlo and Las Vegas guarantees and relates their classes under local checkability.

  • LOCAL model: The LOCAL model uses synchronous rounds on an n-node graph, with unique identifiers and unrestricted messages exchanged between neighboring nodes.Each node initially knows its neighbors and ultimately outputs its own part of the solution.
  • Complexity classes: The paper defines LOCAL, SLOCAL, RLOCAL, and ZLOCAL classes by deterministic or randomized algorithms in the corresponding models, and introduces their polylogarithmic-time variants.For locally checkable problems, randomized LOCAL algorithms can be converted into zero-error algorithms with an added local-checking overhead.
  • SLOCAL model: SLOCAL algorithms process nodes sequentially, allowing each node to inspect an r-hop neighborhood and previously stored information; r is the locality.The processing order may be adversarially chosen.
  • Randomized classes: Monte Carlo algorithms have fixed running time and succeed with probability greater than 1 − 1/n, whereas the paper’s Las Vegas definition uses node flags with total expected failure below 1.The paper notes that this Las Vegas definition is equivalent to more standard notions up to polylogarithmic factors.
  • Network decomposition: Network decompositions partition vertices into colored classes whose induced components have bounded diameter, enabling distributed simulation of SLOCAL algorithms.The paper uses decompositions as a central graph structure for connecting sequential and distributed models.

3 Basic Derandomization of Local Algorithms

The basic derandomization method converts suitable randomized LOCAL algorithms into deterministic SLOCAL algorithms by fixing random choices through conditional expectation. Network decompositions then simulate these sequential algorithms in the distributed LOCAL model, yielding class and complexity consequences.

  • Scope and overhead: The approach applies only to Las Vegas algorithms, although the paper notes that most Monte Carlo graph algorithms, including locally checkable problems, can be converted to Las Vegas algorithms.The deterministic LOCAL simulation can nevertheless incur a substantial network-decomposition overhead.
  • Derandomization: A zero-error r-round LOCAL algorithm can be derandomized into a deterministic SLOCAL algorithm of locality 2r by assigning node randomness so the algorithm succeeds.The construction processes nodes sequentially and fixes each private random string while preserving a conditional-expectation invariant.
  • Derandomization: Conditional expectation works because each node’s failure flag depends only on its r-hop neighborhood, so fixing a node’s randomness requires information from its 2r-neighborhood.The locally checkable assumption is critical for efficiently derandomizing the algorithm.
  • Distributed simulation: A network decomposition of G^r simulates an SLOCAL(r)-algorithm as a deterministic LOCAL algorithm, processing differently clustered nodes of the same color independently.The resulting round complexity depends on the decomposition parameters and the SLOCAL locality.
  • Class consequences: The framework gives ZLOCAL(r) ⊆ SLOCAL(4r) and establishes P-ZLOCAL = P-SLOCAL.The 4r locality composes the derandomization stage with execution of the resulting deterministic algorithm.

4 Deterministic Hypergraph Maximal Matching

The section develops deterministic hypergraph maximal matching through degree splitting and a staged matching construction. This yields a maximal matching algorithm and supports applications including edge-coloring and approximate matching.

  • The hypergraph model communicates along shared hyperedges, and a matching is a maximal set of pairwise disjoint hyperedges.This formulation enables reductions from graph problems to hypergraph maximal matching.
  • Degree splitting colors hyperedges red and blue so every sufficiently high-degree vertex receives nearly balanced portions of both colors.The deterministic splitting algorithm runs in O(r log(n∆)/ε^2) rounds.
  • The staged construction partitions edges by their intersection size with U and combines maximal matchings from larger to smaller classes.Each suffix of the constructed matchings is maximal for the corresponding suffix of edge classes.
  • The construction repeatedly reduces degree through splitting, then applies a matching procedure that covers an Ω(1/r) fraction of high-degree vertices.After O(log r) staged matchings, the final low-degree instance is handled by Lemma 4.3.
  • A maximal matching of an n-node hypergraph with maximum degree ∆ and rank r can be computed deterministically in O(r^2 log(n∆) log n log^4 ∆) LOCAL rounds.This is the section's main algorithmic guarantee.
  • 4.1 Implications on Edge-Coloring, Maximum Matching, and Low-Degree Orientation: Known reductions use the maximal-matching algorithm to obtain deterministic algorithms for edge-coloring, approximate maximum matching, and low out-degree orientation.For (2∆−1)-list-edge-coloring, the stated complexity is O(log^2 n log^4 ∆); the matching-approximation construction has total complexity O(log^10 n log^5 ∆/ε^9).

5 The Lov´asz Local Lemma

The paper develops distributed LLL algorithms through shattering, bootstrapping, and derandomization, improving runtimes and extending applicability across degree regimes.

  • 5.1 Previous Distributed LLL Algorithms: The LLL provides a general framework for avoiding low-probability, weakly dependent bad events, but its original existential guarantee does not directly yield efficient algorithms.Distributed LLL algorithms therefore seek constructive procedures under criteria such as epd^(1+ε) ≤ 1.
  • 5.2 Techniques: Graph shattering separates randomized partial progress from deterministic solution of small residual components, while bootstrapping amplifies slack across successive LLL instances.These techniques organize the paper’s distributed constructions and their runtime analyses.
  • 5.4 The LLL for Low-Degree Graphs: The paper’s low-degree algorithm combines prior LLL routines and bootstrapping to obtain a runtime that makes constant progress from log n toward log log n for constant d.The paper describes this as log^(1+ε) n for a constant ε > 0, while noting the notation is informal.
  • 5.6 Derandomizing the LLL: The generic derandomization framework converts randomized LOCAL algorithms for locally checkable problems into deterministic SLOCAL algorithms, then into deterministic LOCAL algorithms.The deterministic LLL version increases the dependence on n by an exponential factor relative to the randomized algorithm.

6 The LLL for High-Degree Graphs

For high-degree graphs, the paper replaces degree-dependent LLL methods with a fragility-based algorithm that supports broad applications, including defective coloring and bounded-overlap k-SAT.

  • 6 The LLL for High-Degree Graphs: The high-degree algorithm avoids dependence on Δ and runs in 2^O(√log log n) rounds under a fragility condition.Theorem 1.8 requires f(B) ≤ e^(-10d^(-12)) and produces a satisfying assignment with high probability.
  • 6.2 Applications: Compared with prior work, the approach is more generic and also supports applications such as k-SAT that are not directly covered by the earlier framework.The paper contrasts this with problem-specific recoloring techniques used in prior defective-coloring algorithms.
  • 6 The LLL for High-Degree Graphs: The algorithm identifies dangerous bad events, forms the neighboring residual instance, fixes non-unknown variables, and applies a deterministic LLL procedure to each residual component.This is the paper’s generic high-degree LLL procedure based on dangerous events.
  • 6.1 Examples of Events with Bounded Fragility: Fragility measures the probability that an event remains true after independently combining two assignments coordinatewise, and bounds how likely the event is to become dangerous.The paper proves P(B is q-dangerous) ≤ f(B)/q.
  • 6 The LLL for High-Degree Graphs: If every bad event has sufficiently small fragility, Algorithm 2 terminates with a satisfying assignment in 2^O(√log log n) rounds with high probability.The guarantee is stated independently of the maximum degree.
  • 6.2 Applications: The framework yields a 2^O(√log log m)-round algorithm for k-SAT with bounded clause overlap and a 2^O(√log log n)-round h-defective coloring algorithm.The defective-coloring result gives h = O(log Δ) and k = Δ^O(1).

7 Obstacles to Derandomizing Local Algorithms

The section identifies limits and separations in derandomizing local algorithms, then develops sinkless-orientation results and several SLOCAL-completeness consequences.

  • Sinkless orientation: Theorem 7.1 gives deterministic SLOCAL locality Ω(log_d log n) and randomized SLOCAL locality Ω(log_d log log n) for sinkless orientation on d-regular graphs.These lower bounds follow from known deterministic and randomized LOCAL lower bounds, respectively.
  • Sinkless orientation: A deterministic SLOCAL algorithm solves sinkless orientation in O(log log n) locality on graphs with minimum degree at least 3.The result combines randomized LOCAL sinkless orientation with derandomization for locally checkable problems.
  • Sinkless orientation: An RSLOCAL algorithm achieves O(log log log n) locality for sinkless orientation on graphs with minimum degree at least 3.The construction uses two passes: random marking and deterministic SLOCAL processing of the small bad-node components.
  • Limits of derandomization: Local checkability is essential: a cycle-marking problem has a zero-round randomized algorithm, whereas every deterministic SLOCAL algorithm requires Ω(√n) locality.The proposition demonstrates that efficient derandomization does not extend to arbitrary distributed problems.
  • Complete problems: The paper proves P-SLOCAL-completeness for polylogarithmic distributed set cover, polylog-factor MDS approximation, maximal independent star sets, and sparse neighborhood covers.Sparse neighborhood covers and (O(log n), O(log n))-network decompositions are equivalent up to polylogarithmic factors in the LOCAL model.

A Residual problems and shattering

The shattering framework randomly satisfies most vertices, isolates a sparse residual graph with small components, and then solves the residual problem deterministically or with SLOCAL procedures.

  • Residual problems and shattering: Shattering uses a random phase to satisfy most vertices, followed by deterministic solution of the small connected components induced by unsatisfied vertices.The residual set R is sparse, and its components are handled separately.
  • Backbones: A c-backbone is an independent set in G^c whose induced G^3c subgraph is connected.Backbone-freeness is used to control the size of residual components.
  • Backbones: The backbone argument shows that connected residual components can be reduced to connected independent structures while preserving a lower bound on their size.Proposition A.4 supplies a backbone at least as large as an independent connected witness set.
  • Residual bounds: With high probability, the random residual set is c,m-backbone-free for m = Ω(log n), and each residual component containing v has probability at most (eΔ)^(-w/(Δ+1)^c+1) of exceeding size w.These bounds follow by counting possible backbones and bounding their survival probabilities.
  • Residual decomposition: With high probability, the residual graph admits an (O(log log n), O((log log n)^2))-network decomposition in r·2^{O(√log log n)} rounds.The construction uses a ruling set, a contracted graph on its centers, and deterministic decomposition of logarithmic-size components.
  • Residual problems: If the residual problem has an SLOCAL(r) procedure, shattering yields a high-probability LOCAL solution with residual components bounded by O(Δ^{2c} log n).The paper also identifies SLOCAL algorithms as a source for second-phase procedures, including Las Vegas algorithms.
Loading 1711.02194v4…