TY - GEN
T1 - Hop-constrained expander decompositions, oblivious routing, and distributed universal optimality
AU - Haeupler, Bernhard
AU - Räcke, Harald
AU - Ghaffari, Mohsen
N1 - Publisher Copyright:
© 2022 ACM.
PY - 2022/9/6
Y1 - 2022/9/6
N2 - This paper studies the fundamental task of establishing routing paths in distributed networks. We prove the existence of compact routing tables that store in each network-node few simple forwarding rules tracing out hop-constrained and oblivious routing paths for any pair of nodes. For any collection of pairs the congestion of these paths is almost-optimal, i.e., competitive with the globally optimal solution up to a sub-polynomial factor. The key to this result is the algorithmic theory of hop-constrained expanders and expander decompositions developed in this paper. Informally, we say a graph is an h-hop †-expanders iff for any set of node-pairs, in which each node is paired to O(deg(v)) nodes at hop-distance O(h), there exists an (h)-hop path between each pair such that any edge is used at most (1/†) often. An h-hop †-expander is basically a regular (†)-expander when h = ω(logn/†). For shorter path lengths h 1/†, however, h-hop expanders become interesting, powerful, and fundamentally different. We prove that every graph can be decomposed into h-hop (boundary-linked) †-expanders by cutting at most an O(† logn)-fraction of its edges. We also provide efficient constructions for almost-optimal h-hop expander decompositions and our compact routing tables. These are parallel algorithms with almost-linear work and sub-polynomial depth that also have highly-efficient implementations in CONGEST, the standard model for distributed message-passing algorithms. As major implication this gives novel CONGEST algorithms for a large class of important optimization problems, including minimum-spanning tree, (1+")-min-cut, (1+)-shortest paths. Our algorithms solve these problems in sub-polynomial rounds on any network, as long as a sub-polynomial-round distributed algorithm exists for this network. This strong optimality guarantee is closely related to the notion of universal optimality.
AB - This paper studies the fundamental task of establishing routing paths in distributed networks. We prove the existence of compact routing tables that store in each network-node few simple forwarding rules tracing out hop-constrained and oblivious routing paths for any pair of nodes. For any collection of pairs the congestion of these paths is almost-optimal, i.e., competitive with the globally optimal solution up to a sub-polynomial factor. The key to this result is the algorithmic theory of hop-constrained expanders and expander decompositions developed in this paper. Informally, we say a graph is an h-hop †-expanders iff for any set of node-pairs, in which each node is paired to O(deg(v)) nodes at hop-distance O(h), there exists an (h)-hop path between each pair such that any edge is used at most (1/†) often. An h-hop †-expander is basically a regular (†)-expander when h = ω(logn/†). For shorter path lengths h 1/†, however, h-hop expanders become interesting, powerful, and fundamentally different. We prove that every graph can be decomposed into h-hop (boundary-linked) †-expanders by cutting at most an O(† logn)-fraction of its edges. We also provide efficient constructions for almost-optimal h-hop expander decompositions and our compact routing tables. These are parallel algorithms with almost-linear work and sub-polynomial depth that also have highly-efficient implementations in CONGEST, the standard model for distributed message-passing algorithms. As major implication this gives novel CONGEST algorithms for a large class of important optimization problems, including minimum-spanning tree, (1+")-min-cut, (1+)-shortest paths. Our algorithms solve these problems in sub-polynomial rounds on any network, as long as a sub-polynomial-round distributed algorithm exists for this network. This strong optimality guarantee is closely related to the notion of universal optimality.
KW - distributed packet routing
KW - expander decomposition
KW - oblivious routing
UR - http://www.scopus.com/inward/record.url?scp=85130638011&partnerID=8YFLogxK
U2 - 10.1145/3519935.3520026
DO - 10.1145/3519935.3520026
M3 - Conference contribution
AN - SCOPUS:85130638011
T3 - Proceedings of the Annual ACM Symposium on Theory of Computing
SP - 1325
EP - 1338
BT - STOC 2022 - Proceedings of the 54th Annual ACM SIGACT Symposium on Theory of Computing
A2 - Leonardi, Stefano
A2 - Gupta, Anupam
PB - Association for Computing Machinery
T2 - 54th Annual ACM SIGACT Symposium on Theory of Computing, STOC 2022
Y2 - 20 June 2022 through 24 June 2022
ER -