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

Original language | English |
---|---|

Title of host publication | STOC 2022 - Proceedings of the 54th Annual ACM SIGACT Symposium on Theory of Computing |

Editors | Stefano Leonardi, Anupam Gupta |

Publisher | Association for Computing Machinery |

Pages | 1325-1338 |

Number of pages | 14 |

ISBN (Electronic) | 9781450392648 |

DOIs | |

State | Published - 6 Sep 2022 |

Event | 54th Annual ACM SIGACT Symposium on Theory of Computing, STOC 2022 - Rome, Italy Duration: 20 Jun 2022 → 24 Jun 2022 |

### Publication series

Name | Proceedings of the Annual ACM Symposium on Theory of Computing |
---|---|

ISSN (Print) | 0737-8017 |

### Conference

Conference | 54th Annual ACM SIGACT Symposium on Theory of Computing, STOC 2022 |
---|---|

Country/Territory | Italy |

City | Rome |

Period | 20/06/22 → 24/06/22 |

## Keywords

- distributed packet routing
- expander decomposition
- oblivious routing