PaperlayerView exact revision on arXiv

Source-linked AI summary

Polylogarithmic-Time Deterministic Network Decomposition and Distributed Derandomization

Václav Rozhoň, Mohsen Ghaffari

arXiv:1907.10937v2cs.DScs.DCcs.DMmath.CO

TL;DR

The paper addresses the longstanding gap between randomized and deterministic polylogarithmic-time distributed algorithms. It presents a deterministic network-decomposition algorithm and uses it to obtain faster algorithms and a general distributed derandomization result.

  • Problem

    Prior work left a significant gap between randomized and deterministic distributed algorithms, including open questions for problems such as MIS and (Δ+1)-coloring.

  • Method

    The paper constructs network decompositions through a phased clustering process that progressively aligns neighboring cluster identifiers by identifier bits.

  • Results

    The paper presents a polylogarithmic-time deterministic distributed algorithm for network decomposition that leads to faster deterministic and randomized algorithms for many distributed graph problems.

  • Takeaways & Limitations

    The network-decomposition result resolves several central open problems and provides a general and efficient basis for distributed derandomization.

  • Takeaways & Limitations

    The overview states that the two network-decomposition approaches cannot go below a 2^{O(√(log n log log n))} complexity.

Abstract

from arXiv · show

We present a simple polylogarithmic-time deterministic distributed algorithm for network decomposition. This improves on a celebrated $2^{O(\sqrt{\log n})}$-time algorithm of Panconesi and Srinivasan [STOC'92] and settles a central and long-standing question in distributed graph algorithms. It also leads to the first polylogarithmic-time deterministic distributed algorithms for numerous other problems, hence resolving several well-known and decades-old open problems, including Linial's question about the deterministic complexity of maximal independent set [FOCS'87; SICOMP'92]---which had been called the most outstanding problem in the area. The main implication is a more general distributed derandomization theorem: Put together with the results of Ghaffari, Kuhn, and Maus [STOC'17] and Ghaffari, Harris, and Kuhn [FOCS'18], our network decomposition implies that $$\mathsf{P}\textit{-}\mathsf{RLOCAL} = \mathsf{P}\textit{-}\mathsf{LOCAL}.$$ That is, for any problem whose solution can be checked deterministically in polylogarithmic-time, any polylogarithmic-time randomized algorithm can be derandomized to a polylogarithmic-time deterministic algorithm. Informally, for the standard first-order interpretation of efficiency as polylogarithmic-time, distributed algorithms do not need randomness for efficiency. By known connections, our result leads also to substantially faster randomized distributed algorithms for a number of well-studied problems including $(Δ+1)$-coloring, maximal independent set, and Lovász Local Lemma, as well as massively parallel algorithms for $(Δ+1)$-coloring.

1 Introduction

The paper introduces a polylogarithmic-time deterministic network decomposition and uses it to establish a broad distributed derandomization result, addressing a major gap between randomized and deterministic algorithms.

  • Background and State of the Art: Before this work, distributed graph algorithms had a significant, often nearly-exponential, gap between randomized and deterministic round complexities.The gap was a foundational long-standing question, exemplified by Linial’s question about deterministic polylogarithmic-time MIS.
  • Our Contribution: P-LOCAL = P-RLOCAL for locally checkable problems solvable in poly(log n) rounds, provided the randomized algorithm succeeds with probability 1 − 1/n.The theorem combines the new network decomposition with earlier derandomization frameworks.
  • Implications: The result supplies the first polylogarithmic-time deterministic algorithms for several previously open problems, including MIS, (Δ + 1)-coloring, Lovász Local Lemma, and defective coloring.Known connections also yield faster randomized algorithms for several problems, including poly(log log n)-time randomized (Δ + 1)-coloring in the cited setting.
  • Our Contribution: The paper develops a polylogarithmic-time deterministic algorithm for network decomposition, improving on the prior 2^O(√(log n))-round deterministic bound.The decomposition partitions vertices into O(log n) color classes whose induced components have diameter O(log n).
  • An Overview of Our Network Decomposition Method: The clustering method uses O(log n) identifier-bit phases that release red clusters toward blue clusters while bounding cluster growth.After all phases, each surviving connected component becomes one cluster, at most half the vertices have died, and cluster radii remain poly(log n).
  • Scope and Limitations: The paper’s derandomization scope is restricted to locally checkable problems; arbitrary problems are excluded because randomized and deterministic complexities can differ substantially.The related-work discussion also records author-identified limitations in another proposed splitting result, including an incorrect conditional-probability inequality.

2 The Network Decomposition Algorithm

The paper develops a deterministic polylogarithmic-round network decomposition, first obtaining weak diameter and then transforming it into strong diameter. The construction iteratively clusters vertices using identifier bits, Steiner trees, and repeated removal of clustered vertices.

  • Weak-Diameter Network Decomposition: O(log^7 n) rounds compute O(log n) colors with weak-diameter O(log^3 n).Each cluster also has a radius-O(log^3 n) Steiner tree, and every graph edge belongs to O(log^2 n) such trees.
  • Weak-Diameter Network Decomposition: The initial algorithm repeatedly extracts a non-adjacent clustered subset containing at least half of the currently living vertices.Applying the extraction for O(log n) iterations yields O(log n) color classes covering all vertices.
  • Weak-Diameter Network Decomposition: O(log^6 n) rounds suffice to find the half-sized subset, whose clusters have weak diameter O(log^3 n) and supporting Steiner trees.The trees have radius O(log^3 n), with every graph edge appearing in O(log n) trees for that extraction.
  • Weak-Diameter Network Decomposition: Identifier-bit phases maintain separation and bounded tree growth while red clusters propose merges and blue clusters accept or eliminate them.A stopped blue cluster has no edge to a red node, while its Steiner-tree radius grows by at most one per step.
  • CONGEST Model: O(log^8 n) CONGEST rounds implement the decomposition, using Steiner trees for simultaneous broadcasts and convergecasts.More generally, graph-power input G_k is handled in O(k log^8 n · min(k, log^2 n)) rounds with O(k · log^3 n) weak diameter.
  • Strong-Diameter Network Decomposition: O(log^8 n) LOCAL rounds produce O(log n) colors whose clusters have strong diameter O(log n).The transformation applies the weak-diameter construction to a graph connecting vertices within distance 10 log n, then simulates the sequential construction efficiently.

3 Implications and Applications

The efficient deterministic decomposition has broad implications for distributed graph algorithms. It supports derandomization, improved algorithms for several graph problems, and improvements in massively parallel computation.

  • The decomposition leads to a general efficient distributed derandomization theorem.
  • It yields better deterministic and randomized distributed algorithms for a range of well-studied problems.
  • It also provides improvements in massively parallel computation, including MapReduce algorithms.

3.1 Maximal Independent Set and Coloring

The paper uses efficient network decomposition to obtain polylogarithmic deterministic algorithms for MIS and coloring, while also improving randomized and massively parallel algorithms.

  • Maximal Independent Set: Poly(log n)-round deterministic MIS in the LOCAL model resolves Linial’s long-standing open question.The construction computes an O(log n)-color network decomposition with O(log^3 n)-diameter clusters in O(log^7 n) rounds, then processes clusters color by color.
  • Maximal Independent Set: O(log Δ)+poly(log log n) rounds yields a randomized LOCAL-model MIS algorithm with probability at least 1−1/poly(n).The improvement comes from plugging the deterministic MIS algorithm into a shattering framework.
  • Coloring: O(log^7 n) rounds suffice for deterministic (Δ+1)-vertex coloring in the LOCAL model, including its list-coloring generalization.The method applies the standard network-decomposition approach used for MIS.
  • Coloring: poly(log log n) rounds improve randomized LOCAL-model (Δ+1)-coloring, with success probability at least 1−1/poly(n).The algorithm combines a randomized shattering phase with deterministic list-coloring on the remaining small components.
  • Coloring: A deterministic LOCAL algorithm also computes a (2+o(1))a-coloring for graphs of arboricity at most a in poly(log n) rounds.This is obtained using the deterministic list-coloring result together with an arboricity-dependent method.
  • Coloring: O(log log log n) rounds give a high-probability randomized MPC algorithm for (Δ+1)-coloring with strongly sublinear memory per machine.Each machine has memory n^α for any constant α<1.

3.2 Derandomization via Network Decomposition

The paper combines its network decomposition with conditional-expectation derandomization to convert efficient randomized algorithms for locally checkable problems into efficient deterministic ones.

  • Motivation: The derandomization result addresses the open problem of a general efficient derandomization technique for distributed message passing.Several locally checkable problems had poly(log n)-round randomized algorithms but no known deterministic algorithms of comparable complexity.
  • Guarantee: The theorem establishes P-RLOCAL = P-LOCAL for locally checkable problems solvable and checkable in poly(log n) rounds.P-LOCAL and P-RLOCAL refer respectively to deterministic and randomized polylogarithmic-time solvability in the LOCAL model.
  • Method: A deterministic algorithm processes network-decomposition colors sequentially and fixes each cluster’s node randomness without increasing conditional expectation.Clusters of the same color are sufficiently separated to operate in parallel.
  • Guarantee: For an r(n)-round randomized algorithm and a t(n)-round deterministic checker, the resulting deterministic algorithm runs in (r(n)+t(n))·poly(log n) rounds.The method applies when both r(n) and t(n) are poly(log n).

3.3 Other Implications (Deterministic & Randomized)

The section presents deterministic and randomized improvements for the Lovász Local Lemma, locally checkable problems, optimization, coloring, arboricity, and CONGEST-model graph primitives.

  • Lovász Local Lemma: poly(log n) rounds yield a deterministic distributed Lovász Local Lemma algorithm when epd ≤1−δ.The guarantee allows constant δ>0 or slightly sub-constant δ>1/poly(log n).
  • Lovász Local Lemma: poly(log log n) rounds yield randomized LLL algorithms in constant-degree graphs under the condition Cpd^8≤1.The algorithm has complexity O(d^2)+poly(log log n) rounds.
  • Sublogarithmic Complexity: o(log n)-round randomized locally checkable problems in constant-degree graphs can be reduced to poly(log log n) rounds.Thus their randomized complexity is either Ω(log n) and above or poly(log log n) and below.
  • Packing/Covering Integer Linear Programs: poly(log n/ε) rounds suffice for deterministic 1+ε approximation of any covering or packing integer linear program.Examples include maximum independent set and minimum dominating set approximations.
  • Coloring and Arboricity: poly(log n) rounds yield deterministic O(Δ/p)-defective O(p)-coloring and near-optimal arboricity orientations or decompositions.The arboricity result gives maximum outdegree at most (1+o(1))a and distinguishes forests from pseudo-forests according to a.

A Comparison of previous work with Theorem 1.2

Earlier network decomposition approaches had nearly-exponential round complexity and appeared unable to reach polylogarithmic complexity, whereas Theorem 2.3 achieves a poly(log n)-round complexity.

  • Prior Work: Before this work, Panconesi and Srinivasan provided the state-of-the-art deterministic network decomposition algorithm with 2^{O(√(log n log log n))} rounds.
  • Comparison: The approaches of Awerbuch et al. and the newer alternative both appeared stuck at 2^{O(√(log n log log n))} rounds.
  • Comparison: Theorem 2.3 reaches poly(log n) round complexity, unlike the earlier approaches that fall short for the same reasons.

A.1 Recap on Ruling sets

A ruling set separates selected vertices while keeping every graph vertex close to one selected vertex; the paper uses this weaker alternative to MIS and constructs it deterministically in O(log n) rounds.

  • Motivation: The ruling-set procedure replaces MIS because MIS was known to be computable only through network decomposition in the cited approach.
  • Definition: An (α,β)-ruling set has selected vertices at pairwise distance at least α and every graph vertex within distance β of one selected vertex.
  • Definition: A maximal independent set is a (2,1)-ruling set, while the construction here targets a (2,O(log n))-ruling set.
  • Construction: O(log n) deterministic rounds suffice to compute a (2,O(log n))-ruling set in the LOCAL model.The procedure assumes unique O(log n)-bit identifiers.
  • Construction: The construction repeatedly prunes vertices according to identifier bits, producing a nested sequence ending in the ruling set.
  • Construction: The resulting selected vertices root disjoint oriented trees of depth O(log n), giving every vertex a selected vertex within that distance.

A.2 Recap on the Approach of Awerbuch et al. [AGLP89]

The Awerbuch et al. approach iteratively reduces the graph using defective-degree structure and ruling sets, producing a 2^{O(√(log n log log n))}-round network decomposition.

  • Result: The resulting decomposition uses O(log n) color classes with clusters of diameter O(log n) and requires 2^{O(√(log n log log n))} rounds.
  • Iterative Reduction: The approach simulates one round on G_i using O(log n)^(i−1) rounds in the original graph.
  • Iterative Reduction: Each iteration separates vertices into high-degree H_i and low-degree L_i sets using threshold d.
  • Low-Degree Vertices: Low-degree vertices receive a d^2-coloring, with each color class becoming a final network-decomposition class.
  • High-Degree Vertices: A ruling set in the squared graph clusters high-degree vertices into oriented trees of depth O(log n), forming the next graph G_{i+1}.
  • Iterative Reduction: Each iteration reduces the number of vertices by at least a factor d+1, so the process takes at most log_d n iterations.

A.3 A New Network Decomposition with Complexity 2O(

The new construction builds a network-decomposition component by growing power-of-t ball neighborhoods, selecting ruling sets, and coloring covered vertices. It achieves 2^O(√(log n log log n)) rounds while producing O(log n) color classes with bounded weak diameter and substantial coverage.

  • Construction and guarantee: 2^O(√(log n log log n)) rounds suffice to compute a colored vertex set S with O(log n) colors and bounded weak-diameter components.Each color class has components of weak diameter 2^O(√(log n log log n)).
  • Construction and guarantee: Vertices grow balls with radii that are powers of t and stop when the smaller ball captures an ε fraction of the next larger ball.The stopping rule ensures |B(u,r(u))| is a substantial fraction of |B(u,t·r(u))|.
  • Ruling-set selection: Vertices are grouped by stopping radius into graphs G_i, where edges connect pairs within distance 3t_i to separate their corresponding balls.Nonadjacent vertices in G_i have balls that neither overlap nor touch.
  • Ruling-set selection: A (2,t/4)-ruling set is computed in each G_i, and every covered vertex receives the smallest index of a ruling-set ball containing it.The resulting balls within each color class are disjoint and nonadjacent, preserving bounded weak diameter.
  • Coverage and complexity: The construction outputs O(log n) color classes because log_(1/ε) n = O(log n), while enlarged balls cover the graph and smaller balls retain substantial volume.A double-counting argument establishes that S contains a substantial fraction of the graph’s vertices.

A.4 Contrasting the poly(log n)-round and 2O(

The earlier approaches face a shared obstruction on high-dimensional torus-like graphs: multiplicative cluster growth or contraction preserves difficult geometry and yields subpolylogarithmic barriers. The new algorithm avoids this by increasing cluster diameters additively.

  • Shared limitation: 2^O(√log n) rounds remain a barrier for both earlier approaches on a high-dimensional torus-like graph.The discussion is intuitive rather than formal and identifies a graph on which both approaches get stuck.
  • Hard instance: The hard graph has dimension √log n, side length about 2^√log n, diameter Θ(2^√log n), and volume expansion Θ(2^√log n) when doubling radius.It optimizes the trade-off between diameter and volume expansion.
  • Proposition A.4: Proposition A.4 grows balls by doubling their radius, so continuing until graph coverage requires time proportional to the graph diameter.Stopping earlier leaves the enlarged ball much larger than the selected ball, limiting the fraction colored in one phase.
  • Awerbuch et al.: The Awerbuch et al. approach contracts via ruling sets, but torus-like structure survives contractions and still requires 2^Θ(√log n) communication rounds to simulate.After O(log n) repetitions, the contracted graph retains the relevant high-dimensional structure.
  • New approach: The new algorithm circumvents the obstruction by growing clusters with only additive diameter increase per step rather than multiplicative increase.Both earlier methods instead rely on multiplicative radius changes and must achieve substantial progress per increase.

B CONGEST Network Decomposition for Power Graphs

The CONGEST extension lets red vertices within k hops of blue clusters propose through BFS and Steiner trees, while maintaining separation, bounded tree growth, and controlled congestion. Its running time is O(k log^8 n min(k + log^2 n)).

  • Algorithm: The extended process allows all red vertices within k hops of blue nodes to propose, identified by simultaneous BFS in k CONGEST rounds.The process is a k-iteration variant of BFS run from all blue nodes at once.
  • Algorithm: Red nodes receiving a token join the corresponding cluster’s Steiner tree as terminals and later broadcast their proposals through that tree.Living blue nodes remain inactive when receiving tokens, while living red nodes forward the selected token.
  • Correctness invariants: Steiner trees remain rooted trees, and token iteration i+1 reaches exactly vertices at distance i from the blue set.Additional invariants track token membership and decreasing distance for dead nodes that join later trees.
  • Correctness invariants: A blue cluster’s Steiner-tree radius grows by at most k per step, while red-cluster radii do not grow.This establishes the stated radius invariant for the process.
  • Running time: O(k log^8 n min(k + log^2 n)) rounds bound the full running time.The bound combines O(log n) color classes, O(log n) phases, O(log^2 n) steps per phase, BFS, and Steiner-tree broadcasts.
Loading 1907.10937v2…