PaperlayerView exact revision on arXiv

Source-linked AI summary

An Improved Distributed Algorithm for Maximal Independent Set

Mohsen Ghaffari

arXiv:1506.05093v2cs.DS

TL;DR

The paper asks whether MIS can achieve tight probabilistic guarantees for each node using local analysis rather than global termination arguments. It introduces an extremely simple randomized algorithm with near-optimal local complexity and combines it with graph-shattering techniques to obtain an improved global bound. The results also yield improvements for several related distributed models and problems, while stronger lower bounds remain constrained by tree-local-view techniques.

  • Problem

    Existing MIS analyses primarily target global termination, leaving open whether tight probabilistic time guarantees can be established separately for each node using only local neighborhoods.

  • Method

    The paper develops a simple randomized MIS algorithm with a local analysis and combines it with graph shattering and deterministic finish-off techniques.

  • Results

    O(log deg(v) + log 1/ε) rounds suffice for each node v with probability at least 1 − ε, and the combined algorithm terminates globally in O(log Δ) + 2^O(√(log log n)) rounds with probability at least 1 − 1/n.

  • Takeaways & Limitations

    The local degree-dependent guarantee is optimal under the cited lower bound and improves the previous global MIS bound while supporting improvements for several related problems and models.

  • Takeaways & Limitations

    Improving the known lower bound requires abandoning tree local views, a technique for which no distributed locality-based lower bound is currently known.

Abstract

from arXiv · show

The Maximal Independent Set (MIS) problem is one of the basics in the study of locality in distributed graph algorithms. This paper presents an extremely simple randomized algorithm providing a near-optimal local complexity for this problem, which incidentally, when combined with some recent techniques, also leads to a near-optimal global complexity. Classical algorithms of Luby [STOC'85] and Alon, Babai and Itai [JALG'86] provide the global complexity guarantee that, with high probability, all nodes terminate after $O(\log n)$ rounds. In contrast, our initial focus is on the local complexity, and our main contribution is to provide a very simple algorithm guaranteeing that each particular node $v$ terminates after $O(\log \mathsf{deg}(v)+\log 1/ε)$ rounds, with probability at least $1-ε$. The guarantee holds even if the randomness outside $2$-hops neighborhood of $v$ is determined adversarially. This degree-dependency is optimal, due to a lower bound of Kuhn, Moscibroda, and Wattenhofer [PODC'04]. Interestingly, this local complexity smoothly transitions to a global complexity: by adding techniques of Barenboim, Elkin, Pettie, and Schneider [FOCS'12, arXiv: 1202.1983v3], we get a randomized MIS algorithm with a high probability global complexity of $O(\log Δ) + 2^{O(\sqrt{\log \log n})}$, where $Δ$ denotes the maximum degree. This improves over the $O(\log^2 Δ) + 2^{O(\sqrt{\log \log n})}$ result of Barenboim et al., and gets close to the $Ω(\min\{\log Δ, \sqrt{\log n}\})$ lower bound of Kuhn et al. Corollaries include improved algorithms for MIS in graphs of upper-bounded arboricity, or lower-bounded girth, for Ruling Sets, for MIS in the Local Computation Algorithms (LCA) model, and a faster distributed algorithm for the Lovász Local Lemma.

1 Introduction and Related Work

The paper shifts MIS analysis from global termination to per-node local complexity, asking whether tight guarantees can be obtained from small neighborhoods. It gives a simple randomized algorithm with near-optimal local complexity and improved global and related-model consequences.

  • Motivation: MIS locality research traditionally emphasized global termination, often analyzing whole-graph progress rather than individual nodes.Classical analyses show that removing a constant fraction of all edges per round yields O(log n) global termination with high probability.
  • Motivation: The local complexity question asks how long each particular node v needs to decide MIS membership with probability at least 1 − ε.This separates per-node probabilistic guarantees from the time until every node terminates.
  • Local Complexity: O(log deg(v) + log 1/ε) rounds suffice for node v, even when randomness outside its 2-hop neighborhood is adversarially determined.This degree-dependent local guarantee is supported directly by Theorem 1.1.
  • Local Complexity: The logarithmic degree dependence is optimal under the cited lower bound, which requires Ω(log Δ) rounds for some nodes to decide with constant probability.The paper therefore matches the relevant local lower-bound dependence up to the distinction between local degree and maximum degree.
  • Open Questions: A stronger lower bound remains open because current locality arguments rely on tree local views, and no distributed locality lower bound is known without that restriction.The paper identifies this topology requirement as a barrier to improving the existing lower bound.

2 Warm Up: Local Analysis of Luby’s Algorithm

Luby’s algorithm is simple and globally efficient, but tightly analyzing its local complexity is difficult because neighboring degree reductions can be delayed and correlated. Successive modifications improve the local bound, yet retain unfavorable degree or error dependencies.

  • Luby’s Algorithm: Each round assigns random numbers, adds strict local minima to the MIS, and removes those nodes and their neighbors.One algorithmic round can be implemented using two communication rounds in the LOCAL model.
  • Global Analysis: O(log n) rounds suffice globally with high probability because each iteration removes at least half of the remaining edges in expectation.The standard analysis uses a global view of the graph and applies Markov’s inequality.
  • Local Analysis: A local degree argument shows that a node whose degree is at least half its neighbors’ maximum degree is removed in one round with probability at least 1/3.Degree reductions cannot be chained straightforwardly because neighboring delays may be positively correlated.
  • Local Analysis: Take 1: O(log^2.5 ∆ + log ∆ log 1/ε) rounds provide a weak local guarantee for Luby’s algorithm.The argument repeatedly reduces the degrees of a node and its neighborhood, then uses repetition to obtain failure probability at most ε.
  • Local Analysis: Take 1: O(log^2 ∆ + log 1/ε) rounds improve Luby’s local bound, but the O(log^2 ∆) term remains far from optimal.The stronger analysis is described as more complex than the preceding argument.
  • Local Analysis: Take 2: Θ(log ∆ log log ∆ + log ∆ log 1/ε) rounds result from kicking out nodes whose degree lags behind phase thresholds.This modification improves the ∆-dependency, but the error term is multiplied by log ∆, which also yields an O(log^2 ∆) shattering threshold.

3 The New Algorithm and Its Local Complexity

The paper introduces a simple randomized MIS algorithm whose progress depends locally on effective neighbor activity, yielding fast per-node termination even under distant adversarial randomness.

  • Local guarantee: O(log deg(v) + log 1/ε) rounds suffice for node v to decide with probability at least 1 − ε, even when randomness outside its 2-hop neighborhood is adversarially fixed.The decision is whether v joins MIS or has a neighbor in MIS.
  • Algorithm: The algorithm assigns each node a desire-level and defines effective-degree as the sum of neighbors’ desire-levels.Desire-levels start at 1/2 and are adjusted according to whether effective-degree is at least 2.
  • Algorithm: Each round marks node v with probability p_t(v); an unopposed marked node joins MIS and removes itself and its neighbors.One algorithmic round uses two communication rounds in the LOCAL model.
  • Analysis: Golden rounds capture two removal opportunities: v can join when competition is low, or a low-degree neighbor can join when many such neighbors compete.The analysis proves that enough golden rounds occur within the target time.
  • Novelty: Unlike Luby’s fixed marking probability, the algorithm dynamically changes desire-levels to decouple v’s progress from nodes farther than roughly 3 hops away.This flexible update is identified as the key ingredient of the new algorithm.
  • Analysis: Each golden round removes v with probability at least 1/100, so 100(log deg(v) + log 1/ε) golden rounds reduce the failure probability to at most ε.Type-1 rounds give v a chance to join; type-2 rounds give a neighbor a chance to join.

4 Improved Global Complexity

Combining the local MIS algorithm with shattering and deterministic finishing techniques gives a high-probability global complexity of O(log Δ) + 2^{O(√log log n)} rounds.

  • Global result: O(log Δ) + 2^{O(√log log n)} rounds yield the promised high-probability global MIS complexity.The bound includes O(log Δ) pre-shattering rounds and the finishing phase.
  • Shattering: After Θ(c log Δ) rounds, every 5-independent set S remains entirely undecided with probability at most Δ^{-c|S|}.The proof uses local randomness within distance 2 and disjoint neighborhoods of 5-independent nodes.
  • Shattering: With probability at least 1 − 1/n^c, the remaining undecided set has no G^4-independent, G^9-connected subset of size at least log_Δ n.G^x connects nodes whose original graph distance is at most x.
  • Finish-off: A direct deterministic finish would give 2^{O(√(log Δ log log n))} rounds, so the method leverages the shattering structure to remove the undesirable log Δ factor from the exponent.The contraction-based approach bounds contracted component size by log_Δ n with high probability.
  • Finish-off: The remaining components are finished using ruling sets, clustering, contraction, and deterministic MIS computation on the contracted graphs.A (5,h)-ruling set with h = Θ(log log n) supports the clustering and contraction step.
  • Finish-off: The deterministic finishing phase processes network-decomposition colors sequentially, with each cluster solving its MIS instance locally after gathering its topology and prior adjacent MIS information.The total color-processing complexity is 2^{O(√log log n)} rounds.

5 Concluding Remarks

The paper concludes that its local MIS guarantee is near-optimal, while the remaining upper–lower-bound gap and deterministic complexity question remain open.

  • Contributions and open questions: The local degree-dependent guarantee is optimal up to constants, matching a lower bound requiring Ω(log Δ) rounds for some nodes.The lower bound concerns deciding MIS membership with constant probability.
  • Contributions and open questions: The improved global complexity still has an upper–lower-bound gap when log Δ = ω(√log n).The paper identifies this gap as its most interesting open question.
  • Contributions and open questions: Closing the gap may require moving beyond tree-local-view topologies if the lower bound is the quantity that should improve.This is presented as a conditional direction rather than a resolved result.
  • Contributions and open questions: A poly(log n) deterministic distributed MIS algorithm remains another longstanding open problem.Combined with this paper’s results, such an algorithm could potentially yield O(log Δ) + poly(log log n) randomized complexity.

A Simplified Global Analysis of Luby’s, due to Yves et al.

The appendix gives a simplified global analysis of Luby’s algorithm by showing geometric decay in the expected number of alive edges and then applying Markov’s inequality.

  • Edge-decay analysis: E[m_{t+1}] ≤ m_t/2: each round halves the expected number of edges among currently alive nodes.The expectation is over the randomness of round t.
  • Edge-decay analysis: An alive edge dies when a node adjacent to one of its endpoints is the strict local minimum in its neighborhood.The node responsible for this event is described as killing the edge.
  • Edge-decay analysis: The probability that a node w kills an edge is 1/(d(w)+1), but direct summation is difficult because different killing events overlap.The appendix resolves this overlap through strongly killing events.
  • Strong killing: Strong killing requires w to be the strict minimum over Γ_w ∪ Γ_v, making events from the same endpoint disjoint and losing only a 2-factor for possible double counting.This change is attributed to Yves et al.
  • Global conclusion: After 4 log n rounds, the expected number of alive edges is at most n^2/2.This follows directly from repeated halving in the edge process.
  • Global conclusion: Markov’s inequality bounds the probability that any edge remains alive after 4 log n rounds by at most 1/n^2, so all nodes terminate with that probability guarantee.The supplied derivation states the resulting all-node termination bound after 4 log n rounds.
Loading 1506.05093v2…