Universally-Optimal Distributed Shortest Paths and Transshipment via Graph-Based L1-Oblivious Routing

Abstract

We provide universally-optimal distributed graph algorithms for $(1+\epsilon )$-approximate shortest path problems including shortest-path-tree and transshipment. The universal optimality of our algorithms guarantees that, on any $n$-node network $G$, our algorithm completes in $T\cdot n^{o(1)}$ rounds whenever a $T$-round algorithm exists for $G$. This includes $D\cdot n^{o(1)}$-round algorithms for any planar or excluded-minor network. Our algorithms never require more than $(\sqrt{n}+D)\cdot n^{o(1)}$ rounds, resulting in the first sub-linear-round distributed algorithm for transshipment. The key technical contribution leading to these results is the first efficient $n^{o(1)}$-competitive linear ${\ell }_1$-oblivious routing operator that does not require the use of ${\ell }_1$-embeddings. Our construction is simple, solely based on low-diameter decompositions, and -- in contrast to all known constructions -- directly produces an oblivious flow instead of just an approximation of the optimal flow cost. This also has the benefit of simplifying the interaction with Sherman's multiplicative weight framework [SODA'17] in the distributed setting and its subsequent rounding procedures.

Accepted to SODA 2022. Author ordering was randomized using https://www.aeaweb.org/journals/policies/random-author-order/generator

References in corpus (2)

• Approximation of Distances and Shortest Paths in the Broadcast Congest Clique
• Low-Congestion Shortcuts in Constant Diameter Graphs

Cited by in corpus (1)

• Universally-Optimal Distributed Exact Min-Cut