Universally Optimal Information Dissemination and Shortest Paths in the HYBRID Distributed Model

In most modern networks, nodes have access to various modes of communication each with different characteristics. In this work we consider the Hybrid model of distributed computing, introduced recently by Augustine, Hinnenthal, Kuhn, Scheideler, and Schneider (SODA 2020), where nodes have access to two different communication modes: high-bandwidth local communication along the edges of the graph and low-bandwidth all-to-all communication, capturing the non-uniform nature of modern communication networks. It is noteworthy that the Hybrid model in its most general form covers most of the classical distributed models as marginal cases.

Prior work in Hybrid has focused on showing existentially optimal algorithms, meaning there exists a pathological family of instances on which no algorithm can do better. This neglects the fact that such worst-case instances often do not appear or can be actively avoided in practice. In this work, we focus on the notion of universal optimality, first raised by Garay, Kutten, and Peleg (FOCS 1993). Roughly speaking, a universally optimal algorithm is one that, given any input graph, runs as fast as the best algorithm designed specifically for that graph.

We show the first universally optimal algorithms in Hybrid, up to polylogarithmic factors. We present universally optimal solutions for fundamental tools that solve information dissemination problems, such as broadcasting and unicasting multiple messages in a Hybrid network. Furthermore, we demonstrate these tools for information dissemination can be used to obtain universally optimal solutions for various shortest paths problems in Hybrid. A major conceptual contribution of this work is the conception of a new graph parameter called neighborhood quality that captures the inherent complexity of many fundamental graph problems in the Hybrid model. We also develop new existentially optimal shortest paths algorithms in Hybrid, which are utilized as key subroutines in our universally optimal algorithms and are of independent interest. Our new approximation algorithms for k-source shortest paths match the existing [EQUATION] lower bound for all k. Previously, the lower bound was only known to be tight when k ∈ Ω(n^2/3).