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:
- 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.
- 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