  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.
  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. We present
universally optimal solutions for fundamental information dissemination tasks,
such as broadcasting and unicasting multiple messages in HYBRID. Furthermore,
we apply these tools to obtain universally optimal solutions for various
shortest paths problems in HYBRID.
  A main 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 HYBRID.
  We also show 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 algorithms for $k$-source shortest paths
match the existing $\tilde{\Omega}(\sqrt{k})$ lower bound for all $k$.
Previously, the lower bound was only known to be tight when $k \in
\tilde{\Omega}(n^{2/3})$.
