An Almost-Tight Distributed Algorithm for Computing Single-Source Shortest Paths

Monika Henzinger, Sebastian Krinninger, Danupon NanongkaiarXiv 2015 · arXiv · OpenReview

TL;DR

This paper presents the first non-trivial deterministic algorithm for approximating single-source shortest paths in distributed networks, achieving a near-optimal running time that matches known lower bounds up to subpolynomial factors. This breakthrough settles a long-standing open problem and introduces novel deterministic techniques for constructing hop sets and replacing randomized "hitting set" arguments.

What Problem Does This Paper Address?

In distributed computing, the CONGEST model is a common framework for analyzing how networks of processors can compute properties about themselves. Imagine a network of computers, each only knowing its immediate neighbors and the "cost" (weight) of the connections. They need to communicate using messages, with limitations on message size and the number of communication rounds. A fundamental problem is Single-Source Shortest Paths (SSSP): given a network and a designated "source" node, every node needs to figure out the shortest path (minimum total weight) from itself to the source.

While exact SSSP algorithms exist, they can be slow in distributed settings. Researchers have explored approximation algorithms that find paths that are close to the shortest path, aiming for faster execution. For SSSP, a key challenge has been to find a deterministic algorithm that is both fast and provides a good approximation. Previous fast algorithms were randomized, and deterministic solutions were significantly slower. The goal was to achieve a $(1+o(1))$-approximation (meaning the found path is at most a tiny bit longer than the true shortest path) with a running time close to the theoretical lower bound of $\tilde O(\sqrt{n} + D)$, where $n$ is the number of nodes and $D$ is the network's diameter.

Methods

The paper introduces two core novel techniques:

  1. Deterministic "Hitting Set" Replacement: The "hitting set argument" is a common randomized technique used to simplify shortest path computations by selecting a random subset of nodes (centers) that are likely to lie on many paths. This paper presents a deterministic method to achieve a similar effect, ensuring that "long" paths are guaranteed to be "hit" by a strategically chosen set of nodes. This is achieved by assigning nodes "types" and using a deterministic process to select centers based on these types.
  2. Deterministic Hop Set Construction: A "hop set" is a set of additional edges added to a graph that allows approximating shortest paths using a limited number of hops (edges). The paper presents a deterministic construction for an $(n^{o(1)}, o(1))$-hop set of size $n^{1+o(1)}$. This is a significant improvement over previous randomized constructions and is crucial for achieving the near-optimal running time.

These techniques are combined with existing distributed algorithms for:

  • Source Detection: Identifying nodes close to a set of "sources."
  • Ruling Sets: Selecting a subset of nodes with certain distance properties.
  • Partial Distance Estimation: Estimating distances to a subset of nodes.

Datasets

Not discussed in the paper. The algorithms are theoretical and designed for general weighted undirected graphs.

Key Insights and Ideas

  • Deterministic Approximation is Possible: The paper demonstrates that achieving near-optimal approximation for SSSP in distributed settings doesn't require randomization, settling a long-standing question.
  • Novel Deterministic Techniques: The core contributions are the deterministic replacement for the hitting set argument and the deterministic hop set construction. These are powerful tools that can likely be applied to other distributed graph problems.
  • Modularity: The algorithm is structured modularly, separating the construction of an "overlay network" from the actual shortest path computation on that network. This makes the approach more flexible.
  • Bridging Theory and Practice: The work significantly narrows the gap between theoretical lower bounds and achievable upper bounds for this fundamental distributed problem.

Key Results

The paper presents a deterministic $(1+o(1))$-approximation algorithm for SSSP in the CONGEST model with a running time of $O(n^{1/2+o(1)} + D^{1+o(1)})$. This result:

  • Matches the known lower bound of $\Omega(n^{1/2}/\log n + D)$ up to subpolynomial factors.
  • Improves upon previous randomized algorithms by a factor of up to $n^{1/8}$.
  • Implies a $(2+o(1))$-approximation algorithm for weighted diameter approximation within the same time complexity.
  • Also yields deterministic algorithms for SSSP in congested clique and streaming models.

Limitations and Future Work

  • Directed Graphs: The deterministic hitting set replacement technique currently works only for undirected graphs. Derandomizing algorithms for directed graphs remains an open problem.
  • Exact SSSP: While the paper settles approximate SSSP, the exact SSSP problem still has a gap between the best known upper bound and the lower bound. Understanding the complexity of exact distributed algorithms is an important open problem.
  • Subpolynomial Factors: The authors mention that the $o(1)$ terms in the approximation ratio and running time hide subpolynomial factors. Eliminating these could be a direction for future work, although recent results suggest this might be challenging.

Summary updated

Abstract

We present a deterministic $(1+o(1))$-approximation $(n^{1/2+o(1)}+D^{1+o(1)})$-time algorithm for solving the single-source shortest paths problem on distributed weighted networks (the CONGEST model); here $n$ is the number of nodes in the network and $D$ is its (hop) diameter. This is the first non-trivial deterministic algorithm for this problem. It also improves (i) the running time of the randomized $(1+o(1))$-approximation $\tilde O(n^{1/2}D^{1/4}+D)$-time algorithm of Nanongkai [STOC 2014] by a factor of as large as $n^{1/8}$, and (ii) the $O(\epsilon^{-1}\log \epsilon^{-1})$-approximation factor of Lenzen and Patt-Shamir's $\tilde O(n^{1/2+\epsilon}+D)$-time algorithm [STOC 2013] within the same running time. Our running time matches the known time lower bound of $\Omega(n^{1/2}/\log n + D)$ [Elkin STOC 2004] up to subpolynomial factors, thus essentially settling the status of this problem which was raised at least a decade ago [Elkin SIGACT News 2004]. It also implies a $(2+o(1))$-approximation $(n^{1/2+o(1)}+D^{1+o(1)})$-time algorithm for approximating a network's weighted diameter which almost matches the lower bound by Holzer and Pinsker [OPODIS 2015]. In achieving this result, we develop two techniques which might be of independent interest and useful in other settings: (i) a deterministic process that replaces the "hitting set argument" commonly used for shortest paths computation in various settings, and (ii) a simple, deterministic, construction of an $(n^{o(1)}, o(1))$-hop set of size $n^{1+o(1)}$. We combine these techniques with many distributed algorithmic techniques, some of which from problems that are not directly related to shortest paths, e.g., ruling sets [Goldberg et al. STOC 1987], source detection [Lenzen and Peleg PODC 2013], and partial distance estimation [Lenzen and Patt-Shamir PODC 2015].
BibTeX
@misc{henzinger2015almost,
  author = {Monika Henzinger and Sebastian Krinninger and Danupon Nanongkai},
  title = {{An Almost-Tight Distributed Algorithm for Computing Single-Source Shortest Paths}},
  year = {2015},
  eprint = {1504.07056},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/1504.07056},
}
Figure