# Near Tight Shortest Paths in the Hybrid Model

Philipp Schneider, University of Bern, Switzerland
<EMAIL_ADDRESS>
###### Abstract

Shortest paths problems are subject to extensive studies in classic
distributed models such as the $\mathsf{CONGEST}$ or
$\mathsf{Congested\,Clique}$. These models dictate how nodes may communicate
in order to determine shortest paths in a distributed input graph. This
article focuses on shortest paths problems in the $\mathsf{HYBRID}$ model,
which combines local communication along edges of the input graph with global
communication between arbitrary pairs of nodes that is restricted in terms of
bandwidth.

Previous work showed that it takes $\smash{\widetilde{\Omega}}(\\!\sqrt{k})$
rounds in the $\mathsf{HYBRID}$ model for each node to learn its distance to
$k$ dedicated source nodes (aka the $k$-SSP problem), even for crude
approximations. This lower bound was also matched with algorithmic solutions
for $k\geq n^{2/3}$. However, as $k$ gets smaller, the gap between the known
upper and lower bounds diverges and even becomes exponential for the single
source shortest paths problem (SSSP). In this work we close this gap for the
whole range of $k$ (up to terms that are polylogarithmic in $n$), by giving
algorithmic solutions for $k$-SSP in
$\smash{\widetilde{O}}\big{(}\\!\sqrt{k}\big{)}$ rounds for any $k$.

##  1 Introduction

Computing or approximating shortest paths in a network has important uses, for
instance to obtain information about the topology of the network or as a
subroutine for related tasks like computing or updating tables for IP routing.
In shortest paths problems nodes of a network are required to learn their
distance to other nodes and in the distributed version of the shortest paths
problem knowledge of input graph is spread over the nodes, which must then
determine their distance to other nodes by efficiently communicating with each
other.

This problem has obtained significant attention from a theoretical angle in
the classical models of distributed computing over the last decade (see e.g.
[50, 24] and the references therein). These classic models come in two
different “flavors”. The first is based on local communication in a graph,
where nodes communicate in synchronous rounds and in each such round adjacent
pairs of nodes in a graph $G$, which also serves as the problem input, may
exchange a small message (this is called $\mathsf{CONGEST}$ model).

The second flavor captures global communication, where any pair of nodes can
exchange a small message per round and each node initially knows only its
neighbors of the input graph $G$ (this became known as the
$\mathsf{Congested\,Clique}$ model). Another example of global communication
is the $\mathsf{MPC}$ model (cf. [41, 31, 7, 12]), which in some sense
generalizes the $\mathsf{Congested\,Clique}$ model and was inspired by
practical applications (cf. MapReduce [23]).

Theoretic research on distributed graph problems and in particular shortest
paths problems has concentrated mostly on distributed models where nodes use
only either a local or global mode of communication. This began to change only
recently with the introduction of the so called $\mathsf{HYBRID}$ model [11],
where nodes have access to two modes of communication. First, a graph based
local mode which allows neighbors to communicate by exchanging relatively
large messages. And second, a global mode where any pair of nodes can
communicate in principle but only a few small messages may be exchanged each
round.

The hybrid model is intended to capture the fact that in modern networks,
nodes can often interface with multiple, diverse communication
infrastructures. For instance, data centers combine wired communication with
wireless communication [34]. Organizations can augment their own networks with
communication over the Internet using virtual private networks (VPNs) [52].
Another example are mobile devices like smart-phones, which have access to
high bandwidth, short range communication via WiFi or Bluetooth with other
devices that are close by, which can be combined with the relatively low-
bandwidth communication via the cellular network (cf., 5G [8]).

###  1.1 The $\mathsf{HYBRID}$ model

For the formal definition of the $\mathsf{HYBRID}$ model, we rely on the
concept of synchronous message passing [49], where nodes exchange messages and
conduct local computations in synchronous rounds. Note that synchronous
message passing focuses on the round complexity, i.e., the number of rounds
required to solve a distributed problem, and therefore nodes are considered
computationally unbounded.

######  Definition 1 (Synchronous Message Passing, cf. [49]).

Let $V$ be a set of $n$ nodes with unique identifiers
ID$:V\\!\to\\![n]\\!\stackrel{{\scriptstyle\text{def}}}{{=}}\\!\\{1,\ldots,n\\}$.
Time is slotted into discrete rounds. Nodes wake up synchronously at the start
of some round and each round consists of the following steps. First, all nodes
receive the set of messages addressed to them in the last round. Second, nodes
conduct computations based on their current state and the set of received
messages to compute their new state (randomized algorithms also include the
result of a random function). Third, based on the new state, the next messages
are sent.

The aim of the $\mathsf{HYBRID}$ model is to reflect the fundamental concepts
of locality and congestion to capture the nature of distributed systems that
combine both physical and logical networks.

######  Definition 2 (cf. [10]).

The $\mathsf{HYBRID}(\lambda,\gamma)$ model is a synchronous message passing
model (Def. 1), subject to the following restrictions. _Local mode:_ nodes may
send a message per round of maximum size $\lambda$ bits to each of their
neighbors in a connected graph. _Global mode:_ nodes can send and receive
messages of total size at most $\gamma$ bits per round to/from any other
node(s) in the network. If these restrictions are violated a strong
adversary111The strong adversary knows the states of all nodes, their source
codes and even the outcome of all random functions. selects the messages that
are delivered.

The parameter $\lambda$ restricts the bandwidth over edges in the local
network, and $\gamma$ restricts the amount of global communication of nodes.
Notably, the classical models of distributed computing are covered by this
model as marginal cases: $\mathsf{LOCAL}$ and $\mathsf{CONGEST}$ are given by
$\gamma=0$ and $\lambda=\infty$ and $\lambda\in\smash{O}(\log n)$,
respectively. The $\mathsf{Congested\,Clique}$ and $\mathsf{NCC}$ models are
given by $\lambda=0$ and $\gamma\in\smash{O}(n\log n)$ (due Lenzens routing
algorithm [45]) and $\gamma\in\smash{O}(\log^{2}n)$, respectively.

Of particular practical and theoretical interest are non-marginal
parameterizations of $\mathsf{HYBRID}(\lambda,\gamma)$ that push both
communication modes to one extreme end of the spectrum. More specifically, to
model the high bandwidth of physical connections we leave the size of local
messages unrestricted. To model the severely restricted global bandwidth of
shared logical networks, we allow only $\operatorname{polylog}n$ bits of
global communication per node per round. Formally, we define the “standard”
hybrid model as combination of the standard $\mathsf{LOCAL}$ [51] and node
capacitated clique [10] models:
$\mathsf{HYBRID}:=\mathsf{HYBRID}\big{(}\infty,\smash{O}(\log^{2}n)\big{)}$.

###  1.2 Preliminaries

We continue with some definitions, conventions and nomenclature that we will
use in the following.

######  Definition 3 ($k$-Sources Shortest Paths ($k$-SSP) Problem).

Given subset of $k$ source nodes in a graph $G=(V,E)$, every node $v\in V$ has
to learn $d(v,s)$ for all sources $s$. In the $\alpha$-approximate version of
the problem for _stretch_ $\alpha\geq 1$, every $u\in V$ has to learn values
$\tilde{d}(v,s)$ such that $d(v,s)\leq\tilde{d}(v,s)\leq\alpha d(v,s)$ for all
sources $s$.

The all-pairs shortest paths problem (APSP) equals the case $k=n$ and the
single-source shortest paths problem (SSSP) equals the case $k=1$. Note that
the local communication graph and the input graph for the graph problem are
the same, which is a standard assumption for distributed models with graph-
based communication (like $\mathsf{LOCAL}$ and $\mathsf{CONGEST}$).

Our algorithms are randomized and aim for success with high probability
(w.h.p.), which means with success probability at least $1-\frac{1}{n^{c}}$
for an arbitrary constant $c>0$. We write i.i.d. if we pick elements from some
set independently, identically distributed. In this work, logarithm functions
without subscript are generally to the base of two, i.e.,
$\log\stackrel{{\scriptstyle\text{def}}}{{=}}\log_{2}$. Sometimes we write
$\operatorname{polylog}n$ to describe terms of the form $q(\log n)$ where $q$
is a polynomial. We abbreviate sets of the form
$\\{1,\dots,k\\},k\in\mathbb{N}$ with $[k]$. We will often neglect logarithmic
factors in $n$ using the soft $\smash{\widetilde{O}}$-notation.

We consider undirected, connected communication graphs $G=(V,E)$. Edges have
weights $w:E\to[W]$, where $W$ is at most polynomial in $n$, thus the weight
of an edge and of a simple path fits into a $\smash{O}(\log n)$ bit message. A
graph is considered unweighted if $W=1$. Let $w(P)=\sum_{e\in P}w(e)$ denote
the length of a path $P\subseteq E$.

Then the _distance_ between two nodes $u,v\in V$ is
$d_{G}(u,v):=\\!\min_{\text{$u$-$v$-path }P}w(P).$ A path with smallest length
between two nodes is called a _shortest path_. Let $|P|$ be the number of
edges (or _hops_) of a path $P$. We define the _$h$ -hop limited distance_
from $u$ to $v$ as $d_{G,h}(u,v):=\\!\\!\min_{{\text{$u$-$v$-path }P,|P|\leq
h}}\,w(P).$ If there is no $u$-$v$ path $P$ with $|P|\leq h$ we define
$d_{G,h}(u,v):=\infty$.

The _hop-distance_ between two nodes $u$ and $v$ is defined as
$\operatorname{hop}_{G}(u,v):=\\!\min_{\text{$u$-$v$-path }P}|P|.$ We
generalize this for sets $U,W\subseteq V$
$\operatorname{hop}_{G}(U,W):=\\!\min_{u\in U,w\in
W}\operatorname{hop}_{G}(u,w)$ (whereas $\operatorname{hop}_{G}(v,v):=0$). The
_diameter_ of $G$ is defined as $D_{G}:=\max_{u,v\in
V}\operatorname{hop}_{G}(u,v).$ We drop the subscript $G$, if $G$ is clear
from the context.

###  1.3 Related Work

#### Local Communication Networks.

Shortest paths problems have been intensely studied in the $\mathsf{CONGEST}$
model. For the SSSP problem, [54] showed that any approximation algorithm has
a runtime of $\smash{\widetilde{\Omega}}(\\!\sqrt{n}+D)$ for any constant
stretch. Following the publication of this lower bound, there has been a
series of papers that attempt to obtain algorithms that get close to the lower
bound, see [46, 50, 35, 13, 26, 30, 28, 22, 20]. Notably, the work of [13]
gives an algorithm that computes a $(1+\varepsilon)$-approximate SSSP solution
in time $\smash{\widetilde{O}}(\\!\sqrt{n}\\!+\\!D)$.

In another strain of work, [33, 57] aim for SSSP algorithms that are
competitive in terms of complexity to the best algorithm that can be crafted
for a given graph topology, which is also known as universal optimality. The
work of [57] achieves a $(1+\varepsilon)$ approximation, in time
$T\\!\cdot\\!n^{o(1)}$, where $T$ is the complexity of the best
$\mathsf{CONGEST}$ algorithm for the given topology, which comes close to the
best known algorithm that is optimized for the worst case where
$T\in\smash{\widetilde{\Omega}}(\\!\sqrt{n}+D)$ (see above).

The APSP problem in $\mathsf{CONGEST}$ has received significant attention as
well [37, 29, 50, 47, 1, 38, 26, 18, 39, 5, 3, 14, 4, 2]. Linear lower bounds
that hold for small diameter graphs are shown or implied by [29, 50, 1, 18].
Notably a lower bound of $\smash{\widetilde{\Omega}}(n/\log n)$ [50] that
holds for the unweighted case and constant stretch approximations is matched
by an $\smash{O}(n/\log n)$ algorithm for unweighted graphs [38].
Interestingly, [2] gives a $\Omega(n)$ lower bounded for the weighted problem,
thus separating it from the unweighted case. In terms of algorithmic upper
bounds, the current state of the art is the randomized algorithm by [14],
which computes an exact solution in $\smash{\widetilde{O}}(n)$ rounds, even
for directed edges with negative and zero weights. The best deterministic,
exact algorithm takes $\smash{\widetilde{O}}(n^{4/3})$ rounds and is due to
[4].

#### Global Communication Networks.

Shortest paths problems also obtained significant attention in the
$\mathsf{Congested\,Clique}$ model, see, [44, 21, 16, 17, 40, 25, 15, 24].
Some of these results give fast (down to $\smash{\widetilde{O}}(1)$ rounds),
constant approximations for APSP and $k$-SSP in the
$\mathsf{Congested\,Clique}$ model. The power of the
$\mathsf{Congested\,Clique}$ model is demonstrated by [25] which achieves a
$\operatorname{poly}(\log\log n)$ round, constant approximation of APSP on
unweighted graphs. For cruder $\smash{\widetilde{O}}(1)$ approximations of
APSP [24] even achieves constant rounds on weighted graphs.

In a branch similar to $\mathsf{Congested\,Clique}$, the work of [50, 36, 13]
investigates shortest paths in the broadcast variant of
$\mathsf{Congested\,Clique}$, where in each round, each node may broadcast a
single message. Notably, [13] gives a $(1\\!+\\!\varepsilon)$-approximation
algorithm for the SSSP problem that runs in $\smash{\widetilde{O}}(1)$ rounds.
Finally, [10] introduces the more restrictive $\mathsf{NCC}$ model and
considers various fundamental graph problems. Their algorithmic solutions
include the computation of BFS trees, which can be used to solve the SSSP
problem for unweighted graphs of bounded arboricity in
$\smash{\widetilde{O}}(D)$ rounds.

Figure 1: Complexity landscape of the $k$-SSP problem with the number of
sources on the horizontal and the round complexity on the vertical axis.
Circles or bars denote known upper bounds (ours in gray). The gray shaded area
denotes the lower bound. References are as follows $*$: [11], $\dagger$: [42],
$\ddagger$: [19], §: this work.

#### Hybrid Communication Networks

A graphic overview of the state of the art for the $k$-SSP problem is provided
in Figure 1. Research on shortest paths in the $\mathsf{HYBRID}$ model was
started by [11], with a range of results. They introduce a technique for
efficiently broadcasting messages in the network, which they leverage, for
instance, to obtain an exact solution of APSP in
$\smash{\widetilde{O}}(n^{2/3})$ rounds and a $1\\!+\\!\varepsilon$
approximation in $\smash{\widetilde{O}}(\\!\sqrt{n})$ rounds (for constant
$\varepsilon>0$), matching their lower bound of
$\smash{\widetilde{\Omega}}(\\!\sqrt{n})$ (which holds even for randomized
$\smash{O}(\\!\sqrt{n})$ approximations). For SSSP, they give a
$1\\!+\\!\varepsilon$ approximation in $\smash{\widetilde{O}}(n^{1/3})$
rounds, a $(1/\varepsilon)^{\smash{O}(1/\varepsilon)}$ approximation in
$\smash{\widetilde{O}}(n^{\varepsilon})$ rounds and an exact solution in
$\smash{\widetilde{O}}\big{(}\\!\sqrt{SPD}\big{)}$ rounds, where $SPD$ is the
shortest path diameter.

Subsequently, [42] improves APSP to $\smash{\widetilde{O}}(n^{1/2})$ for an
exact solution based on a scheme for efficiently unicasting messages in the
network, which settled the problem (up to logarithmic factors in the round
complexity). They also give an exact solution for SSSP in
$\smash{\widetilde{O}}(n^{3/5})$ rounds and constant stretch approximations
for $k$-SSP in $\smash{\widetilde{O}}(n^{1/3}+\sqrt{k})$ rounds, which is
tight with their lower bound of $\smash{\widetilde{\Omega}}(\\!\sqrt{k})$
rounds for $k\geq n^{2/3}$. The stretch was later improved by [19] which
combines the techniques of [42] with a density sensitive approach. In
particular, [19] gives exact solutions for $k\geq n^{2/3}$ random sources in
$\smash{\widetilde{O}}(\\!\sqrt{k})$ rounds and for $n^{1/3}$-SSP in
$\smash{\widetilde{O}}(n^{1/3})$ rounds.

In a subsequent work, [20] uses density awareness in a different way to solve
SSSP in $\smash{\widetilde{O}}(n^{5/17})$ rounds for stretch
$(1\\!+\\!\varepsilon)$. A deterministic protocol for efficiently broadcasting
local edges is given by [6] and then used to obtain a deterministic APSP-
algorithm with stretch $\frac{\log n}{\log\log n}$ in
$\smash{\widetilde{O}}(n^{1/2})$ rounds. For classes of sparse graphs (e.g.,
cactus graphs), [27] demonstrates that $\operatorname{polylog}n$ solutions are
possible even with $\mathsf{CONGEST}$ as local network.

###  1.4 Contributions

Shortest paths problems are hard to solve if only either of the constituent
communication modes of the $\mathsf{HYBRID}$ model can be used in isolation.
In the $\mathsf{LOCAL}$ model computing even crude approxiations for a single
source requires $D_{G}$ rounds, where $D_{G}$ is the diameter of $G$ which can
be linear in $n$. In the $\mathsf{NCC}$ model, a single node learning its
distance to $k$ source nodes has a lower bound of
$\smash{\widetilde{\Omega}}(k)$. By contrast, the known bounds for the $k$-SSP
problem (see Definition 3) in the $\mathsf{HYBRID}$ model are
$\smash{\widetilde{\Omega}}(\\!\sqrt{k})$ for $k\in[n]$ and
$\smash{\widetilde{O}}(\\!\sqrt{k})$ for relatively large $k$ [11, 42]. This
work focuses on closing the gap to the lower bound for the whole range of
$k\in[n]$ (up to $\smash{\widetilde{O}}(1)$ factors). In particular, we show
the following.

  * •

There exists an algorithm that solves the single sources shortest paths
problem with stretch $(1\\!+\\!\varepsilon)$ w.h.p. in
$\smash{\widetilde{O}}(1)$ rounds in the $\mathsf{HYBRID}$ model (Theorem 4).

  * •

There exists an algorithm that solves the $k$ random sources shortest paths
problem with stretch $(1\\!+\\!\varepsilon)$ w.h.p. in
$\smash{\widetilde{O}}\big{(}\\!\sqrt{k}\big{)}$ rounds in the
$\mathsf{HYBRID}$ model (Thm. 11).

  * •

There exists an algorithm that solves the $k$ sources shortest paths problem
with stretch $(3\\!+\\!\varepsilon)$ w.h.p. in
$\smash{\widetilde{O}}\big{(}\\!\sqrt{k}\big{)}$ rounds in the
$\mathsf{HYBRID}$ model (Theorem 11).

The currently fastest algorithms for constant stretch SSSP are by [11] which
takes $\smash{O}(n^{\varepsilon})$ rounds (where $\varepsilon$ is required to
be constant to keep a constant stretch) and by [20] for stretch
$1\\!+\\!\varepsilon$ in $\smash{\widetilde{O}}(n^{5/17})$ rounds. Both
solutions are exponentially slower than the $1\\!+\\!\varepsilon$
approximation proposed in this work. The known lower bound for $k$-SSP of
$\smash{\widetilde{\Omega}}\big{(}\\!\sqrt{k}\big{)}$, which holds even for
randomized algorithms and extremely large stretch in
$\Omega\big{(}\\!\sqrt{n}\big{)}$ was matched (up to
$\smash{\widetilde{O}}(1)$ factors) for $k\geq n^{2/3}$ by a series of
articles [11, 42, 19], with varying, constant stretches. However, tight
algorithms below this threshold for $k$ have been elusive and this work
answers the question whether the lower bound of
$\smash{\widetilde{\Omega}}\big{(}\\!\sqrt{k}\big{)}$ can be matched for
$k<n^{2/3}$ positively. The current complexity landscape of the $k$-SSP
problem in $\mathsf{HYBRID}$ is given by Figure 1. Furthermore, we generalize
our solutions for $k$-SSP for the $\mathsf{HYBRID}(\infty,\gamma)$ model and
show that approximations can be obtained in
$\smash{\widetilde{O}}\big{(}\\!\sqrt{k/\gamma}\big{)}$ rounds222Note that
this is also tight up to $\smash{\widetilde{O}}(1)$ factors due to a matching
lower bound of $\smash{\widetilde{O}}\big{(}\\!\sqrt{k/\gamma}\big{)}$ by [55]
for $k$-SSP, which is a slight generalization of the lower bound of [42].
(details in Theorem 11), demonstrating the benefit of larger global capacity
for solving $k$-SSP.

In terms of technical contributions, we show that an interface model called
$\mathsf{Minor}$-$\mathsf{Aggregation}$ and an oracle to solve the
$\mathsf{Eulerian}$-$\mathsf{Orientation}$ problem that were introduced by
[53] (for SSSP solutions in the $\mathsf{PRAM}$ model), can be efficiently
implemented in the $\mathsf{HYBRID}$ model, which might be useful in case
other problems have fast solutions in this interface model. Furthermore, we
show that multiple graph algorithms can be scheduled efficiently in parallel
on an appropriately sized skeleton graph. This is useful for our purposes
since we can reduce $k$-SSP to multiple instances of SSSP on such a skeleton
graph, but might prove equally useful for other graph problems that can be
broken into smaller problems on skeleton graphs in a similar way.

##  2 Almost Optimal SSSP in Polylogarithmic Time

In this section we show how to obtain an almost optimal
$\smash{\widetilde{O}}(1)$ round algorithm for the $\mathsf{HYBRID}$ model by
adapting the techniques of [53]. In particular, we will prove the following
theorem.

######  Theorem 4.

A $(1\\!+\\!\varepsilon)$-approximation of SSSP can be computed in
$\smash{\widetilde{O}}(1/\varepsilon^{2})$ rounds in the $\mathsf{HYBRID}$
model, w.h.p.

The goal of [53] is the computation of an almost shortest path tree in the
$\mathsf{PRAM}$ model with linear work and $\smash{\widetilde{O}}(1)$ depth.
Their main machinery is the simulation of an interface model, called
$\mathsf{Minor}$-$\mathsf{Aggregation}$ model, defined as follows. Let
$G=(V,E)$ an undirected input graph. In a difference to the synchronous
message passing model (Definition 1) nodes and edges are assumed to be
individual computational units that communicate in synchronous rounds and
conduct arbitrary local computations in each round. Initially, nodes know
their ID of size $\smash{\widetilde{O}}(1)$ and edges know the IDs of their
endpoints. Each round, communication occurs by conducting the following
operations (in that order).

  * •

Contraction: Each edge e chooses a value $c_{e}\in\\{\top,\bot\\}$, which
defines a minor network $G^{\prime}=(V^{\prime},E^{\prime})$ where all edges
with $c_{e}=\top$ are contracted. This forms a set supernodes
$V^{\prime}\subseteq 2^{V}$, where a supernode $s\in V^{\prime}$ consists of
nodes connected by contracted edges. For each $e\in E$ that connects nodes of
distinct supernodes, there is a corresponding edge in $E^{\prime}$.

  * •

Consensus: Each $v\in V$ chooses a $\smash{\widetilde{O}}(1)$-bit value
$x_{v}$. For each supernode $s\in V^{\prime}$, let $y_{s}:=\bigoplus_{v\in
s}x_{v}$, where $\bigoplus$ is some pre-defined aggregation operator. All
$v\in s$ learn $y_{s}$.

  * •

Aggregation: Each edge $e\in E^{\prime}$ connecting supernodes $a\in
V^{\prime}$ and $b\in V^{\prime}$ learns $y_{a}$ and $y_{b}$, and chooses two
$\smash{\widetilde{O}}(1)$-bit values $z_{e,a}$, $z_{e,b}$ (i.e., one for each
endpoint). Every node $v\in s$ of each supernode $s\in V^{\prime}$ learns the
aggregate of its incident edges in $E^{\prime}$, i.e.,
$\bigotimes_{e\in\text{incidentEdges}(s)}z_{e,s}$ where $\bigotimes$ is some
pre-defined aggregation operator. All nodes $v\in s$ learn the same aggregate
value (if the aggregate is not unique).

The work of [53] shows that SSSP can be solved with a stretch of
$(1\\!+\\!\varepsilon)$ in $\smash{\widetilde{O}}(1/\varepsilon^{2})$ rounds
of the $\mathsf{Minor}$-$\mathsf{Aggregation}$ model, if it can call on an
oracle $\mathcal{O}^{\text{Euler}}$ that solves the
$\mathsf{Eulerian}$-$\mathsf{Orientation}$ problem once per round (we define
this oracle formally further below).

######  Lemma 5 (cf., [53]).

A $(1\\!+\\!\varepsilon)$-approximation of SSSP on $G$ can be computed with a
total of $\smash{\widetilde{O}}\big{(}1/\varepsilon^{2}\big{)}$ rounds of
$\mathsf{Minor}$-$\mathsf{Aggregation}$ model and calls to the oracle
$\mathcal{O}^{\text{Euler}}$ on certain Eulerian graphs $H$ (see Definition
8), respectively.

Our goal is to apply this lemma to show Theorem 4. For this we have to prove
that we can (1) efficiently simulate the
$\mathsf{Minor}$-$\mathsf{Aggregation}$ model in $\mathsf{HYBRID}$ and (2)
efficiently implement the oracle $\mathcal{O}^{\text{Euler}}$ in
$\mathsf{HYBRID}$.

###  2.1 Simulation of $\mathsf{Minor}$-$\mathsf{Aggregation}$ in
$\mathsf{HYBRID}$

We show in the following that the $\mathsf{Minor}$-$\mathsf{Aggregation}$
model can be implemented efficiently in the $\mathsf{HYBRID}$ model. One of
the techniques we employ is the following result by [32], which states that an
“overlay network” can be computed with diameter, degree and round complexity
$\smash{\widetilde{O}}(1)$.

######  Lemma 6 (see [32]).

Given that nodes know their neighbors in a graph $G=(V,E)$ as problem input
and a polynomial upper bound of $n$, a rooted tree $T=(V,E_{T})$ (usually not
a sub-graph of $G$) with constant degree and diameter $\smash{O}(\log n)$ can
be computed in $\smash{O}(\log n)$ rounds, w.h.p., in the $\mathsf{HYBRID}$
model ($\mathsf{NCC}$ suffices).

We proceed with the simulation of the $\mathsf{Minor}$-$\mathsf{Aggregation}$
model in $\mathsf{HYBRID}$.

######  Lemma 7.

A round of the $\mathsf{Minor}$-$\mathsf{Aggregation}$ model can be simulated
in $\smash{\widetilde{O}}(1)$ rounds in the $\mathsf{HYBRID}$ model, w.h.p.

###### Proof.

Since nodes in the distributed model are computationally unlimited, each edge
can be simulated by both of its endpoints simultaneously. We compute a tree
$T_{s}$ with diameter, degree and round complexity $\smash{\widetilde{O}}(1)$
on each connected component $s\in V^{\prime}$ using the set of contracted
edges ($e\in E$ with $c_{e}=\top$) as input, see Lemma 6. Note that the small
diameter and degree of $T_{s}$ allows us efficient computation of aggregation
operations by conducting converge-casts on $T_{s}$ in
$\smash{\widetilde{O}}(1)$ rounds. This also allows us to implement the
consensus step by converge casting the values $y_{s}$ of for all $s\in
V^{\prime}$ to all $v\in s$.

As part of the simulation, we assume that each edge $e=\\{s_{1},s_{2}\\}\in
E^{\prime}$ is simulated by both of its incident nodes $v_{1}\in
s_{1},v_{2}\in s_{2}$. The values $y_{s_{1}},y_{s_{2}}$ from the consensus
step can be exchanged between $v_{1},v_{2}$ with their shared edge in a single
round so both can continue the correct simulation of $e$. This is required in
order to choose values $z_{e,a}$, $z_{e,b}$, which may depend on
$y_{s_{1}},y_{s_{2}}$. The aggregation of values $z_{e,s}$ of all $e\in
E^{\prime}$ incident to some $s\in V^{\prime}$ is implemented as before. ∎

###  2.2 Implementation of the Oracle $\mathcal{O}^{\text{Euler}}$

The oracle $\mathcal{O}^{\text{Euler}}$ solves the
$\mathsf{Eulerian}$-$\mathsf{Orientation}$ problem on certain Eulerian graphs
$H$ (i.e., graphs containing an Eulerian cycle), which requires that all edges
are oriented such that in- and out-degree of each node are equal. More
specifically, the requirements towards the oracle $\mathcal{O}^{\text{Euler}}$
in conjunction with the input graph $G$ (the one which we want to solve SSSP
on) are as follows.

######  Definition 8.

Let $H$ be an Eulerian graph that is a sub-graph of some $H^{\prime}$, where
$H^{\prime}$ is obtained by adding at most $\smash{\widetilde{O}}(1)$
arbitrarily connected “virtual” nodes to $G$. Virtual edges, i.e., edges
incident to at least one virtual node, are given in distributed form: an edge
between a virtual and a real node is known by the latter, and edges between
two virtual nodes are known by every node. Then $\mathcal{O}^{\text{Euler}}$
outputs an orientation of edges of $H$ such that in- and out-degree of each
node are equal.

Our goal is to show that we can also efficiently implement a call of
$\mathcal{O}^{\text{Euler}}$ in $\mathsf{HYBRID}$. Our goal is to re-purpose
the PRAM-model algorithm by [9] for this task. The $\mathsf{PRAM}$ model
assumes multiple processors and a shared memory containing the input.
Processors can write or read a memory cell in each step subject to some
restrictions. Each cell may contain a real value but in the SSSP problem with
polynomially bounded, integer weights, $\smash{\widetilde{O}}(1)$ bits per
cell suffice. The performance of a $\mathsf{PRAM}$ algorithm is measured in
the total number of processing steps $N$ (work) and the marginal number of
required parallel steps $T$ (depth) if an arbitrary number of processors can
be used. In the exclusive read, exclusive write variant (EREW) each memory
cell can be read or written by at most one processor in each step.

Since the memory is the only means by which processors can exchange
information, intuitively, an EREW $\mathsf{PRAM}$ algorithm that uses at most
$\smash{\widetilde{O}}(n)$ processors and memory cells can be simulated in
$\smash{\widetilde{O}}(1)$ rounds via the $\mathsf{NCC}$ model, where each
node simulates $\smash{\widetilde{O}}(1)$ processors and cells of the shared
memory and exclusive access to each cell is provided via the global network
($\mathsf{NCC}$ model). The simulation of $\mathsf{PRAM}$ algorithms in
$\mathsf{HYBRID}$ requires $\smash{\widetilde{O}}(N/n+T)$ rounds if each node
has the same amount of cells to simulate.

In [27] it is shown that the simulation of EREW $\mathsf{PRAM}$ can also be
done if the input is the local network $G$, however this adds a term of
$\smash{\widetilde{O}}(a)$ to the running time, where $a$ is the arboricity of
$G$,333The arboricity of $G$ is defined as the smallest number of forests
required to cover all edges of $G$. which reflects imbalances in the number of
memory cells that nodes must simulate. Note that $a$ can be linear in $n$.
Their result carries over to the concurrent read/write (CRCW) variant, which
can be simulated with EREW incurring only $\smash{\widetilde{O}}(1)$ slowdown.
The result of [27] implies the following lemma.

######  Lemma 9 (cf. [27]).

A CRCW $\mathsf{PRAM}$ algorithm that solves a graph problem on $G=(V,E)$ with
depth $T$ using $n=|V|$ processors can be simulated in
$\smash{\widetilde{O}}(a)$ rounds in the $\mathsf{HYBRID}$ model, w.h.p.,
where $a$ equals the arboricity of $G$.

We break the problem of Eulerian orientation down to sub problems with
suitable properties so that in a final step we can efficiently simulate the
PRAM-model algorithm by [9].

######  Lemma 10.

A call of the oracle $\,\mathcal{O}^{\text{Euler}}$ (see Definition 8) can be
implemented in $\smash{\widetilde{O}}(1)$ rounds in the $\mathsf{HYBRID}$
model.

###### Proof.

There is a CRCW $\mathsf{PRAM}$ algorithm that solves the
$\mathsf{Eulerian}$-$\mathsf{Orientation}$ problem with linear work
$\smash{\widetilde{O}}(n\\!+\\!m)$ ($m:=|E|$) and depth
$\smash{\widetilde{O}}(1)$ [9]. Note that in the $\mathsf{PRAM}$ simulation we
can safely ignore the fact that some nodes and edges in $H$ are virtual (see
Def. 8 for the definition of $H$), because these add at most
$\smash{\widetilde{O}}(1)$ nodes and $\smash{\widetilde{O}}(n)$ edges, which
can be evenly distributed and simulated by real nodes. Our goal is to reduce
the problem into sub-problems on sub-graphs of smaller arboricity using the
local network, which admits a solution in $\smash{\widetilde{O}}(1)$ rounds
simulating the $\mathsf{PRAM}$ algorithm by [9] using the simulation in
$\mathsf{HYBRID}$ (Lemma 9).

The idea is to reduce the arboricity of $H$ by greedily orienting disjoint
cycles in $H$ on small subgraphs in parallel, which will ultimately leave us
with a remaining graph of yet unoriented edges with small arboricity. Note
that by orienting disjoint cycles consistently in one direction, the remaining
graph of unoriented edges retains even node degree, i.e., it still has an
$\mathsf{Eulerian}$-$\mathsf{Orientation}$. To identify disjoint cycles
efficiently, we first compute a $(\chi,D)$-network decomposition. This is a
partition of nodes into clusters of diameter $D$ such that the cluster graph
(where two clusters are incident if a pair of nodes from each cluster are
incident) has a valid $\chi$-coloring. A network decomposition with
$D,\chi\in\smash{O}(\log n)$ can be computed in $\smash{\widetilde{O}}(1)$
rounds in the local network ($\mathsf{LOCAL}$), see [48].

However, we compute such a network decomposition not on $G$, but on the power
graph $G^{2}=(V,E^{\prime})$, where any two nodes in $V$ at distance at most
$2$ hops in $G$ share an edge in $E^{\prime}$. Note that the round complexity
is asymptotically the same as computing the network decomposition of $G$,
since $G^{2}$ can be simulated in $2$ rounds in the local network. Let $C$ be
a cluster of the network decomposition of $G^{2}$. Since two nodes in
different clusters of the same color can not be incident in $G^{2}$, the
distance in the original network $G$ between such two nodes of must bigger
than $2$. Let $C^{\prime}$ be the extended cluster of $C$, defined as $C$ and
all nodes within one hop of $C$. Note, due to the aforementioned distance
property any two such extended clusters of the same color are node-disjoint.

For each color in $[\chi]$ and for each cluster $C$ with that color in
parallel, all nodes in the extended cluster $C^{\prime}$ learn $C^{\prime}$ in
$D\in\smash{O}(\log n)$ steps via the local network. This knowledge enables
all nodes in $C^{\prime}$ to consistently orient and greedily remove all
cycles (w.r.t. $G$) in $C^{\prime}$. Note that edges that are nominally
removed will still be used to communicate in $C^{\prime}$. Further, we can do
this for each extended cluster $C^{\prime}$ of the current color in parallel
since they do not overlap. Each extended cluster is now cycle-free, thus all
edges in all extended clusters of that color can be covered by a single
forest. Since each node is in some cluster $C$ of some color, both endpoints
of any edge that was not removed are within some extended cluster
$C^{\prime}$, thus in the end all edges are covered by some forest. The number
of forests $a$ corresponds to the number of colors $\chi\in\smash{O}(\log n)$.
Thus the remaining graph can be oriented with the simulation of [27] to run
the $\mathsf{PRAM}$ algorithm by [9] in $\smash{\widetilde{O}}(1)$ rounds. ∎

We can now apply our implementation of the
$\mathsf{Minor}$-$\mathsf{Aggregation}$ model and the oracle
$\mathcal{O}^{\text{Euler}}$ in $\mathsf{HYBRID}$ to the result by [53],
hence, Theorem 4 is proven by combining Lemma 5, Lemma 7 and Lemma 10.

##  3 Shortest Paths with Multiple Sources

In this section we give a direct application for the fast SSSP algorithm from
the previous section by providing a framework to efficiently schedule multiple
algorithms in parallel on a so called skeleton graph. Since our algorithmic
solutions scale with the amount of global communication that we permit, we
also give solutions for the more general $\mathsf{HYBRID}(\infty,\gamma)$
model. In particular, we show that
$\smash{\widetilde{O}}\big{(}\\!\sqrt{k/\gamma}\big{)}$ rounds suffice to
compute approximations (given that the precision parameter $\varepsilon$ is
constant). The claim for the standard $\mathsf{HYBRID}$ model is implied by
substituting $\gamma=\log^{2}n$. Note that the general result is also tight
(up to $\smash{\widetilde{O}}(1)$ factors), as the lower bound of
$\smash{\widetilde{\Omega}}\big{(}\\!\sqrt{k}\big{)}$ by [42] can be
generalized to $\smash{\widetilde{\Omega}}\big{(}\\!\sqrt{k/\gamma}\big{)}$
(see [55]).

######  Theorem 11.

Let $\varepsilon>0$. The $k$-SSP problem can be approximated w.h.p.

  * •

in $\mathsf{HYBRID}$ in
$\smash{\widetilde{O}}\big{(}\\!\sqrt{k}\cdot\tfrac{1}{\varepsilon^{2}}\big{)}$
rounds for stretch $1\\!+\\!\varepsilon$ and $k$ i.i.d. _random_ sources,

  * •

in $\mathsf{HYBRID}(\infty,\gamma)$ in
$\smash{\widetilde{O}}\big{(}\\!\sqrt{k/\gamma}\cdot\tfrac{1}{\varepsilon^{2}}\big{)}$
rounds for stretch $3\\!+\\!\varepsilon$ and $k$ arbitrary sources,

  * •

in $\mathsf{HYBRID}(\infty,\gamma)$ in
$\smash{\widetilde{O}}\big{(}\tfrac{1}{\varepsilon^{2}}\big{)}$ rounds for
stretch $1\\!+\\!\varepsilon$ and $k\leq\gamma$ arbitrary sources.

###  3.1 Parallel Scheduling of Algorithms on a Skeleton Graph

Besides the scheme for SSSP introduced in Section 2, our main technical
component is to show that we can efficiently run multiple instances of
independent algorithms on a so called skeleton graph in parallel. A skeleton
graph consists of skeleton nodes that are sampled with probability $1/x$ from
$V$. Skeleton edges are created between skeleton nodes that have a path of
length roughly $\smash{\widetilde{O}}(x)$ in $G$ between them with the weight
of such an edge corresponding to the distance of that path. Such a skeleton
graph has many useful properties, the main ones are that it preserves
distances of $G$ and can be computed efficiently in a distributed sense, where
each skeleton node knows its incident skeleton edges in
$\smash{\widetilde{O}}(x)$ rounds. The formal definition is given as follows.

######  Definition 12 (cf. [56, 11]).

A skeleton graph $\mathcal{S}=(V_{\mathcal{S}},E_{\mathcal{S}})$ of $G$, is
obtained by sampling each node of $G$ to $V_{\mathcal{S}}$ with prob. at least
$\frac{1}{x}$. The edges of $\mathcal{S}$ are
$E_{\mathcal{S}}\\!=\\!\\{\\{u,v\\}\\!\mid\\!u,v\\!\in\\!V_{\mathcal{S}},\text{hop}(u,v)\\!\leq\\!h\\}$
(for some appropriate $h\in\smash{\widetilde{O}}(x)$) with weights
$w_{\mathcal{S}}(u,v)=d_{h,G}(u,v)$ for $\\{u,v\\}\in E_{\mathcal{S}}$.

In [10] it is shown that $\mathcal{S}$ gives a good approximation of the
topology of the graph, in particular, that the distance between sampled nodes
in the resulting skeleton graph equals the actual distance in the local graph
w.h.p.

######  Lemma 13 (cf. [10]).

A skeleton graph $\mathcal{S}=(V_{\mathcal{S}},E_{\mathcal{S}})$ as given in
Definition 12 can be constructed in $h\in\smash{\widetilde{O}}(x)$ rounds in
the $\mathsf{LOCAL}$ (and thus $\mathsf{HYBRID}$) model w.h.p. for an
appropriately chosen $h\in\smash{\widetilde{\Theta}}(x)$ with the following
properties. (a) For any $u,v\\!\in\\!V$ with $hop(u,v)\\!\geq\\!h$, there is a
shortest path $P$ from $u$ to $v$, s.t. any sub-path $Q$ of $P$ with at least
$h$ nodes contains a node in $V_{\mathcal{S}}$ w.h.p. (b) For all $u,v,\in
V_{\mathcal{S}}:$ $d_{\mathcal{S}}(u,v)=d_{G}(u,v)$ w.h.p.

Furthermore, for efficient scheduling of algorithms in parallel we also
require the concept of so called helper sets that have been introduced in
[42]. The rough idea is, when given a set of nodes that have been sampled
i.i.d., one can assign each sampled node a set of helper nodes of a certain
size within some small distance, which essentially marks the spot where
distance and neighborhood size (with respect to some “load” $x$) are in a
balance. We parameterize the definition of helper sets from [42] as follows.

######  Definition 14 (cf. [42]).

Let $G=(V,E)$ be a graph, let $x<n$ and assume $W\subseteq V$ was sampled
i.i.d. from $V$ with prob. $1/x$. A family $\\{H_{w}\subseteq V\mid w\in W\\}$
of _helper sets_ fulfills the following properties for all $w\in W$ and some
integer $\mu\in\smash{\smash{\widetilde{\Theta}}(x)}$. (1) Each $H_{w}$ has
size at least $\mu$. (2) For all $u\in H_{w}$ it holds that $hop(w,u)\leq\mu$.
(3) Each node is member of at most $\smash{\widetilde{O}}(1)$ sets $H_{w}$.

The computation of helper sets by [42] works out of the box and we are going
to utilize it in the following form.

######  Lemma 15 (see [42]).

A family of helper sets $\\{H_{w}\subseteq V\mid w\in W\\}$ as given in
Definition 14 can be computed w.h.p. in $\smash{\widetilde{O}}\big{(}x\big{)}$
rounds.

We are now ready to prove the following theorem.

######  Theorem 16.

Let $\gamma<k<n$ and let $\mathcal{S}$ be a skeleton graph of the local graph
$G$ with sampling probability $\sqrt{\gamma/k}$ (see Definition 12). Let
$\mathcal{A}_{1},\dots,\mathcal{A}_{k}$ be $\mathsf{HYBRID}$ algorithms
operating on $\mathcal{S}$ with round complexity at most $T$. Then
$\mathcal{S}$ can be constructed and $\mathcal{A}_{1},\dots,\mathcal{A}_{k}$
can be executed on $\mathcal{S}$ in
$\smash{\widetilde{O}}\big{(}\sqrt{k/\gamma}\cdot T\big{)}$ rounds of the
$\mathsf{HYBRID}(\infty,\gamma)$ model w.h.p.

###### Proof.

The first step is to compute the skeleton graph
$S=(V_{\mathcal{S}},E_{\mathcal{S}})$ as defined in Definition 12 with
sampling probability $\sqrt{\gamma/k}$, which takes
$\smash{\widetilde{O}}\big{(}\\!\sqrt{k/\gamma}\big{)}$ rounds and guarantees
$d_{\mathcal{S}}(u,v)=d_{G}(u,v)$ for all $u.v\in V_{\mathcal{S}}$ w.h.p., by
Lemma 13. As second step, we compute helper sets for $V_{\mathcal{S}}$, which
assign each $u\in V_{\mathcal{S}}$ a set $H_{u}\subseteq V$ such that (1)
$|H_{u}|\in\smash{\widetilde{\Theta}}\big{(}\\!\sqrt{k/\gamma}\big{)}$ and (2)
$\max_{v\in
H_{u}}\\!\operatorname{hop}(u,v)\in\smash{\widetilde{\Theta}}\big{(}\\!\sqrt{k/\gamma}\big{)}$
and (3) each $v\in V$ is member of $\smash{\widetilde{O}}(1)$ helper sets.
This is accomplished w.h.p. in
$\smash{\widetilde{O}}\big{(}\\!\sqrt{k/\gamma}\big{)}$ rounds by Lemma 15.

Note that $\mathcal{S}$ is established in a distributed sense, where each
skeleton edge is known by its incident skeleton nodes. The third step is to
transmit the incident edges and the input w.r.t. each algorithm
$\mathcal{A}_{i}$ of $u\in\mathcal{S}$ to its helpers $H_{u}$ using the local
network, which takes $\smash{\widetilde{O}}\big{(}\\!\sqrt{k/\gamma}\big{)}$
rounds due to (2). This gives each helper $v\in H_{u}$ all the required
information to simulate any $\mathcal{A}_{i}$ on $\mathcal{S}$ on $u$’s
behalf, if also provided with the messages that $u$ receives during the
execution of $\mathcal{A}_{i}$.

In the fourth step, the simulation of the algorithms $\mathcal{A}_{i}$ for
node $u\in\mathcal{S}$ is distributed among all helpers $H_{u}$ in a balanced
fashion, that is, each helper $v\in H_{u}$ is assigned at most $\ell\leq\lceil
k/|H_{u}|\rceil\in\smash{\widetilde{O}}\big{(}\\!\sqrt{k\gamma}\big{)}$
algorithms $\mathcal{A}_{i}$ to simulate (where $\ell$ is uniform for all
helper sets). In particular, we enumerate helpers $H_{u}$ with indices $v_{j}$
and assign algorithms $\mathcal{A}_{\ell(j-1)+1},\dots,\mathcal{A}_{\ell j}$
to $v_{j}$. Furthermore, for each edge $\\{u,u^{\prime}\\}\in E_{\mathcal{S}}$
and each $\mathcal{A}_{i}$, we pair up the helper $v_{j}\in H_{u}$ that
simulates $\mathcal{A}_{i}$ for $u$ with the helper $v_{j}^{\prime}\in
H_{u^{\prime}}$ that simulates $\mathcal{A}_{i}$ for $u^{\prime}$. By
Definitions 12 and 14 (regarding the distances between helpers and between
incident skeleton nodes) and the triangle inequality it holds that

$\operatorname{hop}(v_{j},v_{j}^{\prime})\leq\operatorname{hop}(v_{j},u)+\operatorname{hop}(u,u^{\prime})+\operatorname{hop}(u^{\prime},v_{j}^{\prime})\in\smash{\smash{\widetilde{O}}\big{(}\\!\sqrt{k/\gamma}\big{)}}$

and therefore step four can be coordinated in
$\smash{\widetilde{O}}\big{(}\\!\sqrt{k/\gamma}\big{)}$ rounds via the local
network. It remains to coordinate the message exchange among helpers that
simulate some $\mathcal{A}_{i}$ for some skeleton node $u\in\mathcal{S}$. In
the first round, all outgoing messages can be computed locally by helpers
$v_{j}\in H_{u}$ based on the input they received from $u$. In general, we
presume that the simulation and computation of outgoing messages was correct
up to the current round. It suffices to show the correct transmission of all
messages for all simulated algorithms for the next round.

Messages via the local network $\mathcal{S}$: The hop-distance between helpers
$v_{j},v_{j}^{\prime}$ that simulate $\mathcal{A}_{i}$ for two skeleton nodes
that are adjacent in $\mathcal{S}$ nodes is
$\operatorname{hop}(v_{j},v^{\prime}_{j})\in\smash{\widetilde{O}}\big{(}\\!\sqrt{k/\gamma}\big{)}$.
Hence, the local messages can be transmitted in the same number of rounds
using the unlimited local network. Messages via the global network: each
helper is assigned at most
$\ell\in\smash{\widetilde{O}}\big{(}\\!\sqrt{k\gamma}\big{)}$ algorithms to
simulate. Since each helper has a global capacity of $\gamma$ all global
messages can be sent sequentially in
$\smash{\widetilde{O}}\big{(}\\!\sqrt{k\gamma}/\gamma\big{)}=\smash{\widetilde{O}}\big{(}\\!\sqrt{k/\gamma}\big{)}$
rounds. Due to the canonical assignment of algorithms $\mathcal{A}_{i}$ to
helpers $v_{j}$, no helper will receive more messages than it sends in each
round.

Consequently, each helper can simulate a single round of all assigned
$\mathcal{A}_{i}$ in $\smash{\widetilde{O}}\big{(}\\!\sqrt{k/\gamma}\big{)}$
rounds, thus it takes $\smash{\widetilde{O}}\big{(}\\!\sqrt{k/\gamma}\cdot
T\big{)}$ rounds to complete the simulation of all $\mathcal{A}_{i}$. Finally,
any output that was computed by some helper $v_{j}\in H_{u}$ in the simulation
of $\mathcal{A}_{i}$ can be transmitted back to $u$ in
$\smash{\widetilde{O}}\big{(}\\!\sqrt{k/\gamma}\big{)}$ rounds via the local
network. ∎

###  3.2 Solving the $k$-SSP Problem

We can now employ the procedure from Section 3.1 to schedule $k$ instances of
the SSSP algorithm from Section 2 on an appropriately sized skeleton graph
$\mathcal{S}$, which allows us to solve $k$-SSP for the case that the sources
are part of the skeleton $\mathcal{S}$.

######  Lemma 17.

Let $\gamma<k<n$ and let $\mathcal{S}=(V_{\mathcal{S}},E_{\mathcal{S}})$ be a
skeleton graph of the local graph $G$ with sampling probability
$\sqrt{\gamma/k}$ (see Definition 12). Provided that all sources are in
$V_{\mathcal{S}}$ we can solve the $k$-SSP problem with stretch
$1\\!+\\!\varepsilon$ in
$\smash{\widetilde{O}}\big{(}\\!\sqrt{k/\gamma}\cdot\tfrac{1}{\varepsilon^{2}}\big{)}$
rounds of the $\mathsf{HYBRID}(\infty,\gamma)$ model w.h.p.

###### Proof.

Let $K\subseteq V_{\mathcal{S}}$ be the set of $k$ source nodes. Let
algorithms $\mathcal{A}_{s}$ be an instance of the SSSP algorithm from Section
2 for some source $s\in K$. By Theorem 4 the algorithms $\mathcal{A}_{s}$ have
a native round complexity of
$\smash{\widetilde{O}}(\tfrac{1}{\varepsilon^{2}})$ to compute an
approximation with stretch $1\\!+\\!\varepsilon$. We apply Theorem 16 to
schedule all $\mathcal{A}_{s},s\in K$ on $\mathcal{S}$ in parallel in
$\smash{\widetilde{O}}\big{(}\\!\sqrt{k/\gamma}\cdot\frac{1}{\varepsilon^{2}}\big{)}$
rounds. After conducting this procedure, every skeleton node $u\in
V_{\mathcal{S}}$ knows a stretch $1\\!+\\!\varepsilon$ distance approximation
$\smash{\widetilde{d}}_{\mathcal{S}}(u,s)$ for every $s\in K$.

In a post-processing step, each node $v\in V$ that is not part of the skeleton
$\mathcal{S}$ computes its own distance to each source as follows. For this we
utilize that edges $E_{\mathcal{S}}$ correspond to paths of at most
$h\in\smash{\widetilde{O}}\big{(}\\!\sqrt{k/\gamma}\big{)}$ hops in $G$.
First, node $v$ retrieves its distance information to each source from all
skeleton nodes within $h$ hops, i.e., in
$\smash{\widetilde{O}}(\sqrt{k/\gamma})$ rounds. For each source $s\in K$,
node $v$ computes
$\smash{\widetilde{d}}(v,s):=\min_{u\in\mathcal{S}}d_{h,G}(v,u)+\smash{\widetilde{d}}_{\mathcal{S}}(u,s)$.
By Lemma 13 (a) there is a shortest path from $v$ to $s$ which has a skeleton
node $u\in V_{\mathcal{S}}$ within $h$ hops of $v$ w.h.p. For this particular
skeleton node $u$ we have

$\displaystyle\smash{\widetilde{d}}(v,s)$ $\displaystyle\hskip
11.66563pt\leq\hskip
11.09654ptd_{h,G}(v,u)+\smash{\widetilde{d}}_{\mathcal{S}}(u,s)$
$\displaystyle\hskip 4.55244pt\stackrel{{\scriptstyle
Thm.\ref{thm:almost_shortest_sssp}}}{{\leq}}\hskip
4.55244ptd_{h,G}(v,u)+(1\\!+\\!\varepsilon)d_{\mathcal{S}}(u,s)$
$\displaystyle\\!\stackrel{{\scriptstyle Lem.\ref{lem:skeleton-
graph}(b)}}{{=}}d_{h,G}(v,u)+(1\\!+\\!\varepsilon)d_{G}(u,s)$
$\displaystyle\hskip 11.66563pt\leq\hskip
11.09654pt(1\\!+\\!\varepsilon)\big{(}d_{h,G}(v,u)+d_{G}(u,s)\big{)}\phantom{\stackrel{{\scriptstyle
Lem.\ref{lem:skeleton-graph}(b)}}{{=}}}$
$\displaystyle\\!\stackrel{{\scriptstyle Lem.\ref{lem:skeleton-
graph}(a)}}{{\leq}}(1\\!+\\!\varepsilon)d_{G}(v,s).$ ∎

Finally, we show that solving $k$-SSP on the skeleton $\mathcal{S}$ can also
be used to obtain good approximations for more general cases of the $k$-SSP
problem on the local graph $G$ with the different trade offs as stated in
Theorem 11.

###### Proof of Theorem 11.

The case $k\leq\gamma$ is the simplest. Here, we have enough available global
capacity in $\mathsf{HYBRID}(\infty,\gamma)$ to execute the $k$
$\mathsf{HYBRID}$ SSSP algorithms in parallel in
$\smash{\widetilde{O}}(\tfrac{1}{\varepsilon^{2}})$ rounds (Theorem 4), since
each such algorithm requires only $\smash{\widetilde{O}}(1)$ global capacity
per round and the local capacity is unlimited.

In the remaining proof we assume $\gamma<k$. Let $\mathcal{S}$ be a skeleton
graph with skeleton nodes $V_{\mathcal{S}}$ sampled with probability
$\sqrt{\gamma/k}$ and edges $E_{\mathcal{S}}$ that correspond to paths of at
most $h\in\smash{\widetilde{O}}\big{(}\\!\sqrt{k/\gamma}\big{)}$ hops in $G$,
which can be computed in
$\smash{\widetilde{O}}\big{(}\\!\sqrt{k/\gamma}\big{)}$ rounds (see Definition
12 and Lemma 13). Let $K\subseteq V_{\mathcal{S}}$ be the set of $k$ source
nodes.

Consider the case where $K$ was sampled i.i.d. from $V$ and where we are
interested in the standard $\mathsf{HYBRID}$ model, i.e.,
$\gamma\in\smash{\widetilde{O}}(1)$. We make a distinction on the size of $k$.
For a large number of sources $k\geq n^{2/3}$ we apply the known $k$-SSP
algorithm by [20] whose round complexity is
$\smash{\widetilde{O}}(n^{1/3}+\sqrt{k})$, which equals
$\smash{\widetilde{O}}(\\!\sqrt{k})$ for $k$ above this threshold and even
provides an exact solution.

If the number of sources is small $k\leq n^{2/3}$ we add $K$ to
$V_{\mathcal{S}}$ and conduct the construction of the skeleton edges with the
set $K$ in addition to the sampled nodes. Since each node has a-priori the
same chance to be drafted to the skeleton either by being sampled or as a
random source, the property of an i.i.d. selection of nodes is retained. Note
that $|V_{\mathcal{S}}|\in\smash{\widetilde{\Theta}}\big{(}n/\sqrt{k}\big{)}$
w.h.p. before adding the sources $K$ to $V_{\mathcal{S}}$ (due to the sampling
probability $\smash{\widetilde{O}}\big{(}1/\sqrt{k}\big{)}$ and w.h.p. by
applying a Chernoff bound). The number of sources added to $V_{\mathcal{S}}$
can be bounded by $k\leq n^{2/3}=n/n^{1/3}\leq n/\sqrt{k}$. Thus adding $K$ to
$V_{\mathcal{S}}$ only changes the size of $|V_{\mathcal{S}}|$ by a
$\smash{\widetilde{O}}(1)$ factor. Therefore, we can apply Lemma 17 to obtain
a $1\\!+\\!\varepsilon$ approximation of $k$-SSP on $G$ with $k\leq n^{2/3}$
random sources.

Finally, consider the case where the $k$ sources are chosen arbitrarily. We
have to deal with the fact that these might be highly concentrated in a local
neighborhood and can therefore not simply be added to the skeleton as this
leads to difficulties with scheduling the SSSP algorithms (even assuming
$k\leq n^{2/3}$ does not help here). We employ technique similar to [43],
where each source $s\in K$ tags its closest skeleton node
$u_{s}:=\operatorname*{arg\,min}_{w\in V_{\mathcal{S}}}d_{h,G}(s,w)$ as its
proxy source in $\mathcal{S}$ (note that $u_{s}$ is within
$h\in\smash{\widetilde{O}}\big{(}\\!\sqrt{k}\big{)}$ hops of $s$ by Lemma 13
(a)).

Subsequently, we have $k^{\prime}\leq k$ skeleton nodes that are tagged as
proxy sources, which again allows us to compute $1\\!+\\!\varepsilon$
approximations for $k^{\prime}$-SSP on the proxy sources in
$\smash{\widetilde{O}}\big{(}\\!\sqrt{k/\gamma}\cdot\tfrac{1}{\varepsilon^{2}}\big{)}$
rounds using Lemma 17. To construct decent approximations to the real source
nodes we have to first make the distance $d_{h,G}(u_{s},s)$ from each source
$s\in K$ to its closest skeleton $u_{s}$ public knowledge.

For this we use the so called token dissemination routine (see [11]), which
solves the following problem. Nodes have tokens of size $\smash{O}(\log n)$
(in our case distance labels) which need to be broadcast to everyone. Given
that there are at most $x$ such tokens in the network and no node has more
than one token, [11] solves this in
$\smash{\widetilde{O}}\big{(}\\!\sqrt{x}\big{)}$ rounds in the
$\mathsf{HYBRID}$ model. In the $\mathsf{HYBRID}(\infty,\gamma)$ we can
exploit the higher global capacity by running
$y\in\smash{\widetilde{O}}(\gamma)$ such algorithms in parallel, where each
algorithm is responsible for broadcasting at most
$x\in\smash{\widetilde{O}}(k/\gamma)$ tokens, thus the round complexity is
$\smash{\widetilde{O}}\big{(}\\!\sqrt{k/\gamma}\big{)}$ (note that each token
can be assigned i.i.d., randomly to one of the $y$ parallel token
dissemination algorithms ensuring $x\in\smash{\widetilde{O}}(k/\gamma)$
w.h.p.).

Now each node $v\in V$ constructs its (approximate) distance to each source
$s\in S$ as follows. If there is a shortest path from $v$ to $s$ with at most
$h$ hops, then the local network suffices to find it in
$h\in\smash{\widetilde{O}}\big{(}\\!\sqrt{k/\gamma}\big{)}$ rounds. Else, $v$
computes $\hat{d}(v,s):=\smash{\widetilde{d}}(v,u_{s})+d_{h,G}(u_{s},s)$. Note
that there is a node $w\in V_{\mathcal{S}}$ within $h$ hops of $s$ on some
shortest path from $v$ to $s$. Due to the property of $u_{s}$ we have
$d_{h,G}(u_{s},s)\leq d_{h,G}(w,s)\leq d_{h,G}(v,s)$. We combine this with the
triangle inequality and obtain

$\displaystyle\hat{d}(v,s)$ $\displaystyle\hskip 11.66563pt=\hskip
11.09654pt\smash{\widetilde{d}}(v,u_{s})+d_{h,G}(u_{s},s)$
$\displaystyle\hskip 4.55244pt\stackrel{{\scriptstyle\text{Thm.
}\ref{thm:almost_shortest_sssp}}}{{\leq}}\hskip
4.55244pt(1\\!+\\!\varepsilon)d_{G}(v,u_{s})+d_{h,G}(u_{s},s)$
$\displaystyle\hskip 11.66563pt\leq\hskip
11.09654pt(1\\!+\\!\varepsilon)\big{(}d_{G}(v,w)+d_{G}(w,u_{s})+d_{h,G}(u_{s},s)\big{)}\phantom{\stackrel{{\scriptstyle
Lem.\ref{lem:skeleton-graph}(b)}}{{=}}}$ $\displaystyle\hskip
11.66563pt\leq\hskip
11.09654pt(1\\!+\\!\varepsilon)\big{(}d_{G}(v,w)+d_{G}(w,u_{s})+d_{h,G}(w,s)\big{)}\phantom{\stackrel{{\scriptstyle
Lem.\ref{lem:skeleton-graph}(b)}}{{=}}}$ $\displaystyle\hskip
11.66563pt=\hskip
11.09654pt(1\\!+\\!\varepsilon)\big{(}d_{G}(v,s)+d_{G}(w,u_{s})\big{)}\phantom{\stackrel{{\scriptstyle
Lem.\ref{lem:skeleton-graph}(b)}}{{=}}}$ $\displaystyle\hskip
11.66563pt\leq\hskip
11.09654pt(1\\!+\\!\varepsilon)\big{(}d_{G}(v,s)+d_{G}(w,s)+d_{G}(s,u_{s})\big{)}\phantom{\stackrel{{\scriptstyle
Lem.\ref{lem:skeleton-graph}(b)}}{{=}}}$ $\displaystyle\hskip
11.66563pt\leq\hskip
11.09654pt(1\\!+\\!\varepsilon)\big{(}3d_{G}(v,s)\big{)}\stackrel{{\scriptstyle\varepsilon^{\prime}:=3\varepsilon}}{{=}}(3\\!+\\!\varepsilon^{\prime})d_{G}(v,s).\phantom{\stackrel{{\scriptstyle
Lem.\ref{lem:skeleton-graph}(b)}}{{=}}}$ ∎

## References

  * [1] Amir Abboud, Keren Censor-Hillel, and Seri Khoury.  Near-linear lower bounds for distributed distance computations, even in sparse networks.  In 30th International Symposium on Distributed Computing (DISC), pages 29–42, 2016.
  * [2] Amir Abboud, Keren Censor-Hillel, Seri Khoury, and Ami Paz.  Smaller cuts, higher lower bounds.  ACM Transactions on Algorithms (TALG), 17(4):1–40, 2021.
  * [3] Udit Agarwal and Vijaya Ramachandran.  Distributed weighted all pairs shortest paths through pipelining.  In IEEE International Parallel and Distributed Processing Symposium (IPDPS), pages 23–32. IEEE, 2019.
  * [4] Udit Agarwal and Vijaya Ramachandran.  Faster deterministic all pairs shortest paths in congest model.  In ACM Symposium on Parallelism in Algorithms and Architectures (SPAA), pages 11–21, 2020.
  * [5] Udit Agarwal, Vijaya Ramachandran, Valerie King, and Matteo Pontecorvi.  A deterministic distributed algorithm for exact weighted all-pairs shortest paths in $\widetilde{O}(n^{3/2})$ rounds.  In Proc. of the 2018 ACM Symposium on Principles of Distributed Computing (PODC), pages 199–205, 2018.
  * [6] Ioannis Anagnostides and Themis Gouleakis.  Deterministic distributed algorithms and lower bounds in the hybrid model.  In 35th International Symposium on Distributed Computing, 2021.
  * [7] Alexandr Andoni, Aleksandar Nikolov, Krzysztof Onak, and Grigory Yaroslavtsev.  Parallel algorithms for geometric graph problems.  In Proceedings of the forty-sixth annual ACM symposium on Theory of computing, pages 574–583, 2014.
  * [8] Arash Asadi, Vincenzo Mancuso, and Rohit Gupta.  An sdr-based experimental study of outband d2d communications.  In IEEE INFOCOM 2016 - The 35th Annual IEEE International Conference on Computer Communications, pages 1–9, 2016.
  * [9] Mikhail Atallah and Uzi Vishkin.  Finding euler tours in parallel.  Journal of Computer and System Sciences, 29(3):330–337, 1984.
  * [10] John Augustine, Mohsen Ghaffari, Robert Gmyr, Kristian Hinnenthal, Christian Scheideler, Fabian Kuhn, and Jason Li.  Distributed computation in node-capacitated networks.  In Proc. 31st ACM Symp. on Parallelism in Algorithms and Architectures (SPAA), pages 69–79, 2019.
  * [11] John Augustine, Kristian Hinnenthal, Fabian Kuhn, Christian Scheideler, and Philipp Schneider.  Shortest paths in a hybrid network model.  In Symposium on Discrete Algorithms (SODA), pages 1280–1299, 2020\.
  * [12] Paul Beame, Paraschos Koutris, and Dan Suciu.  Communication steps for parallel query processing.  Journal of the ACM (JACM), 64(6):1–58, 2017.
  * [13] Ruben Becker, Andreas Karrenbauer, Sebastian Krinninger, and Christoph Lenzen.  Near-optimal approximate shortest paths and transshipment in distributed and streaming models.  In Proc. 31st Int. Symp. on Distributed Computing (DISC), pages 7:1–7:16, 2017.
  * [14] Aaron Bernstein and Danupon Nanongkai.  Distributed exact weighted all-pairs shortest paths in near-linear time.  In Proc. 51st ACM Symp. on Theory of Computing (STOC), pages 334–342, 2019.
  * [15] Amartya Shankha Biswas, Michal Dory, Mohsen Ghaffari, Slobodan Mitrović, and Yasamin Nazari.  Massively parallel algorithms for distance approximation and spanners.  In Proceedings of the 33rd ACM Symposium on Parallelism in Algorithms and Architectures, SPAA ’21, page 118–128, New York, NY, USA, 2021\. Association for Computing Machinery.
  * [16] Keren Censor-Hillel, Michal Dory, Janne H. Korhonen, and Dean Leitersdorf.  Fast approximate shortest paths in the congested clique.  In Proc. ACM Symp. on Principles of Distributed Computing (PODC), page 74–83, 2019.
  * [17] Keren Censor-Hillel, Petteri Kaski, Janne H. Korhonen, Christoph Lenzen, Ami Paz, and Jukka Suomela.  Algebraic methods in the congested clique.  Distributed Computing, 32(6):461–478, 2019.
  * [18] Keren Censor-Hillel, Seri Khoury, and Ami Paz.  Quadratic and near-quadratic lower bounds for the congest model.  In 31st International Symposium on Distributed Computing (DISC). Schloss Dagstuhl-Leibniz-Zentrum fuer Informatik, 2017.
  * [19] Keren Censor-Hillel, Dean Leitersdorf, and Volodymyr Polosukhin.  Distance computations in the hybrid network model via oracle simulations.  In Symposium on Theoretical Aspects of Computer Science (STACS). Schloss Dagstuhl-Leibniz-Zentrum für Informatik, 2021.
  * [20] Keren Censor-Hillel, Dean Leitersdorf, and Volodymyr Polosukhin.  On sparsity awareness in distributed computations.  In ACM Symposium on Parallelism in Algorithms and Architectures (SPAA), pages 151–161, 2021.
  * [21] Keren Censor-Hillel, Dean Leitersdorf, and Elia Turner.  Sparse matrix multiplication and triangle listing in the congested clique model.  In Proc. 22nd Int. Conf. on Principles of Distributed Systems (OPODIS), pages 4:1–4:17, 2018.
  * [22] Shiri Chechik and Doron Mukhtar.  Single-source shortest paths in the congest model with improved bounds.  Distributed Computing, pages 1–18, 2021.
  * [23] Jeffrey Dean and Sanjay Ghemawat.  Mapreduce: simplified data processing on large clusters.  Communications of the ACM, 51(1):107–113, 2008.
  * [24] Michal Dory, Orr Fischer, Seri Khoury, and Dean Leitersdorf.  Constant-round spanners and shortest paths in congested clique and mpc.  In ACM Symposium on Principles of Distributed Computing (PODC), pages 223–233, 2021.
  * [25] Michal Dory and Merav Parter.  Exponentially faster shortest paths in the congested clique.  In Proceedings of the 39th Symposium on Principles of Distributed Computing, PODC ’20, page 59–68, New York, NY, USA, 2020. Association for Computing Machinery.
  * [26] Michael Elkin.  Distributed exact shortest paths in sublinear time.  In ACM Symposium on Theory of Computing (STOC), pages 757–770, 2017.
  * [27] Michael Feldmann, Kristian Hinnenthal, and Christian Scheideler.  Fast hybrid network algorithms for shortest paths in sparse graphs.  In Principles of Distributed Systems (OPODIS), pages 31:1–31:16, 2020.
  * [28] Sebastian Forster and Danupon Nanongkai.  A faster distributed single-source shortest paths algorithm.  In 59th IEEE Symposium on Foundations of Computer Science (FOCS), pages 686–697, 2018.
  * [29] Silvio Frischknecht, Stephan Holzer, and Roger Wattenhofer.  Networks cannot compute their diameter in sublinear time.  In Proc. 23rd ACM-SIAM Symposium on Discrete Algorithms (SODA), pages 1150–1162, 2012.
  * [30] Mohsen Ghaffari and Jason Li.  Improved distributed algorithms for exact shortest paths.  In ACM Symposium on Theory of Computing (STOC), pages 431–444, 2018.
  * [31] Michael T Goodrich, Nodari Sitchinava, and Qin Zhang.  Sorting, searching, and simulation in the mapreduce framework.  In International Conference on Algorithms and Computation, pages 374–383, 2011.
  * [32] Thorsten Götte, Kristian Hinnenthal, Christian Scheideler, and Julian Werthmann.  Time-optimal construction of overlay networks.  In Symposium on Principles of Distributed Computing (PODC), pages 457–468, 2021.
  * [33] Bernhard Haeupler and Jason Li.  Faster distributed shortest path approximations via shortcuts.  In Symposium on Distributed Computing (DISC). Schloss Dagstuhl-Leibniz-Zentrum fuer Informatik, 2018.
  * [34] Daniel Halperin, Srikanth Kandula, Jitendra Padhye, Paramvir Bahl, and David Wetherall.  Augmenting data center networks with multi-gigabit wireless links.  In Proc. of the ACM SIGCOMM 2011 Conference, pages 38–49, 2011\.
  * [35] Monika Henzinger, Sebastian Krinninger, and Danupon Nanongkai.  A deterministic almost-tight distributed algorithm for approximating single-source shortest paths.  SIAM Journal on Computing, 50(3):STOC16–98, 2019.
  * [36] Stephan Holzer and Nathan Pinsker.  Approximation of distances and shortest paths in the broadcast congest clique.  In Proc. 19th Int. Conf. on Principles of Distributed Systems (OPODIS), pages 1–16, 2016.
  * [37] Stephan Holzer and Roger Wattenhofer.  Optimal distributed all pairs shortest paths and applications.  In 2012 ACM Symposium on Principles of Distributed Computing (PODC), pages 355–364, 2012.
  * [38] Qiang-Sheng Hua, Haoqiang Fan, Lixiang Qian, Ming Ai, Yangyang Li, Xuanhua Shi, and Hai Jin.  Brief announcement: A tight distributed algorithm for all pairs shortest paths and applications.  In ACM Symposium on Parallelism in Algorithms and Architectures (SPAA), pages 439–441, 2016.
  * [39] Chien-Chung Huang, Danupon Nanongkai, and Thatchaphol Saranurak.  Distributed exact weighted all-pairs shortest paths in $\widetilde{O}(n^{5/4})$ rounds.  In 58th IEEE Symposium on Foundations of Computer Science (FOCS), pages 168–179, 2017.
  * [40] Taisuke Izumi and François Le Gall.  Quantum distributed algorithm for the all-pairs shortest path problem in the congest-clique model.  In ACM Symposium on Principles of Distributed Computing (PODC), pages 84–93, 2019.
  * [41] Howard Karloff, Siddharth Suri, and Sergei Vassilvitskii.  A model of computation for mapreduce.  In Symposium on Discrete Algorithms, pages 938–948. SIAM, 2010\.
  * [42] Fabian Kuhn and Philipp Schneider.  Computing shortest paths and diameter in the hybrid network model.  In Proceedings of the 39th Symposium on Principles of Distributed Computing, pages 109–118, 2020.
  * [43] Fabian Kuhn and Philipp Schneider.  Routing Schemes and Distance Oracles in the Hybrid Model.  In International Symposium on Distributed Computing (DISC), volume 246, pages 28:1–28:22, 2022.
  * [44] François Le Gall.  Further algebraic algorithms in the congested clique model and applications to graph-theoretic problems.  In Proc. 30th Int. Symp. on Distributed Computing (DISC), pages 57–70, 2016.
  * [45] Christoph Lenzen.  Optimal deterministic routing and sorting on the congested clique.  In Principles of Distr. Comp. (PODC), pages 42–50, 2013.
  * [46] Christoph Lenzen and Boaz Patt-Shamir.  Fast routing table construction using small messages.  In Proc. 45th ACM Symposium on Theory of Computing (STOC), pages 381–390, 2013.
  * [47] Christoph Lenzen and Boaz Patt-Shamir.  Fast partial distance estimation and applications.  In 2015 ACM Symposium on Principles of Distributed Computing (PODC), pages 153–162, 2015.
  * [48] Nathan Linial and Michael Saks.  Decomposing graphs into regions of small diameter.  In Proceedings of the second annual ACM-SIAM symposium on Discrete algorithms, pages 320–330, 1991.
  * [49] Nancy A Lynch.  Distributed algorithms.  Elsevier, 1996.
  * [50] Danupon Nanongkai.  Distributed approximation algorithms for weighted shortest paths.  In Symp. on Theory of Computing (STOC), pages 565–573, 2014.
  * [51] D. Peleg.  Distributed Computing: A Locality-Sensitive Approach.  SIAM, 2000.
  * [52] Michael Rossberg and Guenter Schaefer.  A survey on automatic configuration of virtual private networks.  Computer Networks, 55(8), 2011.
  * [53] Václav Rozhoň, Christoph Grunau, Bernhard Haeupler, Goran Zuzic, and Jason Li.  Undirected (1+$\varepsilon$)-shortest paths via minor-aggregates: near-optimal deterministic parallel and distributed algorithms.  In Symposium on Theory of Computing, pages 478–487, 2022.
  * [54] Atish Das Sarma, Stephan Holzer, Liah Kor, Amos Korman, Danupon Nanongkai, Gopal Pandurangan, David Peleg, and Roger Wattenhofer.  Distributed verification and hardness of distributed approximation.  SIAM Journal on Computing, 41(5):1235–1265, jan 2012.
  * [55] Philipp Schneider.  Power and Limitations of Hybrid Communication Networks.  PhD thesis, University of Freiburg, 2023.
  * [56] Jeffrey D. Ullman and Mihalis Yannakakis.  High-probability parallel transitive-closure algorithms.  Journal on Computing, 20(1):100–125, 1991.
  * [57] Goran Zuzic, Gramoz Goranci, Mingquan Ye, Bernhard Haeupler, and Xiaorui Sun.  Universally-optimal distributed shortest paths and transshipment via graph-based $\ell$1-oblivious routing.  In ACM-SIAM Symposium on Discrete Algorithms (SODA), pages 2549–2579. SIAM, 2022.