Hop-constrained expander decompositions, oblivious routing, and distributed universal optimality

Bernhard Haeupler, Harald Räcke, Mohsen Ghaffari

Publikation: Beitrag in Buch/Bericht/KonferenzbandKonferenzbeitragBegutachtung

24 Zitate (Scopus)

Abstract

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.

OriginalspracheEnglisch
TitelSTOC 2022 - Proceedings of the 54th Annual ACM SIGACT Symposium on Theory of Computing
Redakteure/-innenStefano Leonardi, Anupam Gupta
Herausgeber (Verlag)Association for Computing Machinery
Seiten1325-1338
Seitenumfang14
ISBN (elektronisch)9781450392648
DOIs
PublikationsstatusVeröffentlicht - 6 Sept. 2022
Veranstaltung54th Annual ACM SIGACT Symposium on Theory of Computing, STOC 2022 - Rome, Italien
Dauer: 20 Juni 202224 Juni 2022

Publikationsreihe

NameProceedings of the Annual ACM Symposium on Theory of Computing
ISSN (Print)0737-8017

Konferenz

Konferenz54th Annual ACM SIGACT Symposium on Theory of Computing, STOC 2022
Land/GebietItalien
OrtRome
Zeitraum20/06/2224/06/22

Fingerprint

Untersuchen Sie die Forschungsthemen von „Hop-constrained expander decompositions, oblivious routing, and distributed universal optimality“. Zusammen bilden sie einen einzigartigen Fingerprint.

Dieses zitieren