# Massively Parallel Algorithms for Distance Approximation and Spanners

Amartya Shankha Biswas
CSAIL, MIT  Michal Dory,
Technion  Mohsen Ghaffari
ETH Zurich  Slobodan Mitrović
CSAIL, MIT  Yasamin Nazari
Johns Hopkins University

###### Abstract

Over the past decade, there has been increasing interest in
distributed/parallel algorithms for processing large-scale graphs. By now, we
have quite fast algorithms—usually sublogarithmic-time and often
$\operatorname{poly}(\log\log n)$-time, or even faster—for a number of
fundamental graph problems in the massively parallel computation
($\mathsf{MPC}$) model. This model is a widely-adopted theoretical abstraction
of MapReduce style settings, where a number of machines communicate in an all-
to-all manner to process large-scale data. Contributing to this line of work
on $\mathsf{MPC}$ graph algorithms, we present $poly(\log
k)\in\operatorname{poly}(\log\log n)$ round $\mathsf{MPC}$ algorithms for
computing $O(k^{1+{o(1)}})$-spanners in the strongly sublinear regime of local
memory. To the best of our knowledge, these are the first sublogarithmic-time
$\mathsf{MPC}$ algorithms for spanner construction.

As primary applications of our spanners, we get two important implications, as
follows:

  * •

For the MPC setting, we get an $O(\log^{2}\log n)$-round algorithm for
$O(\log^{1+o(1)}n)$ approximation of all pairs shortest paths (APSP) in the
near-linear regime of local memory. To the best of our knowledge, this is the
first sublogarithmic-time $\mathsf{MPC}$ algorithm for distance
approximations.

  * •

Our result above also extends to the Congested Clique model of distributed
computing, with the same round complexity and approximation guarantee. This
gives the first _sub-logarithmic_ algorithm for approximating APSP in
_weighted_ graphs in the Congested Clique model.

##  1 Introduction and Related Work

###  1.1 Massively Parallel Computation

Processing large-scale data is one of the indubitable necessities of the
future, and one for which we will rely more and more on distributed/parallel
computation. Over the past two decades, we have witnessed the emergence and
wide-spread usage of a number of practical distributed data processing
frameworks, including MapReduce [DG08], Hadoop [Whi12], Spark [ZCF+10] and
Dryad [IBY+07]. More recently, there has also been increasing interest in
building a corresponding algorithmic toolbox for such settings. By now, there
is a de-facto standard theoretical abstraction of these frameworks, known as
the _Massively Parallel Computation_ ($\mathsf{MPC}$) model. The model was
introduced first by Karloff et al. [KSV10] and refined later by Beam et al.
[BKS13] and Goodrich et al. [GSZ11].

###### MPC model.

On a very high-level, the model assumes a number of machines, each with a
memory capacity polynomially smaller than the entire data, which can
communicate in an all-to-all fashion, in synchronous message passing rounds,
subject to their memory constraints. More concretely, in the $\mathsf{MPC}$
model [KSV10, GSZ11, BKS13], we are given an input of size $N$ which is
arbitrarily distributed among a number of machines. Each machine has a memory
of size $S=N^{\alpha}$ for some $0<\alpha<1$, known as the local memory or
memory per machine. Since the data should fit in these machines, the number of
machines is at least $N/S$, and often assumed to be at most
$O(N/S\operatorname{poly}(\log N))$. Hence, the global memory—that is, the
summation of the local memories across the machines— is $\tilde{O}(N)$. The
machines can communicate in synchronous message-passing rounds, subject to the
constraint that the total amount of messages a machine can communicate per
round is limited by its memory $S$.

In the case of graph problems, given a graph $G=(V,E)$ the total memory $N$ is
$O(|E|)$ words. Ideally, we would like to be able to work with machines that
have a small local memory, and still have only few rounds. However, the task
gets more complex as one reduces the local memory. Depending on how the local
memory compares with the number of vertices $n=|V|$, there are three regimes
that have been studied in the $\mathsf{MPC}$ model:

  * •

the _strongly superlinear_ regime where $S\geq n^{1+\varepsilon}$ for a
constant $\varepsilon>0$,

  * •

the _near-linear_ regime where $S=\tilde{O}(n)$, and

  * •

the strongly sublinear regime where $S=n^{\gamma}$ for a positive constant
$\gamma<1$.

We note that the algorithms that can work in the strongly sublinear memory
regime are sometimes referred to as _scalable massively parallel algorithms_.
Our focus will be on the more stringent, and also more desirable, regimes of
near-linear and strongly sublinear memory.

###  1.2 Graph Problems and Massively Parallel Computation

At the center of the effort for building algorithmic tools and techniques for
large-scale data processing has been the subarea of _$\mathsf{MPC}$ algorithms
for graph problems_, e.g., [GSZ11, LMSV11, BKS13, ANOY14, BKS14, HP15, AG15,
RVW16, IMS17, CLM+18, Ass17, ABB+19, GGK+18, HLL18, BFU18, BEG+18, ASS+18,
BBD+19, BHH19, BDE+19, ASS+18, ASZ19, ABB+19, ASW19, GKMS19, GLM19, GU19,
LMOS20, ILMP19, CFG+19, GKU19, GNT20, GN20]. We discuss a very brief overview
here. Please see Appendix A for a more detailed overview, with quantitative
bounds.

Early on [KSV10, BKS13], it was observed that $\mathsf{MPC}$ can simulate
classic $\mathsf{PRAM}$ parallel algorithms (subject to conditions on the
total amount of work) in the same time. This immediately led to
$\operatorname{poly}(\log n)$ round algorithms for a wide range of graph
problems.

Since then, the primary objective in the study of $\mathsf{MPC}$ algorithms
has been to obtain significantly faster algorithms, e.g., with constant or
$\operatorname{poly}(\log\log n)$ round complexity. This was achieved
initially for the strongly super-linear memory regime, for many problems, and
over the past few years, there has also been significant progress on near-
linear and strongly sublinear memory regimes. In particular, there has been
quite some progress for (A) global graph problems such as connected
components, maximal forest, minimum-weight spanning tree, minimum cut, etc,
[LMSV11, AGM12, ASS+18, BDE+19, GNT20, GN20] and (B) local graph problems such
as maximum matching approximation, graph coloring, maximal independent set,
vertex cover approximation, etc [LMSV11, HLL18, CLM+18, GGK+18, ABB+19, ACK19,
CFG+19, CFG+19, RG20].

###### Distance Problems.

Despite the substantial progress on various graph problems, one fundamental
category of graph problems for which the progress in $\mathsf{MPC}$ has been
slower is distance computations and, more generally, distance-related graph
problems. In particular, considering that a key criteria in the area is to
obtain near constant (and especially $o(\log n)$) time algorithms, the
following question has remained open.

Question: Are there $\operatorname{poly}(\log\log n)$-time MPC algorithms in
the near-linear memory regime that compute all pairs shortest paths, or any
reasonable approximation of them?

In fact, to the best of our knowledge, prior to our work, there was no known
$\mathsf{MPC}$ algorithm even with a sublogarithmic round complexity, for any
non-trivial approximation factor, and even for single-source shortest paths.

The known algorithms provide only $poly(\log n)$ round complexity, which is
considerably above our target. For instance, one can obtain a $poly(\log n)$
round algorithm for $1+\varepsilon$ approximation of single source shortest
paths (SSSP) in the sublinear memory regime of $\mathsf{MPC}$, by adapting the
$\mathsf{PRAM}$ algorithm of Cohen [Coh00]. While that algorithm requires
$m^{1+\Omega(1)}$ global memory, recent $\mathsf{PRAM}$ results reduce that to
$\tilde{O}(m)$ [Li20, ASZ20]. Among more recent work, Hajiaghayi et al.
[HLSS19] give an all pairs shortest path (APSP) algorithm that runs
$O(\log^{2}n)$ rounds in strongly sublinear local memory, for certain range of
edge weights, and uses a large polynomial global memory, which depends on
exponents of matrix multiplication.

To tackle the above question, we can naturally ask whether, in the allowed
time, one can sparsify the graph considerably, without stretching the
distances – as that sparse graph then can be potentially moved to one machine.
This directly brings us to the notion of spanners, as introduced by Peleg and
Schäffer [PS89], which are subgraphs with few edges that preserve distances,
up to a certain multiplicative factor. A more detailed explanation follows.

###### Spanners.

Given a graph $G=(V,E)$, a $k$-spanner is a (sparse) spanning subgraph $H$ of
$G$ such that the distance between each pair of nodes in $V$ on this subgraph
$H$ is at most $k$ times their distance in the original graph $G$ [Pel00]. It
is known that every graph admits a $(2k-1)$-spanner of size $O(n^{1+1/k})$,
for $k\geq 1$, and assuming Erdös girth conjecture, this tradeoff is also
tight. Spanners have found many applications in various models, such as, in
constructing sparsifiers in the streaming model [KW14], designing work-
efficient $\mathsf{PRAM}$ algorithms [FL18], and transshipment based distance
approximations in $\mathsf{PRAM}$ [Li20] and Congested Clique [BKKL17]. In the
context of strongly sublinear memory $\mathsf{MPC}$, [DN19] used spanners to
obtain an exponential speed up in preprocessing of distance sketches (though,
still requiring polylogarithmic rounds). In particular, they achieve this by
using spanners in order to simulate non-work-efficient $\mathsf{PRAM}$
algorithms in $\mathsf{MPC}$ without using extra memory. In general, spanners
can be applied to reduce use of resources such as communication and memory for
distance-related computation on denser graphs at the expense of accuracy.

We are not aware of any $\operatorname{poly}(\log\log n)$ round MPC algorithm
for computing spanners, in the sublinear or near-linear memory regime. Though
one can obtain some (weaker) results from those of other computational models,
as we will be discussed later, when mentioning our results.

###  1.3 Our Contribution

In this paper, we provide the first sublogarithmic time $\mathsf{MPC}$
algorithms for distance approximations and for constructing spanners. Our
spanner construction works in the strongly sublinear memory regime, while for
using them in distance approximation we need to move to the near-linear memory
regime. Since, as stated, spanners are versatile tools that have found
applications in various distance-related graph problems, we are hopeful that
our spanner construction should also help in a wider range of problems.

##### Spanner Constructions.

Our main technical result, as stated below, provides a family of algorithms
which provide a general trade-off between the number of $\mathsf{MPC}$ rounds
and the stretch of the resulting spanner.

######  Theorem 1.1.

Given a weighted graph $G$ on $n$ vertices and $m$ edges and a parameter $t$,
there is an algorithm that runs in $O(\frac{1}{\gamma}\cdot\frac{t\log
k}{\log(t+1)})$ rounds of $\mathsf{MPC}$ and w.h.p. outputs a spanner of size
$O(n^{1+1/k}\cdot(t+\log k))$, and stretch $O(k^{s})$ when memory per machine
is $O(n^{\gamma})$ for any constant $\gamma>0$, and where
$s=\frac{\log(2t+1)}{\log(t+1)}$. This algorithm uses total memory of
$\tilde{O}(m)$.

Since the theorem statement in Theorem 1.1 might be complex due to the number
of variables involved, we next state several interesting corollaries of this
theorem.

######  Corollary 1.2.

Given a total memory of $\tilde{O}(m)$ and memory per machine being
$O(n^{\gamma})$, for any constant $\gamma>0$, there is an $\mathsf{MPC}$
algorithm that w.h.p. outputs a spanner with the following guarantees in terms
of round complexity, stretch and size:

  1. 1.

runs in $O(\log k)$ rounds, has $O(k^{\log 3})$ stretch and
$O(n^{1+1/k}\cdot\log k)$ size;

  2. 2.

runs in $O\left(2^{1/\varepsilon}\cdot\varepsilon^{-1}\cdot\log k\right)$
rounds, has $O(k^{1+\varepsilon})$ stretch and
$O(n^{1+1/k}\cdot(2^{1/\varepsilon}+\log k))$ size;

  3. 3.

runs in $O(\frac{\log^{2}k}{\log\log k})$ rounds, has $O(k^{1+o(1)})$ stretch
and $O(n^{1+1/k}\cdot\log k)$ size;

  4. 4.

runs in $O(\frac{\log^{2}\log{n}}{\log\log\log{n}})$ rounds, has
$O(\log^{1+o(1)}n)$ stretch and $O(n\cdot\log\log{n})$ size.

Moreover, and crucially for our distance approximation applications, our
algorithms are applicable to weighted graphs.

$\mathsf{PRAM}$ algorithms for spanners such as Baswana-Sen [BS07] have depth
at least $\Omega(k)$, which leads to $\mathsf{MPC}$ algorithms with $O(k)$
complexity. Our algorithms are significantly faster, at the price of a small
penalty in the stretch. Another relevant prior work that we are aware of is a
one of Parter and Yogev in the Congested Clique model, on constructing graph
spanners in unweighted graphs [PY18] of $O(k)$ stretch. In Appendix B, we show
how by building on this work one can obtain the following result.

######  Theorem 1.3.

Given an unweighted graph $G$ on $n$ vertices and $m$ edges, there is an
algorithm that in $O(\frac{1}{\gamma}\cdot\log k)$ $\mathsf{MPC}$ rounds
w.h.p. outputs a spanner of size $O(n^{1+1/k}\cdot k)$ and stretch $O(k)$ when
memory per machine is $O(n^{\gamma})$, for any constant $\gamma>0$. This
algorithm uses a total memory of $\tilde{O}(m+n^{1+\gamma})$.

It is worth noting that these round complexities are close to optimal,
conditioned on a widely believed conjecture. This is because lower bounds in
the distributed LOCAL model imply an $\Omega(\log k)$ conditional lower bound
for the closely related problem of finding spanners with optimal parameters,
i.e., $(2k-1)$-spanners with $O(n^{1+\frac{1}{k}})$ edges. Specifically, there
is an $\Omega(k)$ lower bound for the problem in the LOCAL model [DGPV08], and
as shown in [GKU19], this implies $\Omega(\log k)$ conditional lower bound in
$\mathsf{MPC}$ with sublinear memory, under the widely believed conjecture
that connectivity requires $\Omega(\log n)$ rounds.111The proof in [GKU19] is
for $\mathsf{MPC}$ algorithms that are component-stable, see [GKU19] for the
exact details. This conjecture is also called the cycle vs two cycles
conjecture, as even distinguishing between one cycle of $n$ nodes from 2
cycles of $n/2$ nodes, is conjectured to require $\Omega(\log n)$ rounds. Our
algorithms have complexity of $\operatorname{poly}(\log k)$ for near-optimal
(up to a factor of $k^{o(1)}$) stretch which nearly matches the lower bound.

It is an interesting question whether spanners with _optimal_ parameters can
be also constructed in $\operatorname{poly}(\log k)$ time. While our main goal
is to construct spanners in standard $\mathsf{MPC}$ in
$\operatorname{poly}\log k$ rounds, we also provide two results that lead to
near optimal parameters (stretch $O(k)$ and size $\tilde{O}(n^{1+1/k})$) at
the expense of computational resources. As mentioned above, Theorem 1.3
constructs $O(k)$-spanners with $O(n^{1+1/k}\cdot k)$ edges in $O(\log{k})$
rounds. This however comes at a price of extra total memory, and also only
works for _unweighted_ graphs. Additionally, in Section 3, we provide an
algorithm that runs in $O(\sqrt{k})$ rounds and computes an $O(k)$-spanner
with $O(\sqrt{k}n^{1+1/k})$ edges. While the parameters of the spanner are
near-optimal, this comes at a price of significant increase in the round
complexity (this is still much faster compared to previous algorithms that
require $O(k)$ time).

##### Distance Approximations.

As a direct but important corollary of our spanner construction in Corollary
1.2, in the near-linear memory regime we get an $O(\log^{2}\log n)$-round
algorithm for $O(\log^{1+o(1)}n)$ approximation of distance related problems,
including all-pairs-shortest-paths. Alternatively, we can obtain a faster
algorithm that runs in $O(\log\log n)$ rounds, if we relax the approximation
factor to $O(\log^{1+\varepsilon}n)$ for a constant $\varepsilon>0$. It is
important to note that as the global memory in MPC is bounded by
$\tilde{O}(m)$, we do not have enough space to store the complete output of
APSP. Instead, we have one coordinator machine that stores the spanner, which
implicitly stores approximate distances between all vertices. This machine can
then compute distances locally based on the spanner. This gives the following
(See Section 7 for full details).

######  Corollary 1.4.

There is a randomized algorithm that w.h.p computes
$O(\log^{s}n)$-approximation for APSP in weighted undirected graphs, and runs
in $O(\frac{t\log\log{n}}{\log(t+1)})$ rounds of $\mathsf{MPC}$, when memory
per machine is $\tilde{O}(n)$, $s=\frac{\log(2t+1)}{\log(t+1)}$, and
$t=O(\log{\log{n}})$. This algorithm uses total memory of size $\tilde{O}(m)$.

Our work leaves an intriguing open question.

Open Problem. _Can we compute a constant, or perhaps even $1+o(1)$,
approximation of all pairs shortest paths in $\operatorname{poly}(\log\log n)$
rounds in the near-linear local memory regime of $\mathsf{MPC}$?_

##### Extension to Other Models.

In addition to these two models, we show the generality of our techniques by
extending our results to the PRAM and Congested Clique models.

######  Congested Clique

We can extend our spanner construction to work also in the distributed
Congested Clique model (see Section 8), leading to the following corollary for
approximate shortest paths.

######  Corollary 1.5.

There is a randomized algorithm in the Congested Clique model that w.h.p
computes $O(\log^{s}n)$-approximation for APSP in weighted undirected graphs,
and runs in $O(\frac{t\log\log{n}}{\log(t+1)})$ rounds, where
$s=\frac{\log(2t+1)}{\log(t+1)}$, and $t=O(\log{\log{n}})$.

As two special cases, this gives $O((\log n)^{\log 3})$-approximation in
$O(\log\log n)$ time, and $O(\log^{1+o(1)}n)$-approximation in $O((\log{\log
n})^{2})$ time. It is important to note that these are the first _sub-
logarithmic_ algorithms that approximate weighted APSP in the Congested Clique
model. Prior results take at least poly-logarithmic number of rounds or only
work for _unweighted_ graphs, as we review next.

Previous poly-logarithmic algorithms include the following. First, the spanner
construction of Baswana-Sen [BS07] gives $O(\log n)$-approximation for
weighted APSP in $O(\log n)$ rounds, by building $O(\log{n})$-spanner of size
$O(n\log{n})$ and letting all vertices learn the spanner. Additionally, it is
possible to get a $(3+\epsilon)$-approximation for weighted APSP in
$O(\frac{\log^{2}{n}}{\epsilon})$ time [CHDKL19]. In unweighted graphs, a
recent work [DP20] shows that it is possible to get
$(2+\epsilon)$-approximation for APSP in $poly(\log{\log{n}})$ time, however
the techniques only apply for the unweighted case.

We note that while there are fast constructions of spanners in the Congested
Clique model [PY18], they work only for _unweighted_ graphs, and also the size
of the spanner is at least $\Omega(n\log n)$. The latter adds $\Omega(\log n)$
rounds to the complexity of APSP, for collecting the spanner, which means one
cannot achieve a sublogarithmic round complexity for APSP using these spanner
constructins.

###### PRAM

Our result also extends to the PRAM CRCW model. We would get the same PRAM
depth as the MPC round complexity, with an additional multiplicative
$\log^{*}n$ factor that arises from certain PRAM primitives (see Section 6).
We note that $O(k\log^{*}n)$ depth PRAM algorithms for $O(k)$ spanners were
studied in [MPVX15], and [BS07]. To the best of our knowledge, before this
work there were no known algorithms in PRAM with depth $o(k)$, even for
suboptimal spanners.

##  2 Overview of Our Techniques

The main objective of our work is to design spanners that can be implemented
in small parallel depth, e.g., $\operatorname{poly}(\log\log n)$ rounds of
MPC. For the sake of simplicity, we present our main ideas by considering
unweighted graphs only. However, our main results apply to weighted graphs as
well, and that’s one of the key strengths of our approach.

Our general approach will be to grow clusters of vertices by engulfing
adjacent vertices and clusters. Additionally, each cluster will be associated
with a rooted tree that essentially shows the “history” of the cluster’s
growth, with the root representing the oldest vertex of the cluster. The tree
edges will all be part of the spanner, and the maximum depth of the tree will
be called the _radius_ of the corresponding cluster.

A general paradigm when attaching a cluster to either a vertex or another
cluster will be to keep only one edge between them (the one of minimum weight)
in the spanner, and discarding the remaining edges. The discarded edges will
be spanned by the single included edge and the tree edges within the
cluster(s). Thus, (disregarding many details) we can generally upper bound the
stretch of any discarded edge by four times the maximum radius of any cluster.
Moving forwards, we will talk about stretch and cluster radius interchangeably
since they are asymptotically equal.

###  2.1 Fast Algorithm using Cluster-Cluster Merging

As a starting point, we design an algorithm based on _cluster-cluster merging_
, that can be summarized as follows.

Cluster-cluster merging
Given an unweighted $G=(V,E)$ and parameter $k\geq 2$: - Let $\mathcal{C}_{0}$
be a set of $n$ clusters ($|V|=n$), where each vertex of $V$ is a single
cluster. - For $i=1\ldots\log{k}$: (A) Let $\mathcal{C}_{i}$ be a set of
clusters obtained by sampling each cluster from $\mathcal{C}_{i-1}$ with
probability $n^{(-2^{i-1}/k)}$. (B) For each cluster
$c\in\mathcal{C}_{i-1}\setminus\mathcal{C}_{i}$: (i) If $c$ has a neighbor
$c^{\prime}\in\mathcal{C}_{i}$, add an edge between $c$ and $c^{\prime}$ to
the spanner, and merge $c$ to $c^{\prime}$. (ii) Otherwise, for every
$c^{\prime}\in\mathcal{C}_{i-1}\setminus\mathcal{C}_{i}$ that is a neighbor of
$c$ add an edge between $c$ and $c^{\prime}$ to the spanner. - Add an edge
between each pair of clusters remaining.

We start by letting each vertex be a singleton cluster, and in each subsequent
iteration, a set of clusters is sub-sampled. These _sampled clusters_ are
“promoted” to the next iteration (the remaining clusters will not be
considered in future iterations). However, the _sampled_ clusters grow to
absorb the neighboring _unsampled_ ones. Conversely, each unsampled cluster
joins its nearest neighboring sampled cluster. If no such neighboring
(sampled) cluster exists, then we can conclude that, with high probability,
there are very few neighboring clusters, and this allows us to deal with these
problematic clusters by including edges to all their neighbors in the spanner.

###### Intuition for the Analysis.

The intuition behind this approach is as follows. As in each iteration
clusters are merged, the number of clusters decreases significantly between
iterations. Since we are aiming for a spanner of size $\tilde{O}(n^{1+1/k})$,
if $C$ is the current set of clusters, we can allow each cluster in $C$ to add
$\frac{n^{1+1/k}}{|C|}$ adjacent edges to the spanner. This means that when
the number of clusters reduces, we can allow each cluster to add significantly
more edges to the spanner. This allows us to decrease the sampling probability
$p$ between different iterations drastically. As a consequence, the number of
clusters decreases rapidly, which results in a $\log{k}$ complexity. We show
that in each iteration the merging grows the stretch by a factor of 3, leading
to an overall stretch of $O(3^{\log{k}})=O(k^{\log{3}}).$

###  2.2 Obtaining Better Stretch

We now discuss how to reduce the stretch, all the way to $k^{1+o(1)}$, while
maintaining the same spanner size and increasing the number of iterations only
by an extra $\log{k}$ factor.

Intuitively, the spanner algorithm described has sub-optimal stretch of
$k^{\log{3}}$ mainly since it is too aggressive in growing clusters in each
iteration, and when two clusters are merged, the radius increases by a factor
of three in one iteration. Thus a natural idea would be to grow the clusters
much more gradually; that is, instead of merging a cluster $c$ to cluster
$c^{\prime}$ entirely in one iteration, $c^{\prime}$ could consume parts of
$c$ repeatedly (over multiple iterations). In other words, similar to the
algorithm of [BS07] we can grow the clusters incrementally before performing a
merge. We call this process _cluster-vertex merging_.

###### Cluster-vertex merging

The main difference between cluster-cluster and cluster-vertex merging can be
outlined as follows: Firstly, in Step A use a smaller sampling probability,
e.g. $n^{-1/k}$, instead of $n^{-2^{i-1}/k}$; Secondly, in Step Bi instead of
merging two clusters, merge to a sampled cluster $c^{\prime}$, only the
vertices _incident_ to $c^{\prime}$ that _do not belong_ to any sampled
cluster. This essentially recovers the algorithm in [BS07], where it was shown
that using only the cluster-vertex merging, one can construct a spanner of
stretch $O(k)$, but this also requires $O(k)$ rounds. We investigate the
interpolation between these two extremes by using a hybrid approach, which
uses both incremental cluster growing (cluster-vertex merging) and cluster-
cluster merging.

###### Combining the two approaches using cluster contractions.

The basic idea is as follows. Instead of merging clusters in each iteration,
we alternate between iterations where we apply the cluster-vertex merging
approach and iterations where we apply the cluster-cluster merging approach.
After a few iterations where we apply cluster-vertex merging, we merge
clusters (an operation we also refer to as _contraction_). this allows to get
an improved stretch but still keep a small running time.

Running the _cluster-vertex merging_ procedure on a contracted graph also
results in the cluster size growing much faster in each step. This accelerated
cluster growth is the main reason for the speedup in our algorithm.

Intuitively, contractions result in _loss of information_ about the _internal
structure_ of the cluster, and any time they are performed we incur extra
stretch penalties. Our aim is to carefully balance out this loss with the
cluster growth rate to get the best tradeoffs. We adjust this by tuning the
sampling probabilities, and the intervals at which we perform contractions.
This interpolation will allow us to reduce the stretch to $k^{1+o(1)}$, while
still having $O(\operatorname{poly}\log k)$ round (iteration) complexity. More
generally, our various tradeoffs are a consequence of how much we grow the
clusters before each contraction.

###  2.3 The General Algorithm for Round-Stretch Tradeoffs

Now, we provide a more detailed overview of our general algorithm. We will
then look at specific parameter settings that lead to various tradeoffs. The
algorithm proceeds in a sequence of epochs, where epoch $i$ consists of $t$
iterations as follows: In each iteration we subsample the clusters with
probability $p_{i}$ (to be defined later). As before, we then grow each
sampled cluster by adding all neighboring vertices that have not joined any
other sampled cluster. At this point we contract the clusters, and move to the
next epoch.

Our general algorithms (in Definition 5.1) achieve a range of tradeoffs,
parameterized by $t$, which is the number of growth iterations before a
contraction, as we outline below.

  1. (A)

Assume that the number of _super-nodes_ in the current graph is $n^{\prime}$
(originally $n$).

  2. (B)

Repeat $t$ times (essentially performing $t$ iterations of [BS07] with
adjusted sampling probabilities):

    1. 1.

Perform _cluster-sub-sampling_ with $p_{i}=\frac{n^{\prime}}{n^{1+1/k}}$:
Ensures that number of added edges
$\frac{n^{\prime}}{p_{i}}=O(n^{1+\frac{1}{k}})$.

    2. 2.

Perform incremental _cluster-vertex merging_ to increase the radius of each
cluster by one unit in the _current graph_ :
Note that the current graph may contain contracted clusters as _super-nodes_.
Assuming that the internal radius of the _super-nodes_ is $r$, the actual
radius increase in the original graph can be as large as $2r+1$ units (see
Fig. 1).

  3. (C)

Perform _cluster-contraction_ on the most recent clusters (clusters become
super-nodes).
This has the effect of reducing the number of clusters in the graph by a
factor of $p_{S}^{t}$ (probability of a specific cluster surviving for $t$
repititions of _cluster-sub-sample_). So, we get $n^{\prime}\leftarrow
n^{\prime}\cdot p_{S}^{t}$.

Following are some example results we obtain for specific values of parameter
$t$.

  * •

$\mathbf{(t=k)}$: This is one extreme case where there is _no contraction_ ,
and the cluster radius only increases by $\mathsf{1}$ for $k$ repetitions,
thus recovering the [BS07] result. This is the _slowest_ algorithm, but it
achieves optimal stretch $2k-1$.

  * •

$\mathbf{(t=\sqrt{k})}$: The immediate generalization involves exactly one
contraction (analysis in Section 3), which occurs after the first set of
$\sqrt{k}$ iterations. A new sampling probability is introduced after the
contraction (reduced size of graph). According to this probability, the
remainder of the algorithm is actually just a normal $\sqrt{k}$ stretch
spanner construction. This algorithm attains $O(k)$ stretch, but it
dramatically reduces the number of rounds to $O(\sqrt{k})$.

  * •

$\mathbf{(t=1)}$: This is the other extreme case (analyzed in Section 4),
where the three procedures (sub-sample, grow, contract) are performed
repeatedly one after another, i.e., the algorithm contracts immediately after
a single grow step. Consequently, the cluster radius grows exponentially, and
the algorithm terminates after $\log k$ repetitions, yielding Item 1 of
Corollary 1.2. This is the _fastest_ algorithm, but only achieves stretch
$O(k^{\log 3})$.

One special interesting setting, which we also use for application in distance
approximation, is when we set $t=\log k$. This leads to stretch $k^{1+o(1)}$
and requires only $O(\frac{\log^{2}k}{\log\log k})$ rounds. The general
tradeoffs can be found in Definition 5.1.

###  2.4 Related Spanner Constructions

Our approach can also be seen as a new contraction-based spanner algorithm
with a focus on parallel depth/round efficiency.

In the context of dynamic stream algorithms, another contraction-based
algorithm was proposed by [AGM12], but only for unweighted graphs. Their
contractions are based on a different type of clustering formed based on
vertex degrees. Algorithm of [AGM12] has resemblance to a special case of our
algorithm described in Section 4.1, but it has a weaker stretch. In
particular, for a spanner of size $\tilde{O}(n^{1+1/k})$ they obtain stretch
$k^{\log 5}$ in $\log k$ passes in streaming (where a pass corresponds to one
round of communication in $\mathsf{MPC}$) in unweighted graphs, whereas in the
same time (pass/round) we obtain stretch $k^{\log 3}$ even for weighted
graphs. Our general algorithm, as a special case, obtains the much stronger
stretch of $k^{1+o(1)}$ in $O(\frac{\log^{2}k}{\log\log k})$ iterations.

These contraction-based algorithms can be seen as an alternative approach to
the well-known algorithm of [BS07]. Mainly, the goal in [BS07] is to compute
optimal spanners of stretch $2k-1$, whereas our main goal is time efficiency.
As a result our algorithm has a slightly weaker stretch/size tradeoff, but
requires exponentially fewer iterations.

This general contraction-based framework may be of interest also in other
related distance objects. A related work by [BLP20] focuses on
$(\alpha,\beta)$-spanners and hopsets, and they use a similar type of
clustering as one part of their construction. However, they connect the
clusters differently and in since their main focus is not computation time,
their algorithms run in polynomial time in most models. We hope that our fast
clustering techniques also give insight into faster algorithms for these
structures, perhaps at an extra cost in the stretch. Such improvements will
have immediate implications for distance computation in various models.

After the submission of our initial manuscript in March 2020, we found out
that in an independent and concurrent work, [FKN21] obtained similar bounds
for spanner construction in dynamic stream settings, but only for unweighted
graphs.

##  3 Cluster-Contraction Algorithm for Near-Optimal Spanners

As a warm-up, in this section we discuss an algorithm that takes $O(\sqrt{k})$
rounds and constructs a spanner with stretch $O(k)$ and size
$O(\sqrt{k}n^{1+1/k})$ in unweighted graphs. Note that this simple algorithm
is already significantly faster compared to [BS07], requiring only
$O(\sqrt{k})$ rounds instead of $O(k)$ rounds.

Given an unweighted graph $G=(V,E)$ we compute a spanner of size
$O(\sqrt{k}n^{1+1/k})$ with stretch $O(k)$. The high-level idea is as follows.
We run the algorithm of [BS07] twice: in the first phase we perform the first
$t=\Theta(\sqrt{k})$ iterations of [BS07] and stop. We will form a supergraph
$\hat{G}=(\hat{V},\hat{E})$ defined by setting each cluster $\mathcal{C}_{t}$
to be a supernode, and will add an edge between supernodes
$c_{1},c_{2}\in\hat{V}$ if the corresponding clusters are connected with at
least one edge in the original graph $G$. Now, for
$t^{\prime}=\Theta(\sqrt{k})$, we compute a $t^{\prime}$-spanner on $G$ by
running the [BS07] algorithm on the graph $\hat{G}$ as a black-box, this
requires only $t^{\prime}=\sqrt{n}$ additional iterations. Next we describe
these two phases in detail.

##### First Phase:

Start with $\mathcal{R}_{0}=V$, and $V^{\prime}=V$, $\mathsf{E}=E$. We will
have a sequence of clusterings
$\mathcal{R}_{1}\supseteq\ldots\supseteq\mathcal{R}_{t}$ for a parameter $t$
(we will set $t=\sqrt{n}$). $V^{\prime}$ and $\mathsf{E}$ will be the set of
vertices and edges that are not yet settled. In each iteration of the first
phase, $V^{\prime}$ is the set of vertices with one endpoint in $\mathsf{E}$.

  1. 1.

Sample a set of clusters $\mathcal{R}_{i}$ by choosing each cluster in
$\mathcal{R}_{i-1}$ with probability $n^{-1/k}$. Set
$\mathcal{C}_{i}=\mathcal{R}_{i}$.

  2. 2.

For all $v\in V^{\prime}$:

    1. (i)

If $v$ is adjacent to a sampled cluster $\mathcal{R}_{i}$, then add $v$ to the
closest $c\in\mathcal{C}_{i}$ and add one edge from $E(v,c)$ to the spanner.
Discard (remove from $\mathsf{E}$) all the edges in $E(v,c)$.

    2. (ii)

If $v$ is not adjacent to any sampled clusters in $\mathcal{R}_{i}$, then for
each neighboring cluster $c^{\prime}\in\mathcal{C}_{i-1}$ add a single edge
from $E(v,c^{\prime})$ to the spanner, and discard all other edges between
$E(v,c^{\prime})$.

    3. (iii)

Remove the intra-cluster edges: remove all the edges with both endpoints in
$\mathcal{C}_{i}$ from $\mathsf{E}$.

##### Second Phase:

Define a supergraph $\hat{G}=(\hat{V},\hat{E})$ by setting each cluster
$\mathcal{C}_{t}$ to be a node in $\hat{G}$ and adding an edge in $\hat{E}$
for each pair of adjacent clusters in $\mathcal{C}_{t}$. We then run a black-
box algorithm for computing a $(2t^{\prime}-1)$-spanner (e.g. by running the
algorithm of [BS07]) on $\hat{G}$, for $t^{\prime}=\sqrt{n}$.

##### Analysis Sketch.

The high-level idea is that we are stopping the algorithm of [BS07] when there
are $O(n^{1-1/\sqrt{k}})$ (or more generally $O(n^{1-t/k})$) clusters in
$C_{t}$. This means that the supergraph $\hat{G}$ is significantly smaller,
and now we can afford to compute a spanner with a better stretch on $\hat{G}$,
for fixed size. The radius of the clusters at termination is
$O(tt^{\prime})=O(k)$, and thus the overall stretch is $O(k)$. To formalize
this argument, we start with the size analysis.

######  Theorem 3.1.

The set of edges added by this algorithm is $O(\sqrt{k}n^{1+1/k})$.

###### Proof..

In the first phase we only add as many edges as the [BS07] algorithm does and
the total number of edges is $O(tn^{1+1/k})$. In the second phase we will add
$O(n^{1-t/k})^{1+1/t^{\prime}})$ edges, which is $O(n^{1-1/k})$ for
$t=t^{\prime}=\sqrt{n}$. ∎

We provide a brief argument for the stretch. A similar and more formal
argument for similar claims will be presented in Section 4.

We next provide the stretch analysis of the algorithm. We first argue that if
an edge $(u,v)$ is not added to the spanner, or discarded by the end of
iteration $i$, then the endpoints $u$ and $v$ are in distinct clusters in
$\mathcal{C}_{i}$. This would imply that we can only restrict our attention to
the vertices that survive inside clusters. Otherwise, they are removed from
$V^{\prime}$.

######  Lemma 3.2.

Let $(u,v)\in E$ be an edge not added to the spanner. At the end of iteration
$i$ of the first phase, $(u,v)$ is either discarded (removed from
$\mathsf{E}$), or both its endpoints belong to clusters in $\mathcal{C}_{i}$.

###### Proof.

Let $j\leq t$ be the first iteration in which at least one of $u$ or $v$ does
not belong to $\mathcal{C}_{j}$. In other words, their cluster does not get
promoted (i.e. is not a cluster subsampled at level $j$). W.l.o.g assume that
$u$ is the endpoint that is not part of any cluster in $\mathcal{C}_{j}$. In
other words, $u$ does not have any neighbouring sampled cluster in
$\mathcal{C}_{j}$. By our assumption on $j$, we know that there exists a
cluster $c_{v}\in\mathcal{C}_{j-1}$ that $v$ belongs to. Hence if edge $(u,v)$
is not added to the spanner, it must have been discarded in step 2 (ii). ∎

We will also use the following property of the algorithm as shown in [BS07].

######  Lemma 3.3.

At iteration $i$ of the first phase, all clusters $\mathcal{C}_{i}$ have
radius $i$.

We now use the properties described to prove the overall stretch.

######  Theorem 3.4.

For each edge $(u,v)\in E$ not added to the spanner there is a path of length
$O(k)$ between $u$ and $v$.

###### Proof.

Let $(u,v)\in E$. From Lemma 3.2, by the end of the first phase, $(u,v)$ is
either discarded, or its endpoints belong to clusters in $\mathcal{C}_{t}$. We
start by discussing the case it is discarded, we consider the following two
cases.

_Case 1: the edge $(u,v)$ is removed in step 2 (i) or (ii)._ Assume w.l.o.g.
that this edge was removed while processing node $u$. In this case, an edge
$(u,v^{\prime})$ was added to the cluster $c_{v}\in\mathcal{C}_{i}$ that $v$
belongs to. Given the fact that this cluster has radius $i$, we know that
there is a path of length $2i+1$ between $u$ and $v$.

_Case 2: $(u,v)$ is removed in step (iii)._ Here $u$ and $v$ both are assigned
to the same cluster, say $c\in\mathcal{C}_{i}$. This means (by Lemma 3.3) that
there is a path of length at most $i$ from $u$ to center of $c$, and a path of
length at most $i$ from $v$ to center of $c$. Thus there is a path of length
at most $2i$ between $u$ and $v$. Hence at the end of first phase all clusters
have radius $2t$.

We next consider the case that by the end of the first phase, both of the
endpoints of $(u,v)$ belong to clusters in $\mathcal{C}_{t}$. If they belong
to the same cluster by iteration $t$, then we know that there is a path of
length $2t$ between $u$ and $v$, since this cluster has radius at most $t$.
Otherwise $u$ and $v$ belong to distinct clusters in $\mathcal{C}_{t}$, which
we denote by $c_{u}$ and $c_{v}$ respectively. These clusters will be
“supernodes” in $\hat{V}$. In other words, any vertex that is not part of
clusters in $\mathcal{C}_{t}$ is already processed and removed from
$V^{\prime}$. Therefore we can restrict our attention to vertices that are
part of clusters in $\hat{V}$.

Since we construct a $t^{\prime}$-spanner on $\hat{G}$, at the end of the
second phase, there will be a path of length $t^{\prime}$ in $\hat{G}$ between
$c_{v}$ and $c_{u}$. Since each of the clusters in $\hat{G}$ have radius $t$
at the time they get passed to the second phase, a path on $\hat{G}$ with
stretch $O(t^{\prime})$ corresponds to a path in $G$ with stretch
$O(tt^{\prime})$. The claim follows when $t=t^{\prime}=\sqrt{n}$. ∎

##  4 Cluster-merging Approach

Following the general paradigm of Baswana and Sen [BS07], our algorithm
proceeds in two phases. In the first phase, the algorithm creates a sequence
of growing clusters, where initial clusters are singleton vertices. This is
similar to the first phase in the [BS07] algorithm, but has the following
crucial differences:

  * •

In each epoch, a sub-sampled set of clusters (from the previous epoch) expand,
by engulfing _neighboring clusters_ that were _not_ sub-sampled. In [BS07],
the sub-sampled clusters only engulf _neighboring vertices_.

  * •

Consequently, the radius of our clusters increase by a factor of $3$ (roughly)
in every epoch, and thus the radius after epoch $i$ is $O(3^{i})$. On the
other hand, the cluster radius in [BS07] increments by $1$ in each epoch,
leading to a radius of $i$ at the end of epoch $i$.

  * •

The sub-sampling probability at epoch $i$ is $n^{-\frac{2^{i-1}}{k}}$, i.e.,
the probabilities _decrease_ as a _double exponential_ , as opposed to [BS07],
where the probabilities are always the same.

  * •

Our algorithm proceeds for $O(\log k)$ epochs as opposed to $k$ epochs in
[BS07].

  * •

The final stretch we achieve is $O(k^{\log 3})$, instead of $O(k)$ as in
[BS07].

Based on the aforementioned sampling probabilities, the final number of
clusters will be $n^{1/k}$. Subsequently, we enter the second phase, where we
add edges between vertices that still have un-processed edges and the final
clusters. The final output is a set of edges $E_{S}$ that represent the
spanner.

The main benefit of our approach, compared to [BS07], is that it provides a
significantly faster way of constructing spanners in $\mathsf{MPC}$. Namely,
the algorithm of [BS07] inherently requires $O(k)$ iterations and it is not
clear how to implement it in $o(k)$ $\mathsf{MPC}$ rounds while not exceeding
a total memory of $\tilde{O}(m)$. On the other hand, in Section 6 we show that
each epoch of our algorithm can be implemented in $O(1)$ $\mathsf{MPC}$
rounds. This implies the above approach can be implemented in $O(\log{k})$
$\mathsf{MPC}$ rounds.

###  4.1 Algorithm

In this section we describe the cluster-merging approach. We will use the
following notation for inter-cluster edges.

######  Definition 4.1.

We define $\mathsf{E}(c_{1},c_{2})$ to be the set of edges in $\mathsf{E}$
that have one endpoint in cluster $c_{1}$ and the other endpoint in cluster
$c_{2}$. We will also abuse this notation, and use $\mathsf{E}(v,c)$ to denote
all edges between _vertex_ $v$ and cluster $c$.

Before a formal description of our algorithm, we also need two more
definitions.

######  Definition 4.2.

A _cluster_ $c$ is a set of vertices $V_{c}\in V$ along with a rooted tree
$T(c)=(V_{c},E_{c})$. The “center” of the cluster is defined as the root of
$T$ (the oldest member), and the “radius” of the cluster is the depth of $T$
(from the root).

######  Definition 4.3.

A clustering of a graph $G=(V,E)$ is a partition of $V$ into a set of disjoint
clusters $\mathcal{C}$, such that for all $c,c^{\prime}\in\mathcal{C}$, we
have $V_{c}\cap V_{c^{\prime}}=\emptyset$.

We next describe the two phases of our algorithm.

###### Phase 1:

The first phase proceeds through $\log k$ epochs. Let $\mathcal{C}_{0}$ be the
clustering of $V$ where each $v\in V$ is a cluster. At a high-level, during
epoch $i$, we sub-sample a set of clusters
$\mathcal{R}^{(i)}\subseteq\mathcal{C}^{(i-1)}$, we will connect the clusters
to each other as follows: Consider a cluster $c$ that is _not_ sampled at
epoch $i$. If $c$ does _not_ have a _neighboring sampled cluster_ in
$\mathcal{R}^{(i)}$, we merge it with each of the (un-sampled) neighboring
clusters in $\mathcal{C}^{(i-1)}$, using the lowest weight edge. On the other
hand, if $c$ has _at least one_ neighboring sampled cluster, then we find the
closest such cluster and merge it to $c$ using the lowest weight edge, say
$e$. Additionally, in the weighted case, we also add an edge to each of the
other neighboring clusters, that are adjacent to $c$ with an edge of _weight
strictly lower than_ that of $e$.

Throughout, we maintain a set $\mathsf{E}$ (initialized to $E$) containing the
unprocessed edges. During each epoch, edges are removed from $\mathsf{E}$.
During execution, some edges from $\mathsf{E}$ are added to the set of spanner
edges $E_{S}$, and some are discarded. Specifically, when we merge clusters
$c_{1}$ and $c_{2}$, only the lowest weight edge in $\mathsf{E}(c_{1},c_{2})$
is added to the spanner $E_{S}$, and all other edges in
$\mathsf{E}(c_{1},c_{2})$ are discarded from $\mathsf{E}$ (the notation
$\mathsf{E}(\cdot,\cdot)$ is in Definition 4.1). We will use
$\mathsf{E}^{(i)}$ to denote the state of the set $\mathsf{E}$ at the end of
epoch $i$. During epoch $i$, we also construct a set of edges
$\mathcal{E}^{(i)}\subseteq E_{S}$, containing the edges that are used to
connect (merge) _sampled_ old clusters with _un-sampled_ clusters to form the
new ones $\mathcal{C}^{(i)}$.

At epoch $i$, for $i=1\ldots\log{k}$, we perform the following steps:

  1. (1)

Sample a set of clusters $\mathcal{R}^{(i)}\subseteq\mathcal{C}^{(i-1)}$,
where each $c\in\mathcal{C}^{(i-1)}$ is chosen to be a member of
$\mathcal{R}^{(i)}$ with probability $n^{-\frac{2^{i-1}}{k}}$. Initialize
$\mathcal{E}^{(i)}$ to the subset of edges in $\mathcal{E}^{(i-1)}$ that are
contained in some cluster $c\in\mathcal{R}^{(i)}$.

  2. (2)

Consider a cluster $c\in\mathcal{C}^{(i-1)}\setminus\mathcal{R}^{(i)}$ that
has a neighbor in $R^{(i)}$. Let $\mathcal{N}^{(i)}(c)\in\mathcal{R}^{(i)}$ be
the _closest neighboring sampled cluster_ of $c$.

    1. (a)

Add the lowest weight edge $e\in\mathsf{E}(c,\mathcal{N}^{(i)}(c))$ to both
$\mathcal{E}^{(i)}$ and $E_{S}$ and remove the entire set
$\mathsf{E}(c,\mathcal{N}^{(i)}(c))$ from $\mathsf{E}$.

    2. (b)

For all clusters $c^{\prime}\in\mathcal{C}^{(i-1)}$ adjacent to $c$ with any
edge of weight strictly less than $e$, add the lowest weight edge in
$\mathsf{E}(c,c^{\prime})$ to $E_{S}$ and then discard all the edges in
$\mathsf{E}(c,c^{\prime})$ from $\mathsf{E}$.

  3. (3)

Consider a cluster $c\in\mathcal{C}^{(i-1)}\setminus\mathcal{R}^{(i)}$ that
has _no_ neighbor in $\mathcal{R}^{(i)}$. Let
$C^{\prime}\subseteq\mathcal{C}^{(i-1)}$ be all the clusters of
$\mathcal{C}^{(i-1)}$ in the _neighborhood_ of $c$. For each $c_{j}\in
C^{\prime}$ move the lowest weight edge in $\mathsf{E}(c,c_{j})$ to $E_{S}$
and discard all edges in $\mathsf{E}(c,c_{j})$ from $\mathsf{E}$.

  4. (4)

The clustering $\mathcal{C}^{(i)}$ is formed by taking the clusters in
$\mathcal{R}^{(i)}$, and then extending them using all the edges in
$\mathcal{E}^{(i)}$ to absorb other clusters that are connected to
$\mathcal{R}^{(i)}$ (using only edges in $\mathcal{E}^{(i)}$).

     * •

Specifically, let $c\in\mathcal{R}^{(i)}$ be a sampled cluster, and let
$\Delta^{(i-1)}(c)=\\{\bar{c}\in\mathcal{C}^{(i-1)}\mid
E(c,\bar{c})\cap\mathcal{E}^{(i)}\not=\emptyset\\}$ be the set of adjacent
clusters that will be absorbed. Each such $c$ results a new cluster
$c^{\prime}\in\mathcal{C}^{(i)}$, where $c^{\prime}$ has the same root node as
$c$, and the tree $T(c^{\prime})$ is formed by attaching the trees
$T(\bar{c})$ (for each $\bar{c}\in\Delta^{(i-1)}(c)$), to the corresponding
leaf node of the tree $T(c)$, using the appropriate edge in
$E(c,\bar{c})\cap\mathcal{E}^{(i)}$ (by construction, there is exactly one
such edge).

  5. (5)

Remove all edges $(u,v)\in\mathsf{E}$ where $u$ and $v$ belong to the same
cluster in $\mathcal{C}^{(i)}$. This set $\mathsf{E}$ at the end of the
$i^{th}$ epoch is denoted $\mathsf{E}^{(i)}$. We then contract and form the
new quotient graph (super-graph) and proceed to the next epoch.

###### Phase 2:

In the second phase, let $V^{\prime}$ be the set of all endpoints of the
remaining edges $\mathsf{E}^{(\log k)}$. For each $v\in V^{\prime}$ and each
$c\in\mathcal{C}^{(\log k)}$, we add the lowest edge in $\mathsf{E}(v,c)$ to
$E_{S}$ before discarding the edges in $\mathsf{E}(v,c)$.

###  4.2 Analysis of Phase 1

We first show that, for each edge $e=(u,v)$ that is discarded (not added to
$E_{S}$), there exists a path from $u$ to $v$ in $E_{S}$, of weight at most
$k\cdot w_{e}$ (see Theorem 4.10), i.e., the edge $e$ is _spanned_ by existing
spanner edges in $E_{S}$. Next, in Section 4.2.2, we show that the number of
edges added to the spanner $E_{S}$ during phase 1, is $O(n^{1+1/k}\log k)$ in
expectation (see Theorem 4.13).

####  4.2.1 Stretch Analysis

We begin by providing some definitions used throughout the analysis, and then
get into a formal stretch analysis.

######  Definition 4.4 (Weighted-Stretch Radius).

$\mathcal{C}$ is a clustering of weighted-stretch radius $r$ with respect to
an edge set $\mathsf{E}$ in a graph $G$ if and only if

  1. (A)

For all $c\in\mathcal{C}$, the cluster $c$ has radius at most $r$
(equivalently, $T_{c}$ has depth at most $r$).

  2. (B)

For each edge $e=(x,v)\in\mathsf{E}$ such that $x\in c\in\mathcal{C}$, all
edges on the path from $x$ to the root of $T_{c}$ have weight less than or
equal to $w_{e}$.

######  Definition 4.5 (Cluster of a vertex).

For a vertex $v$, $\mathbf{c}^{(i)}(v)$ refers to the cluster of
$\mathcal{C}^{(i)}$ containing $v$.

######  Definition 4.6 (Cluster center).

For a vertex $v$, $\mathcal{F}^{(i)}(v)$ denotes the center of
$\mathbf{c}^{(i)}(v)$.

First, an inductive argument shows that all the remaining edges in
$\mathsf{E}^{(i)}$ are between the current set of clusters
$\mathcal{C}^{(i)}$.

######  Lemma 4.7.

During the execution of Phase 1, any edge $e=(u,v)\in\mathsf{E}$ at the end of
epoch $i$ is such that both end-points are members of distinct clusters in
$\mathcal{C}^{(i)}$.

###### Proof.

We prove this statement by induction.

Base case: Before the first epoch, $\mathsf{E}=E$ and all the edges have
endpoints in $\mathcal{C}_{0}$ since this is the set of all vertices.

Inductive hypothesis: Assume that at the beginning of epoch $i$, all edges in
$\mathsf{E}$ have both endpoints in distinct clusters of
$\mathcal{C}^{(i-1)}$.

Induction: Towards a contradiction, assume that there is an edge
$e=(u,v)\in\mathsf{E}$ that survives to the end of epoch $i$ and has at least
one endpoint that is not in any cluster of $\mathcal{C}^{(i)}$. Without loss
of generality, assume that this endpoint is $v$. Note that
$\mathbf{c}^{(i-1)}(v)$ and $\mathbf{c}^{(i-1)}(u)$ exists by the inductive
hypothesis. (See Definition 4.5 for the definition of
$\mathbf{c}^{(i-1)}(\cdot)$.)

If $\mathbf{c}^{(i-1)}(v)$ is adjacent to any cluster in $\mathcal{R}^{(i)}$,
then it would have been processed in Step 2. Therefore, some edge between
$\mathbf{c}^{(i-1)}(v)$ and $r\in\mathcal{R}^{(i)}$ was added to
$\mathcal{E}^{(i)}$. In this case, $\mathbf{c}^{(i-1)}(v)$ will be absorbed
into a new cluster in $\mathcal{C}^{(i)}$ (see Step 4), and consequently, $v$
is also a member of $\mathcal{C}^{(i)}$. Hence, $\mathbf{c}^{(i-1)}(v)$ was
not adjacent to any cluster in $\mathcal{R}^{(i)}$.
So, $\mathbf{c}^{(i-1)}(v)$ was processed in Step 3. In this case, all edges
in $\mathsf{E}(\mathbf{c}^{(i-1)}(v),\mathbf{c}^{(i-1)}(u))$ were discarded
(one of the edges was added to the spanner $E_{S}$), and hence this case could
not happen neither. This now leads to a contradiction (as Step 2 or Step 3 has
to occur) and implies that both $u$ and $v$ belong to some clusters in
$\mathcal{C}^{(i)}$.

It remains to show that $u$ and $v$ belong to distinct clusters of
$\mathcal{C}^{(i)}$. But this follows directly from Step 5. ∎

Next, we argue inductively that in each epoch the cluster radius grows by a
factor of $3$.

######  Theorem 4.8.

At the end of epoch $i$, $\mathcal{C}^{(i)}$ is a clustering of weighted-
stretch radius (see Definition 4.4) at most $\frac{3^{i}-1}{2}$ with respect
to the current set $\mathsf{E}^{(i)}$.

###### Proof.

We first prove Property (A) and then Property (B) of Definition 4.4. Each of
the properties are proved by an inductive argument.

###### Property (A) of Definition 4.4.

As a base case, notice that before the first epoch, each cluster has radius
$0$.

During epoch $i$, each cluster $c^{\prime}\in\mathcal{C}^{(i)}$ is a union of
a cluster $c\in\mathcal{R}^{(i)}\subseteq\mathcal{C}^{(i-1)}$, and some number
of clusters in $\mathcal{C}^{(i-1)}$ that are adjacent to $c$. The root of
cluster $c^{\prime}$ remains the same as the root of $c$. However, the radius
of $c^{\prime}$ becomes the depth of the new rooted tree, which can be at most
three times the old radius plus one (for the edge connecting the adjacent
cluster). Thus the radius (not necessarily strong) of the new larger cluster
is at most $3r+1$, where $r$ is the radius of $\mathcal{C}^{(i-1)}$. For an
illustration, see Fig. 1 and consider the distance between the center of
cluster $c$ and vertex $x$. Assuming that the inductive hypothesis is
satisfied for $\mathcal{C}^{(i-1)}$ i.e., $r\leq\frac{3^{i-1}-1}{2}$, we see
that the radius of $\mathcal{C}^{(i)}$ is at most $\frac{3^{i}-1}{2}$.

Note that this proof implies that Property (A) holds independently of Property
(B).

###### Property (B) of Definition 4.4.

As an inductive hypothesis, assume that the clustering $\mathcal{C}^{(i-1)}$
has weighted-stretch radius $\frac{3^{i-1}-1}{2}$ with respect to
$\mathsf{E}^{(i-1)}$. Now, consider an edge $e=(x,y)\in\mathsf{E}^{(i)}$, such
that $x\in c^{\prime}\in\mathcal{C}^{(i)}$ and $y\not\in c^{\prime}$. Note
that by Lemma 4.7, each edge $e\in\mathsf{E}^{(i)}$ is of this form, i.e., the
endpoints of $e$ belong to distinct clusters of $\mathcal{C}^{(i)}$. According
to Step 4, cluster $c^{\prime}$ was formed from a sampled cluster
$c\in\mathcal{R}^{(i)}$ that _engulfed_ the adjacent clusters in
$\Delta^{(i-1)}(c)$

Figure 1: Sampled super-node $c$ will engulf $\bar{c}$, which is also a
supernode (not sampled). Both correspond to clusters of radius $r$.

###### Case $x\in\bar{c}\in\Delta^{(i-1)}(c)$:

Let $w^{\prime}$ be the weight of the edge $(u,v)\in\mathcal{E}^{(i)}$ that
connects $u\in T_{c}$ to $v\in T_{\bar{c}}$, and let $w_{e}$ be the weight of
the edge $e=(x,y)$ (see Fig. 1). We construct a path from $x$ to
$\mathcal{F}^{(i)}(x)$, by concatenating the following paths
$x{\color[rgb]{0.83,0.67,0.00}\definecolor[named]{pgfstrokecolor}{rgb}{0.83,0.67,0.00}\raisebox{2.15277pt}{
\leavevmode\hbox to16.27pt{\vbox to4.31pt{\pgfpicture\makeatletter\hbox{\hskip
1.61499pt\lower-2.15332pt\hbox to0.0pt{\pgfsys@beginscope\pgfsys@invoke{
}\definecolor[named]{pgfstrokecolor}{rgb}{0.83,0.67,0.00}\pgfsys@color@rgb@stroke{0.83}{0.67}{0.00}\pgfsys@invoke{
}\pgfsys@color@rgb@fill{0.83}{0.67}{0.00}\pgfsys@invoke{
}\pgfsys@setlinewidth{0.4pt}\pgfsys@invoke{ }\nullfont\hbox
to0.0pt{\pgfsys@beginscope\pgfsys@invoke{ }{}{{}}{}
{}{}\pgfsys@beginscope\pgfsys@invoke{
}\pgfsys@setlinewidth{0.86111pt}\pgfsys@invoke{ }{}{{
{\pgfsys@beginscope\pgfsys@setlinewidth{0.68889pt}\pgfsys@setdash{}{0.0pt}\pgfsys@roundcap\pgfsys@roundjoin{}
{}{}{} {}{}{}
\pgfsys@moveto{-1.61499pt}{2.15332pt}\pgfsys@curveto{-1.48041pt}{1.34583pt}{0.0pt}{0.13458pt}{0.40375pt}{0.0pt}\pgfsys@curveto{0.0pt}{-0.13458pt}{-1.48041pt}{-1.34583pt}{-1.61499pt}{-2.15332pt}\pgfsys@stroke\pgfsys@endscope}}
}{}{}{{}}\pgfsys@moveto{0.0pt}{0.0pt}\pgfsys@lineto{13.47818pt}{0.0pt}\pgfsys@stroke\pgfsys@invoke{
}{{}{{}}{}{}{{}}{{{}}{{{}}{\pgfsys@beginscope\pgfsys@invoke{
}\pgfsys@transformcm{1.0}{0.0}{0.0}{1.0}{13.47818pt}{0.0pt}\pgfsys@invoke{
}\pgfsys@invoke{ \lxSVG@closescope }\pgfsys@invoke{\lxSVG@closescope
}\pgfsys@endscope}}{{}}}} \pgfsys@invoke{\lxSVG@closescope }\pgfsys@endscope
\pgfsys@invoke{\lxSVG@closescope
}\pgfsys@endscope{}{}{}\hss}\pgfsys@discardpath\pgfsys@invoke{\lxSVG@closescope
}\pgfsys@endscope\hss}}\lxSVG@closescope\endpgfpicture}}}}\mathcal{F}^{(i-1)}(x){\color[rgb]{0.83,0.67,0.00}\definecolor[named]{pgfstrokecolor}{rgb}{0.83,0.67,0.00}\raisebox{2.15277pt}{
\leavevmode\hbox to15.09pt{\vbox to0.86pt{\pgfpicture\makeatletter\hbox{\hskip
0.43056pt\lower-0.43056pt\hbox to0.0pt{\pgfsys@beginscope\pgfsys@invoke{
}\definecolor[named]{pgfstrokecolor}{rgb}{0.83,0.67,0.00}\pgfsys@color@rgb@stroke{0.83}{0.67}{0.00}\pgfsys@invoke{
}\pgfsys@color@rgb@fill{0.83}{0.67}{0.00}\pgfsys@invoke{
}\pgfsys@setlinewidth{0.4pt}\pgfsys@invoke{ }\nullfont\hbox
to0.0pt{\pgfsys@beginscope\pgfsys@invoke{ }{}{{}}{}
{}{}\pgfsys@beginscope\pgfsys@invoke{
}\pgfsys@setlinewidth{0.86111pt}\pgfsys@invoke{
}{}{}{}{}{{}}\pgfsys@moveto{0.0pt}{0.0pt}\pgfsys@lineto{13.47818pt}{0.0pt}\pgfsys@stroke\pgfsys@invoke{
}{{}{{}}{}{}{{}}{{{}}{{{}}{\pgfsys@beginscope\pgfsys@invoke{
}\pgfsys@transformcm{1.0}{0.0}{0.0}{1.0}{13.47818pt}{0.0pt}\pgfsys@invoke{
}\pgfsys@invoke{ \lxSVG@closescope }\pgfsys@invoke{\lxSVG@closescope
}\pgfsys@endscope}}{{}}}} \pgfsys@invoke{\lxSVG@closescope }\pgfsys@endscope
\pgfsys@invoke{\lxSVG@closescope
}\pgfsys@endscope{}{}{}\hss}\pgfsys@discardpath\pgfsys@invoke{\lxSVG@closescope
}\pgfsys@endscope\hss}}\lxSVG@closescope\endpgfpicture}}}}v{\color[rgb]{0.83,0.67,0.00}\definecolor[named]{pgfstrokecolor}{rgb}{0.83,0.67,0.00}\raisebox{2.15277pt}{
\leavevmode\hbox to15.09pt{\vbox to0.86pt{\pgfpicture\makeatletter\hbox{\hskip
0.43056pt\lower-0.43056pt\hbox to0.0pt{\pgfsys@beginscope\pgfsys@invoke{
}\definecolor[named]{pgfstrokecolor}{rgb}{0.83,0.67,0.00}\pgfsys@color@rgb@stroke{0.83}{0.67}{0.00}\pgfsys@invoke{
}\pgfsys@color@rgb@fill{0.83}{0.67}{0.00}\pgfsys@invoke{
}\pgfsys@setlinewidth{0.4pt}\pgfsys@invoke{ }\nullfont\hbox
to0.0pt{\pgfsys@beginscope\pgfsys@invoke{ }{}{{}}{}
{}{}\pgfsys@beginscope\pgfsys@invoke{
}\pgfsys@setlinewidth{0.86111pt}\pgfsys@invoke{
}{}{}{}{}{{}}\pgfsys@moveto{0.0pt}{0.0pt}\pgfsys@lineto{13.47818pt}{0.0pt}\pgfsys@stroke\pgfsys@invoke{
}{{}{{}}{}{}{{}}{{{}}{{{}}{\pgfsys@beginscope\pgfsys@invoke{
}\pgfsys@transformcm{1.0}{0.0}{0.0}{1.0}{13.47818pt}{0.0pt}\pgfsys@invoke{
}\pgfsys@invoke{ \lxSVG@closescope }\pgfsys@invoke{\lxSVG@closescope
}\pgfsys@endscope}}{{}}}} \pgfsys@invoke{\lxSVG@closescope }\pgfsys@endscope
\pgfsys@invoke{\lxSVG@closescope
}\pgfsys@endscope{}{}{}\hss}\pgfsys@discardpath\pgfsys@invoke{\lxSVG@closescope
}\pgfsys@endscope\hss}}\lxSVG@closescope\endpgfpicture}}}}u{\color[rgb]{0.83,0.67,0.00}\definecolor[named]{pgfstrokecolor}{rgb}{0.83,0.67,0.00}\raisebox{2.15277pt}{
\leavevmode\hbox to15.09pt{\vbox to0.86pt{\pgfpicture\makeatletter\hbox{\hskip
0.43056pt\lower-0.43056pt\hbox to0.0pt{\pgfsys@beginscope\pgfsys@invoke{
}\definecolor[named]{pgfstrokecolor}{rgb}{0.83,0.67,0.00}\pgfsys@color@rgb@stroke{0.83}{0.67}{0.00}\pgfsys@invoke{
}\pgfsys@color@rgb@fill{0.83}{0.67}{0.00}\pgfsys@invoke{
}\pgfsys@setlinewidth{0.4pt}\pgfsys@invoke{ }\nullfont\hbox
to0.0pt{\pgfsys@beginscope\pgfsys@invoke{ }{}{{}}{}
{}{}\pgfsys@beginscope\pgfsys@invoke{
}\pgfsys@setlinewidth{0.86111pt}\pgfsys@invoke{
}{}{}{}{}{{}}\pgfsys@moveto{0.0pt}{0.0pt}\pgfsys@lineto{13.47818pt}{0.0pt}\pgfsys@stroke\pgfsys@invoke{
}{{}{{}}{}{}{{}}{{{}}{{{}}{\pgfsys@beginscope\pgfsys@invoke{
}\pgfsys@transformcm{1.0}{0.0}{0.0}{1.0}{13.47818pt}{0.0pt}\pgfsys@invoke{
}\pgfsys@invoke{ \lxSVG@closescope }\pgfsys@invoke{\lxSVG@closescope
}\pgfsys@endscope}}{{}}}} \pgfsys@invoke{\lxSVG@closescope }\pgfsys@endscope
\pgfsys@invoke{\lxSVG@closescope
}\pgfsys@endscope{}{}{}\hss}\pgfsys@discardpath\pgfsys@invoke{\lxSVG@closescope
}\pgfsys@endscope\hss}}\lxSVG@closescope\endpgfpicture}}}}\mathcal{F}^{(i)}(u)=\mathcal{F}^{(i)}(x)$.
Since we know that the edge $e=(x,y)$ survived Step 2b, it must have weight at
least as the edge $(u,v)$, i.e., $w^{\prime}\leq w_{e}$. By the inductive
hypothesis for level $i-1$, all edges on the first two segments of the above
path have weight at most $w^{\prime}$. Similarly, the first two segments of
the path only contain edges with weight at most $w_{e}$ (again using the
inductive hypothesis at $i-1$). Furthermore, the number of edges on the path
is at most $r+r+1+r=3r+1$, where $r$ is the weighted-stretch radius of
clustering at the previous epoch.

###### Case $x\in c$:

Since $e=(x,y)\in\mathsf{E}^{(i)}\implies(x,y)\in\mathsf{E}^{(i-1)}$, the
inductive hypothesis implies that the path from $x$ to the root of $T_{c}$
(the center is $\mathcal{F}^{(i-1)}(x)=\mathcal{F}^{(i)}(x)$) only uses edges
of weight at most $w_{e}$. ∎

######  Corollary 4.9.

The weighted-stretch radius of the final clustering $\mathcal{C}^{(\log k)}$
is $\frac{k^{\log 3}-1}{2}$.

Using Theorem 4.8, we show the following.

######  Theorem 4.10.

For all edges $e=(u,v)$ removed in Phase 1, there exists a path between $u$
and $v$ in $E_{S}$ of weight at most $w_{e}\cdot k^{\log 3}$.

###### Proof.

Depending on when $e=(u,v)$ was removed from $\mathsf{E}$, there are three
cases to consider: Step 2, Step 3 and Step 5. Before analyzing these cases,
note that by Lemma 4.7 after a cluster is formed no edge is removed from it in
the subsequent epochs. This fact will be important in the rest of this proof
as when we show that there is a path between $u$ and $v$ of weight at most
$k^{\log{3}}\cdot w_{e}$, we will show that this path belongs to a cluster (or
to two adjacent ones). Hence, once this path belongs to a cluster it also
belongs to $E_{S}$.

###### Case $e$ was removed in Step 2 in epoch $i$.

Let $e_{1}=(x,y)$ be the edge that was kept between $\mathbf{c}^{(i-1)}(u)$
and $\mathbf{c}^{(i-1)}(v)$. Let $x\in\mathbf{c}^{(i-1)}(u)$ and
$y\in\mathbf{c}^{(i-1)}(v)$. Then, by Theorem 4.8 there exists a path from $u$
to $x$ within $\mathbf{c}^{(i-1)}(u)$ of weight at most
$2\tfrac{3^{i-1}-1}{2}\cdot w_{e}$. Similarly, there is a path between $v$ and
$y$ within $\mathbf{c}^{(i-1)}(v)$ of weight at most
$2\tfrac{3^{i-1}-1}{2}\cdot w_{e}$. Since $E_{S}$ also contains the edge
$e_{1}$ and $w_{e_{1}}\leq w_{e}$ by Steps 2a and 2b, we have that $E_{S}$
contains a path between $u$ and $v$ of weight at most $(2(3^{i-1}-1)+1)\cdot
w_{e}<3^{i}\cdot w_{e}\leq k^{\log{3}}w_{e}$.

###### Case $e$ was removed in Step 3 in epoch $i$.

This case is analogous to the previous one.

###### Case $e$ was removed in Step 5 in epoch $i$.

Let $c\in\mathcal{C}^{(i)}$ be the cluster from which $e=(v_{1},v_{2})$ was
removed. By construction, this edge is between two clusters $c_{1}$ and
$c_{2}$ from $\mathcal{C}^{(i-1)}$ that are merged with $c$ in this epoch.
Assume that $v_{1}\in c_{1}$. Let $e_{1}=(x_{1},x)$ be the edge via which
$c_{1}$ was merged to $c$, and let $x_{1}\in c_{1}$. Also, let
$e_{2}=(y_{2},y)$ be the edge with which $c_{2}$ was merged with $c$, and let
$y_{2}\in c_{2}$. Since $e$ was not removed before Step 5, it means that when
$c_{1}$ and $c_{2}$ got merged with $c$ the edge $e$ was not discarded in Step
2b. This in turn implies that $w_{e}\geq w_{e_{1}}$ and $w_{e}\geq w_{e_{2}}$.

Now, similar to the analysis of Step 2, using Theorem 4.8 we have that there
is a path in $E_{S}$ between $v_{1}$ and $x_{1}$ of weight at most
$(3^{i-1}-1)\cdot w_{e}$. Also, there is a path between $x$ and $y$ in $E_{S}$
of weight at most $(3^{i-1}-1)\cdot w_{e_{1}}\leq(3^{i-1}-1)\cdot w_{e}$.
Finally, there is a path between $v_{2}$ and $y_{2}$ in $E_{S}$ of weight at
most $(3^{i-1}-1)\cdot w_{e}$. Combining these together, $E_{S}$ contains a
path between $v_{1}$ and $v_{2}$ of weight at most $(3\cdot(3^{i-1}-1)+2)\cdot
w_{e}=(3^{i}-1)\cdot w_{e}\leq k^{\log{3}}\cdot w_{e}$, as desired. ∎

###### Stretch Analysis of Phase 2.

Recall, that in the second phase, we let $V^{\prime}$ be the set of all
endpoints of the _un-processed_ edges in $\mathsf{E}^{(\log k)}$.
Subsequently, we add the lowest edge in $\mathsf{E}(v,c)$ to $E_{S}$ before
discarding the edges in $\mathsf{E}(v,c)$, for each $v\in V^{\prime}$ and
$c\in\mathcal{C}^{(\log k)}$.

Using the weighted stretch radius of the final clustering from Corollary 4.9,
we can prove the following lemma, using an argument similar to Theorem 4.10.
We omit the formal proof to avoid repetition.

######  Lemma 4.11.

For each edge $w_{e}=(v,c)\in V^{\prime}\times\mathcal{C}^{(\log k)}$ removed
in Phase 2, there exists a path between $u$ and $v$ in $E_{S}$ of weight at
most $w_{e}\cdot k^{\log 3}$.

####  4.2.2 Size Analysis

Next, we provide an upper-bound on $E_{S}$. First, we upper-bound the number
of clusters in each $\mathcal{C}^{(i)}$.

######  Lemma 4.12.

For each $i\leq\log{k}$, in expectation it holds $|\mathcal{C}^{(i-1)}|\in
O\left(n^{1-\frac{2^{i-1}-1}{k}}\right)$.

###### Proof.

A cluster $c$ belongs to $\mathcal{C}^{(i-1)}$ only if $c$ was sampled to
$\mathcal{R}_{j}$ in Step 1 for each $1\leq j\leq i-1$.

This happens with probability
$\prod_{j=1}^{i-1}n^{-\frac{2^{j-1}}{k}}=n^{-\frac{2^{i-1}-1}{k}}$. Therefore,
$\mathbb{E}\left[|\mathcal{C}^{(i-1)}|\right]=n^{1-\frac{2^{i-1}-1}{k}}$. ∎

Building on Lemma 4.12 we obtain the following claim.

######  Theorem 4.13.

During Phase 1, in expectation there are $O\left(n^{1+1/k}\cdot\log k\right)$
edges added to $E_{S}$.

###### Proof.

Steps 1, 4 and 5 do not affect $E_{S}$. Hence, we analyze only the remaining
steps.

Consider epoch $i$. Fix a cluster $c\in\mathcal{C}^{(i-1)}$ (which might or
might not be in $\mathcal{R}^{(i)}$). We will upper-bound the number of edges
that in expectation are added when considering $c$.

Let $p=n^{-\frac{2^{i-1}}{k}}$. Recall that each cluster $c^{\prime}$ is added
from $\mathcal{C}^{(i-1)}$ to $\mathcal{R}^{(i)}$ independently and with
probability $p$. Order the clusters $c^{\prime}$ of $\mathcal{C}^{(i-1)}$
adjacent to $c$ in the non-decreasing order by the lowest-edge in
$\mathsf{E}(c,c^{\prime})$. Consider the first $A$ among those sorted
clusters.

Taking into account both Steps 2 and 3, an edge from $c$ to the $A$-th cluster
is added to $E_{S}$ if and only if all previous clusters are not sampled,
which happens with probability $(1-p)^{A-1}$. Hence, the expected number of
edges added by $c$ is upper-bounded by
$\sum_{A=1}^{n}(1-p)^{A-1}<\sum_{A=1}^{\infty}(1-p)^{A-1}=\frac{1}{p}.$ Hence,
we have that in expectation the number of edges added to the spanner when
considering $c$ is $O(1/p).$

∎

###### Size Analysis of Phase 2.

Finally, As a corollary of Lemma 4.12, we see that in expectation
$|\mathcal{C}^{(\log k)}|\in O\left(n^{1/k}\right)$. Therefore, the number of
edges added in Phase 2 is at most $|V^{\prime}|\cdot|\mathcal{C}^{(\log
k)}|\in O\left(n^{1+1/k}\right)$. This concludes our spanner construction, and
yields the main theorem.

######  Theorem 4.14.

Given a weighted graph $G$, the cluster-merging algorithm builds a spanner of
stretch $O(k^{\log{3}})$ and expected size $O(n^{1+1/k}\cdot\log{k})$, within
$O(\log{k})$ epochs.

##  5 General Trade-off between Stretch and Number of Rounds

In this section, we provide an overview of an algorithm that combines ideas of
Section 3 and Section 4, with the cluster-vertex merging concept that we
described earlier. This gives us a general tradeoff between number of rounds,
and stretch. For instance, we can construct a spanner with stretch
$k^{1+o(1)}$ in $\frac{\log^{2}(k)}{\log\log(k)}$ rounds. At a high-level, the
algorithm runs in a sequence of epochs, and each epoch performs $t$ iterations
of [BS07].

We can imagine the algorithm of [BS07] as being one extreme of this tradeoff
(when $t=k$). The algorithm of Section 3 generalizes this, by splitting the
$k$ iterations of [BS07] over two epochs, each with $\sqrt{k}$ iterations.
After the first set of $\sqrt{k}$ iterations (the first epoch), we _contract
the most recent clusters_ , and then repeat $\sqrt{k}$ iterations (the second
epoch) on the contracted graph. Importantly, the second epoch uses different
sampling probabilities – as if we were actually trying to construct a stronger
$\mathcal{O}(\sqrt{k})$ stretch spanner.

Meanwhile, the algorithm of Section 4 occupies the other extreme of our
tradeoff. this algorithm immediately contracts after a single “[BS07]-like
step”. Consequently, each step now becomes an “epoch”, and they all use
different sampling probabilities. With $\log k$ epochs, this is the
_“fastest”_ algorithm in our tradeoff, and thus has the worst stretch.

We interpolate between these extremes by repeating the following two steps:

  * •

In each epoch, we grow clusters, based on the cluster-vertex merging approach,
till a certain radius $t$ on the quotient graph, where each _super-node_ in
the graph is a contracted cluster from the previous epoch.

  * •

At the end of an epoch, we contract the clusters of radius $t$ to obtain the
quotient graph for the next epoch, adjust the sampling probabilities and
continue.

The parameter $t$ can be varied, thus resulting in a family of algorithms that
achieve our trade-offs. For instance, $t=1$ corresponds to Section 4,
$t=\sqrt{k}$ corresponds to Section 3, and $t=k$ brings us back to the
algorithm of [BS07].

The idea behind the generalization is that now, the stretch (equivalently, the
radius of clusters), rather than increasing by a multiplicative factor of $3$
in each epoch (as it did in Section 4), now it grows by a factor of $(2t+1)$
in each epoch. We again use the intuition that after each contraction, since
the remaining graph is smaller in size, we can afford to grow clusters faster,
and we adjust this rate by decreasing the sampling probabilities.

###  5.1 General Trade-off Algorithm

Let us first formalize the concept of a quotient graph before getting into the
algorithm details:

######  Definition 5.1.

Given a graph $G=(V,E)$ and a clustering $\mathcal{C}$, the quotient graph
$\hat{G}=(\mathcal{C},\hat{E})$, is defined as follows.222The quotient graph
is sometimes called a super-graph. Its vertices are the clusters, and there is
an edge between two clusters $c,c^{\prime}\in\mathcal{C}$, if there exist
$v^{\prime}\in c,v^{\prime}\in c^{\prime}$ such that $(v,v^{\prime})\in E$.

We next give a formal description of the algorithm. As can be expected, many
of the steps inside each epoch is similar to the algorithms of previous
sections and [BS07].

###### Phase 1:

The first phase of the algorithm proceeds in $l=\log k/\log(t+1)$ _epochs_.
Through the epochs, we create a sequence of clusterings
$\mathcal{D}^{(1)},\mathcal{D}^{(2)},\cdots,\mathcal{D}^{(l)}$, and graphs
$G^{(0)}\supset G^{(1)}\supset\cdots\supset G^{(l)}$. Here $G^{(0)}=G$, and
$G^{(i)}=(V^{(i)},E^{(i)})=\nicefrac{{G^{(i-1)}}}{{\mathcal{D}^{(i)}}}$ is the
quotient graph induced by the $i^{th}$ level clustering.

In what follows, we will use the term _vertex_ to refer to a member of
$V=V^{(0)}$ i.e. a vertex of the original graph. On the other hand, a _super-
node_ will refer to a member of any intermediate $V^{(i)}$ (including
$V^{(0)}$).

Throughout the execution, we maintain a set of edges $\mathsf{E}$. The state
of this set at the end of epoch $i$ is denoted as $\mathsf{E}^{(i)}$, and
$\mathsf{E}^{(0)}$ is initialized to all the edges in $G$. During epoch $i$,
edges are removed from $\mathsf{E}^{(i-1)}$ to form $\mathsf{E}^{(i)}$. Some
of these removed edges are added to the set of spanner edges $E_{S}$, and the
other ones are discarded.

At epoch $i$ we perform the following steps:

  1. (A)

Let $G^{(i-1)}=(V^{(i-1)},E^{(i-1)})$ be the graph at this epoch, and let
$\mathcal{D}^{(i)}_{0}$ be the initial clustering comprising of all singleton
_super-nodes_ i.e. $\mathcal{D}^{(i)}_{0}\stackrel{{\scriptstyle\text{\tiny\rm
def}}}{{=}}\\{\\{v\\}\mid v\in G^{(i)}\\}$.

Next (in Step B), we perform $t$ iterations of Baswana-Sen333with fixed
sampling probability $n^{-\frac{(t+1)^{i-1}}{k}}$ on $G^{(i)}$, in order to
obtain the final clustering $\mathcal{D}^{(i)}_{t}$. We also maintain a set of
edges $\mathcal{E}^{(i)}_{j}\subseteq E_{S}$ at iteration $j$, where the edges
in $\mathcal{E}^{(i)}_{j}$ induce the clustering at the $j^{th}$ iteration.
Henceforth, we will drop the superscript $(i)$ when it is clear from context.

We will use the set $\mathsf{E}^{(i)}_{j}$, (where $\mathsf{E}^{(i)}_{0}$ is
initialized to $\mathsf{E}^{(i-1)}$), to denote the set of unprocessed edges
at the end of iteration $j$. When clear from context, we will abbreviate this
as $\mathsf{E}$.

  2. (B)

For $j=1,2,\cdots,t$, iteration $j$ proceeds as follows:

    1. 1.

Sample a set of clusters $\mathcal{R}_{j}\subseteq\mathcal{D}_{j-1}$, where
each $c\in\mathcal{D}_{j-1}$ is chosen to be a member of $\mathcal{R}_{j}$
with probability $n^{-\frac{(t+1)^{i-1}}{k}}$. We also initialize
$\mathcal{E}_{j}$ to the subset of edges in $\mathcal{E}_{j-1}$ that are
contained in some cluster $c\in\mathcal{R}_{j}$.

    2. 2.

Consider all (contracted) _super-nodes_ $v\in
G^{(i-1)}\setminus\mathcal{R}_{j}$ that are not in any sampled cluster. We
define $\Gamma_{j}(v)\subseteq\mathcal{D}_{j-1}$ to be all the clusters of
$\mathcal{D}_{j-1}$ in the _neighborhood_ of $v$.

    3. 3.

For each super-node $v$, such that $\Gamma_{j}(v)$ intersects
$\mathcal{R}_{j}$ (i.e. super-nodes with some neighboring sampled cluster),
let $\mathcal{N}_{j}(v)\in\mathcal{R}_{j}\cap\Gamma_{j}(v)$ be the _closest
neighboring sampled cluster_ of $v$.

       * •

Add the lowest weight edge $e$ in $\mathsf{E}(v,\mathcal{N}_{j}(v))$ to both
$\mathcal{E}_{j}$ and $E_{S}$ and remove the entire set
$\mathsf{E}(v,\mathcal{N}_{j}(v))$ from $\mathsf{E}$.

       * •

For all clusters $c\in\Gamma_{j}(v)$ adjacent to $v$ with any edge of weight
strictly less than $e$, Add the lowest weight edge in $\mathsf{E}(v,c)$ to
$E_{S}$ and then discard all the edges in $\mathsf{E}(v,c)$ from $\mathsf{E}$.

    4. 4.

For all super-nodes $v$, such that
$\Gamma_{j}(v)\cap\mathcal{R}_{j}=\emptyset$ (i.e. super-nodes with no
neighboring sampled cluster),

       * •

For each $c\in\Gamma_{j}(v)$ move the lowest weight edge in $\mathsf{E}(v,c)$
to $E_{S}$ and discard all edges in $\mathsf{E}(v,c)$ from $\mathsf{E}$.

    5. 5.

The clustering $\mathcal{D}_{j}$ is formed by taking each cluster in
$\mathcal{R}_{j}$, and then extending it using the edges in $\mathcal{E}_{j}$,
to absorb other _super-nodes_ that are connected to $\mathcal{R}_{j}$ (using
only edges in $\mathcal{E}_{j}$).

Specifically, for each $c\in\mathcal{R}_{j}$, we define $\Delta_{j}(c)=\\{v\in
V^{(i-1)}\mid E^{(i-1)}(v,c)\cap\mathcal{E}_{j}\not=\phi\\}$ as the set of
adjacent _super-nodes_ that will be absorbed. Each such $c$ results a new
cluster $c^{\prime}\in\mathcal{D}_{j}$, where $c^{\prime}$ has the same root
super-node as $c$, and the tree $T(c^{\prime})$ is formed by attaching each
_super-node_ $v\in\Delta_{j-1}$ to the corresponding leaf node of $T(c)$,
using the appropriate edge in $E(c,\bar{c})\cap\mathcal{E}_{j}$ (by
construction, there is exactly one such edge).

Note that this description is simpler than the one presented in Step 4 in
Section 4.1, because we are working in the intermediate graph $G^{(i)}$.

    6. 6.

Remove all edges $(u,v)\in\mathsf{E}$ where $u$ and $v$ belong to the same
cluster in $\mathcal{D}_{j}$. This set $\mathsf{E}$ at the end of the $j^{th}$
iteration (in the $i^{th}$ epoch) is denoted by $\mathsf{E}^{(i)}_{j}$.

  3. (C)

Construct the quotient graph
$G^{(i+1)}=\nicefrac{{G^{(i)}}}{{\mathcal{D}^{(i)}_{t}}}$. For all pairs of
_super-nodes_ $u,v\in V^{(i)}$, we only keep the minimum weight edge between
$u$ and $v$ in $\mathsf{E}$ (currently denoted by $\mathsf{E}^{(i)}_{t}$). All
other edges are discarded, and the final set at the end of the epoch is
denoted by $\mathsf{E}^{(i)}$.

###### Phase 2:

In the second phase, let $V^{\prime}$ be the set of all endpoints of the
remaining edges $\mathsf{E}^{(l)}$. For each $v\in V^{\prime}$ and
$c\in\mathcal{D}^{(l)}_{t}$, we add the lowest edge in $\mathsf{E}(v,c)$ to
$E_{S}$ before discarding the edges in $\mathsf{E}^{(l)}(v,c)$.

###  5.2 Intermediate Graph Clusterings on Original Graph $G$

Notice that the clusterings $\mathcal{D}^{(i)}_{j}$ are defined on the
intermediate graphs $G^{(i)}$. For the sake of clarity, we define the
clustering $\mathcal{C}^{(i)}_{j}$, which is just the same
$\mathcal{D}^{(i)}_{j}$, but on the original graph $G=G^{(0)}$. We achieve
this by defining an operation that is essentially the inverse of the
contraction being performed in Step C. This operation allows us to define
$\mathcal{C}^{(i)}_{j}$ recursively as follows:

######  Definition 5.2 (Composition of Clusterings).

Given a clustering $\mathcal{C}^{(i-1)}$ defined on $G^{(0)}$, and clustering
$\mathcal{D}^{(i)}_{j}$ defined on the contracted graph
$G^{(i)}=\nicefrac{{G}}{{\mathcal{C}^{(i)}}}$, we can obtain the corresponding
$\mathcal{C}^{(i)}_{j}$, by replacing each super-node
$v\in\mathbf{c}_{v}\in\mathcal{D}^{(i)}_{j}$ by the corresponding (older)
cluster $\mathbf{c}^{(i-1)}_{v}\in\mathcal{C}^{(i-1)}$ (i.e. the super-node
$v\in G^{(i)}$ was formed by contracting a cluster
$\mathbf{c}^{(i-1)}_{v}\in\mathcal{C}^{(i-1)}$ in the original $G$).
Specifically, we modify the tree $T(\mathbf{c}_{v})$, by replacing each
internal _super-node_ $v$ by the corresponding tree
$T\left(\mathbf{c}^{(i-1)}_{v}\right)$. Thus, the final tree (also the
cluster) only contains vertices from $G=G^{(0)}$.

We also need to specify how we obtain $\mathcal{C}^{(i)}$, and the following
observation suffices.

######  Definition 5.3.

Since $\mathcal{C}^{(i)}_{t}$ corresponds to $\mathcal{D}^{(i)}_{t}$, and
$G^{(i+1)}=\nicefrac{{G^{(i)}}}{{\mathcal{D}^{(i)}_{t}}}$, and therefore, we
define $\mathcal{C}^{(i)}$ to be the same as $\mathcal{C}^{(i)}_{t}$. As a
base case, $\mathcal{C}^{(0)}\stackrel{{\scriptstyle\text{\tiny\rm
def}}}{{=}}\mathcal{D}^{(0)}$ (singleton clusters).

In the next section, we will see how the radius of the clusters is affected by
the composition defined above. This should be reminiscent of Theorem 4.8.
First, we start with some definitions towards proving an analog of Lemma 4.7.

######  Definition 5.4 (Cluster of a vertex).

For a vertex $v$ in the original vertex set $V$, $\mathbf{c}^{(i)}_{j}(v)$
refers to the cluster of $\mathcal{C}^{(i)}_{j}$ containing $v$.

######  Definition 5.5 (Cluster center).

For a vertex $v$, $\mathcal{F}^{(i)}_{j}(v)$ denotes the center of
$\mathbf{c}^{(i)}_{j}(v)$.

######  Lemma 5.6.

During the execution of Phase 1, for any un-processed edge
$e=(u,v)\in\mathsf{E}^{(i)}_{j}$ at the end of iteration $j$ in epoch $i$,
both end-points $u,v$ are members of distinct clusters in
$\mathcal{C}^{(i)}_{j}$.

###### Proof.

The proof is essentially a combination of Lemma 4.7 and Lemma 3.2, and we
proceed by induction on $j$. In the case that $i\not=0,j=0$, we note that the
clusters in $\mathcal{C}^{(i)}_{0}$ correspond exactly to the clusters in
$\mathcal{C}^{(i-1)}_{t}$. The edge set $\mathsf{E}^{(i)}_{0}$ is also just
$\mathsf{E}^{(i-1)}_{t}$ under a re-labeling, and thus induction on $j$
suffices.

Base case: Initially, $\mathsf{E}^{(0)}_{0}=E$, and all the edges have
endpoints in $\mathcal{C}^{(0)}_{0}$, since it is comprised of singleton
clusters $\\{v\\}$ for all vertices $v\in V^{(0)}=V$ (see Step A).

Inductive hypothesis: Assume that at the beginning of iteration $j$ within
epoch $i$, all edges in $\mathsf{E}^{(i)}_{j-1}$ have both endpoints in
distinct clusters of $\mathcal{C}^{(i)}_{j-1}$.

In what follows, we will be working on the graph $G^{(i)}$ during the $i^{th}$
epoch, and in general, we will drop the $(i)$ super-script from all symbols.

Induction: Towards a contradiction, assume that there is an edge
$e=(u,v)\in\mathsf{E}_{j}$ that survives to the end of iteration $j$, and has
at least one endpoint that is not in any cluster of $\mathcal{C}_{j}$. Without
loss of generality, assume that $v$ is such a “problematic” endpoint. Note
that since
$\mathsf{E}_{j}\subseteq\mathsf{E}_{j-1}\implies(u,v)\in\mathsf{E}_{j-1}$, the
inductive hypothesis implies that both $\mathbf{c}_{j-1}(v)$ and
$\mathbf{c}_{j-1}(u)$ exist (see Definition 5.4).

If the _super-node_ containing the “problematic” $v$ is adjacent to any
cluster in $\mathcal{R}_{j}$, then it would have been processed in Step B3.
Therefore, some edge between $\mathbf{c}_{j-1}(v)$ and
$\mathcal{N}_{j}(v)\in\mathcal{R}_{j}$ would have been added to
$\mathcal{E}_{j}$. In this case, the _super-node_ containing $v$ would be
absorbed into a new cluster in $\mathcal{C}_{j}$, i.e. $v\in
c\in\mathcal{C}_{j}$. Hence, in order to maintain the assumption that $v$ is
“problematic”, it must be the case that $v$ was not adjacent to any cluster in
$\mathcal{R}_{j}$.

What if the super-node containing $v$ was processed in Step B4? In this case,
all edges in $\mathsf{E}(v,\mathbf{c}_{j-1}(u))$ were discarded (one of the
edges was added to the spanner $E_{S}$), and hence
$(u,v)\not\in\mathsf{E}_{j}$.

This implies that neither Step B3 nor Step B4 can have occurred, and therefore
$v$ must have been a member of some cluster in $\mathcal{R}_{j}$, which in
turn implies that $v$ must be a member of some $c\in\mathcal{C}_{j}$. This
contradicts the assumption that $v$ was “problematic”.

Thus, we can conclude that both $u$ and $v$ belong to some clusters in
$\mathcal{C}_{j}$. It remains to show that $u$ and $v$ belong to _distinct_
clusters of $\mathcal{C}_{j}$, which follows directly from Step B6. ∎

###  5.3 General Stretch Analysis

In this section, we provide a stretch analysis for our general algorithm. For
this we need few more notations.

######  Definition 5.7.

For any epoch $i\in[l]$ and any $j\in[t]$, we define $r^{(i)}_{j}$ to be the
weighted-stretch radius of the clustering $\mathcal{C}^{(i)}_{j}$ with respect
to the edge set $\mathsf{E}^{(i)}_{j}$. For the sake of convenience, we also
define $r^{(i)}=r^{(i+1)}_{0}=r^{(i)}_{t}$.

######  Lemma 5.8.

For any $i\in[l]$ and any $j\in[t]$, we have $r^{(i)}_{j}\leq
r^{(i)}_{j-1}+2r^{(i-1)}+1$.

###### Proof.

The proof proceeds analogous to the induction in Theorem 4.8, where we claimed
that the new radius of clustering is upper bounded by $r+2r+1$ ($r$ being the
radius of the previous clustering). This was illustrated in Fig. 1. It is
strongly recommended that one reads the proof of Theorem 4.8 before this one,
since we will be refer to it.

The difference in the general case, is that the clusters present at a certain
iteration within the $i^{th}$ epoch, do not have a radius that only depends on
$i$. Instead, we now also have a dependence on the iteration number $j$.

Figure 2: A figure used in the proof of Lemma 5.8. Sampled super-node $c$ will
engulf $\bar{c}$, which is also a supernode (not sampled).

Specifically, following the proof of Theorem 4.8, we consider a cluster $c$ of
radius $r^{(i)}_{j-1}$ that is about to engulf a _super-node_ $\bar{c}$.
Recall that each such _super-node_ refers to a cluster in
$\mathcal{D}^{(i-1)}_{t}$ (or rather in $\mathcal{C}^{(i-1)}_{t}$, since we
are working in the original graph), that was _contracted_ at the end of the
$(i-1)^{th}$ epoch (Fig. 2), and thus has radius $r^{(i-1)}$. The grey circles
in Fig. 2 correspond to such _super-nodes_ , each of which have weighted-
stretch radius $r^{(i-1)}_{t}=r^{(i-1)}$ (this follows from inductive
hypothesis).

To justify that $r^{(i)}_{j}$ satisfies the above recurrence, we have to show
that the two properties in Definition 4.4 hold for the clustering
$\mathcal{C}^{(i)}_{j}$. The fact that Property (A) holds, should be clear
from Fig. 2. Specifically, the radius of the cluster $\mathcal{C}^{(i)}_{j}$
is at most one greater than the the sum of the radius of
$\mathcal{C}^{(i)}_{j-1}$ and _twice_ the radius of $\mathcal{C}^{(i-1)}$.

In order to show that Property (B) holds, we consider an edge
$e=(x,y)\in\mathsf{E}^{(i)}_{j}$ such that $x\in
c^{\prime}\in\mathcal{C}^{(i)}$, and $y\not\in c^{\prime}$. We can use an
argument similar to the one in Theorem 4.8 (Fig. 2 illustrates the analog of
the first case in the proof of Theorem 4.8). We omit the details to avoid
repetition. ∎

######  Corollary 5.9.

For any $i\in[l]$, we have $r^{(i)}\leq\frac{(2t+1)^{i}-1}{2}$.

###### Proof.

We solve the recurrence from Lemma 5.8 by noticing the base case $r^{(0)}=0$,
and proceeding with induction.

$\displaystyle r^{(i)}=r^{(i)}_{t}$ $\displaystyle\leq
r^{(i)}_{t-1}+2r^{(i-1)}+1$ $\displaystyle\leq
r^{(i)}_{t-2}+\left(2r^{(i-1)}+1\right)$ $\displaystyle\implies r^{(i)}$
$\displaystyle\leq
r^{(i)}_{0}+t\left(2r^{(i-1)}+1\right)=r^{(i-1)}+t\left(2r^{(i-1)}+1\right)$
$\displaystyle=(2t+1)\cdot r^{(i-1)}+t$
$\displaystyle=(2t+1)\cdot\frac{(2t+1)^{i-1}-1}{2}+t=\frac{(2t+1)^{i}-1}{2}$

∎

######  Corollary 5.10.

The final clustering $\mathcal{C}^{(l)}$ has weighted-stretch radius
$\frac{k^{s}-1}{2}$ w.r.t. $\mathsf{E}^{(l)}$, where
$s=\frac{\log(2t+1)}{\log(t+1)}$

###### Proof.

Substituting the value of $l=\frac{\log k}{\log(t+1)}$, we see that
$r^{(l)}=(2t+1)^{l}=(2t+1)^{\frac{\log k}{\log(t+1)}}=2^{\frac{\log
k\log(2t+1)}{\log(t+1)}}=k^{\frac{\log(2t+1)}{\log(t+1)}}$. ∎

Since Definition 4.4 only requires an upper bound on the radius, the above
Corollary 5.10 implies that any intermediate clustering
$\mathcal{C}^{(i)}_{j}$ also has weighted-stretch radius $\frac{k^{s}-1}{2}$.

######  Theorem 5.11.

For any edges $e=\\{u,v\\}$ of weight $w_{e}$ removed in Phase 1, there exists
a path $\mathcal{P}_{e}\in E_{S}$ of total weight at most $2k^{s}\cdot w_{e}$,
between $u$ and $v$, where $s=\frac{\log(2t+1)}{\log(t+1)}$.

###### Proof.

The proof proceeds similarly to that of Theorem 4.10. Edges are discarded in
Step B3, Step B4, Step B6, or Step C.

###### Case $e(v,u)$ was removed in Step B3, Step B4, or Step C.

While these removals are slightly different, they all share a common
structure, which is illustrated in Fig. 3. Specifically, when removing an edge
$e=(v,u)\in E^{(0)}$, the algorithm considers
$c_{v},c_{u}\in\mathcal{C}^{(i)}$ such that $v\in c_{v},u\in c_{u}$, and it
adds edge $e^{\prime}=(v^{\prime},u^{\prime})\in\mathsf{E}(c_{v},c_{u})$ to
the spanner $E_{S}$, before discarding all the edges in
$\mathsf{E}(c_{v},c_{u})$ (including $e$). Since $e^{\prime}$ is always chosen
to be the lowest weight edge, we have $w_{e^{\prime}}\leq w_{e}$. We also
define $\mathcal{F}_{v},\mathcal{F}_{u}$ to be the centers of the
$c_{v},c_{u}$ respectively. Assuming that $c_{v}$ and $c_{u}$ have _weighted-
stretch radius_ $r_{1},r_{2}$ respectively (see Fig. 3), we know that there is
a path
$\mathcal{F}_{v}{\color[rgb]{0.83,0.67,0.00}\definecolor[named]{pgfstrokecolor}{rgb}{0.83,0.67,0.00}\raisebox{2.15277pt}{
\leavevmode\hbox to15.09pt{\vbox to0.86pt{\pgfpicture\makeatletter\hbox{\hskip
0.43056pt\lower-0.43056pt\hbox to0.0pt{\pgfsys@beginscope\pgfsys@invoke{
}\definecolor[named]{pgfstrokecolor}{rgb}{0.83,0.67,0.00}\pgfsys@color@rgb@stroke{0.83}{0.67}{0.00}\pgfsys@invoke{
}\pgfsys@color@rgb@fill{0.83}{0.67}{0.00}\pgfsys@invoke{
}\pgfsys@setlinewidth{0.4pt}\pgfsys@invoke{ }\nullfont\hbox
to0.0pt{\pgfsys@beginscope\pgfsys@invoke{ }{}{{}}{}
{}{}\pgfsys@beginscope\pgfsys@invoke{
}\pgfsys@setlinewidth{0.86111pt}\pgfsys@invoke{
}{}{}{}{}{{}}\pgfsys@moveto{0.0pt}{0.0pt}\pgfsys@lineto{13.47818pt}{0.0pt}\pgfsys@stroke\pgfsys@invoke{
}{{}{{}}{}{}{{}}{{{}}{{{}}{\pgfsys@beginscope\pgfsys@invoke{
}\pgfsys@transformcm{1.0}{0.0}{0.0}{1.0}{13.47818pt}{0.0pt}\pgfsys@invoke{
}\pgfsys@invoke{ \lxSVG@closescope }\pgfsys@invoke{\lxSVG@closescope
}\pgfsys@endscope}}{{}}}} \pgfsys@invoke{\lxSVG@closescope }\pgfsys@endscope
\pgfsys@invoke{\lxSVG@closescope
}\pgfsys@endscope{}{}{}\hss}\pgfsys@discardpath\pgfsys@invoke{\lxSVG@closescope
}\pgfsys@endscope\hss}}\lxSVG@closescope\endpgfpicture}}}}v^{\prime}{\color[rgb]{0.83,0.67,0.00}\definecolor[named]{pgfstrokecolor}{rgb}{0.83,0.67,0.00}\raisebox{2.15277pt}{
\leavevmode\hbox to15.09pt{\vbox to0.86pt{\pgfpicture\makeatletter\hbox{\hskip
0.43056pt\lower-0.43056pt\hbox to0.0pt{\pgfsys@beginscope\pgfsys@invoke{
}\definecolor[named]{pgfstrokecolor}{rgb}{0.83,0.67,0.00}\pgfsys@color@rgb@stroke{0.83}{0.67}{0.00}\pgfsys@invoke{
}\pgfsys@color@rgb@fill{0.83}{0.67}{0.00}\pgfsys@invoke{
}\pgfsys@setlinewidth{0.4pt}\pgfsys@invoke{ }\nullfont\hbox
to0.0pt{\pgfsys@beginscope\pgfsys@invoke{ }{}{{}}{}
{}{}\pgfsys@beginscope\pgfsys@invoke{
}\pgfsys@setlinewidth{0.86111pt}\pgfsys@invoke{
}{}{}{}{}{{}}\pgfsys@moveto{0.0pt}{0.0pt}\pgfsys@lineto{13.47818pt}{0.0pt}\pgfsys@stroke\pgfsys@invoke{
}{{}{{}}{}{}{{}}{{{}}{{{}}{\pgfsys@beginscope\pgfsys@invoke{
}\pgfsys@transformcm{1.0}{0.0}{0.0}{1.0}{13.47818pt}{0.0pt}\pgfsys@invoke{
}\pgfsys@invoke{ \lxSVG@closescope }\pgfsys@invoke{\lxSVG@closescope
}\pgfsys@endscope}}{{}}}} \pgfsys@invoke{\lxSVG@closescope }\pgfsys@endscope
\pgfsys@invoke{\lxSVG@closescope
}\pgfsys@endscope{}{}{}\hss}\pgfsys@discardpath\pgfsys@invoke{\lxSVG@closescope
}\pgfsys@endscope\hss}}\lxSVG@closescope\endpgfpicture}}}}u^{\prime}{\color[rgb]{0.83,0.67,0.00}\definecolor[named]{pgfstrokecolor}{rgb}{0.83,0.67,0.00}\raisebox{2.15277pt}{
\leavevmode\hbox to15.09pt{\vbox to0.86pt{\pgfpicture\makeatletter\hbox{\hskip
0.43056pt\lower-0.43056pt\hbox to0.0pt{\pgfsys@beginscope\pgfsys@invoke{
}\definecolor[named]{pgfstrokecolor}{rgb}{0.83,0.67,0.00}\pgfsys@color@rgb@stroke{0.83}{0.67}{0.00}\pgfsys@invoke{
}\pgfsys@color@rgb@fill{0.83}{0.67}{0.00}\pgfsys@invoke{
}\pgfsys@setlinewidth{0.4pt}\pgfsys@invoke{ }\nullfont\hbox
to0.0pt{\pgfsys@beginscope\pgfsys@invoke{ }{}{{}}{}
{}{}\pgfsys@beginscope\pgfsys@invoke{
}\pgfsys@setlinewidth{0.86111pt}\pgfsys@invoke{
}{}{}{}{}{{}}\pgfsys@moveto{0.0pt}{0.0pt}\pgfsys@lineto{13.47818pt}{0.0pt}\pgfsys@stroke\pgfsys@invoke{
}{{}{{}}{}{}{{}}{{{}}{{{}}{\pgfsys@beginscope\pgfsys@invoke{
}\pgfsys@transformcm{1.0}{0.0}{0.0}{1.0}{13.47818pt}{0.0pt}\pgfsys@invoke{
}\pgfsys@invoke{ \lxSVG@closescope }\pgfsys@invoke{\lxSVG@closescope
}\pgfsys@endscope}}{{}}}} \pgfsys@invoke{\lxSVG@closescope }\pgfsys@endscope
\pgfsys@invoke{\lxSVG@closescope
}\pgfsys@endscope{}{}{}\hss}\pgfsys@discardpath\pgfsys@invoke{\lxSVG@closescope
}\pgfsys@endscope\hss}}\lxSVG@closescope\endpgfpicture}}}}\mathcal{F}_{u}$ of
weight at most $w_{e^{\prime}}(r_{1}+1+r_{2})$ that use only edges in $E_{S}$.
Similarly, we know that there are paths
$v{\color[rgb]{0.83,0.67,0.00}\definecolor[named]{pgfstrokecolor}{rgb}{0.83,0.67,0.00}\raisebox{2.15277pt}{
\leavevmode\hbox to15.09pt{\vbox to0.86pt{\pgfpicture\makeatletter\hbox{\hskip
0.43056pt\lower-0.43056pt\hbox to0.0pt{\pgfsys@beginscope\pgfsys@invoke{
}\definecolor[named]{pgfstrokecolor}{rgb}{0.83,0.67,0.00}\pgfsys@color@rgb@stroke{0.83}{0.67}{0.00}\pgfsys@invoke{
}\pgfsys@color@rgb@fill{0.83}{0.67}{0.00}\pgfsys@invoke{
}\pgfsys@setlinewidth{0.4pt}\pgfsys@invoke{ }\nullfont\hbox
to0.0pt{\pgfsys@beginscope\pgfsys@invoke{ }{}{{}}{}
{}{}\pgfsys@beginscope\pgfsys@invoke{
}\pgfsys@setlinewidth{0.86111pt}\pgfsys@invoke{
}{}{}{}{}{{}}\pgfsys@moveto{0.0pt}{0.0pt}\pgfsys@lineto{13.47818pt}{0.0pt}\pgfsys@stroke\pgfsys@invoke{
}{{}{{}}{}{}{{}}{{{}}{{{}}{\pgfsys@beginscope\pgfsys@invoke{
}\pgfsys@transformcm{1.0}{0.0}{0.0}{1.0}{13.47818pt}{0.0pt}\pgfsys@invoke{
}\pgfsys@invoke{ \lxSVG@closescope }\pgfsys@invoke{\lxSVG@closescope
}\pgfsys@endscope}}{{}}}} \pgfsys@invoke{\lxSVG@closescope }\pgfsys@endscope
\pgfsys@invoke{\lxSVG@closescope
}\pgfsys@endscope{}{}{}\hss}\pgfsys@discardpath\pgfsys@invoke{\lxSVG@closescope
}\pgfsys@endscope\hss}}\lxSVG@closescope\endpgfpicture}}}}\mathcal{F}_{v}$ and
$\mathcal{F}_{u}{\color[rgb]{0.83,0.67,0.00}\definecolor[named]{pgfstrokecolor}{rgb}{0.83,0.67,0.00}\raisebox{2.15277pt}{
\leavevmode\hbox to15.09pt{\vbox to0.86pt{\pgfpicture\makeatletter\hbox{\hskip
0.43056pt\lower-0.43056pt\hbox to0.0pt{\pgfsys@beginscope\pgfsys@invoke{
}\definecolor[named]{pgfstrokecolor}{rgb}{0.83,0.67,0.00}\pgfsys@color@rgb@stroke{0.83}{0.67}{0.00}\pgfsys@invoke{
}\pgfsys@color@rgb@fill{0.83}{0.67}{0.00}\pgfsys@invoke{
}\pgfsys@setlinewidth{0.4pt}\pgfsys@invoke{ }\nullfont\hbox
to0.0pt{\pgfsys@beginscope\pgfsys@invoke{ }{}{{}}{}
{}{}\pgfsys@beginscope\pgfsys@invoke{
}\pgfsys@setlinewidth{0.86111pt}\pgfsys@invoke{
}{}{}{}{}{{}}\pgfsys@moveto{0.0pt}{0.0pt}\pgfsys@lineto{13.47818pt}{0.0pt}\pgfsys@stroke\pgfsys@invoke{
}{{}{{}}{}{}{{}}{{{}}{{{}}{\pgfsys@beginscope\pgfsys@invoke{
}\pgfsys@transformcm{1.0}{0.0}{0.0}{1.0}{13.47818pt}{0.0pt}\pgfsys@invoke{
}\pgfsys@invoke{ \lxSVG@closescope }\pgfsys@invoke{\lxSVG@closescope
}\pgfsys@endscope}}{{}}}} \pgfsys@invoke{\lxSVG@closescope }\pgfsys@endscope
\pgfsys@invoke{\lxSVG@closescope
}\pgfsys@endscope{}{}{}\hss}\pgfsys@discardpath\pgfsys@invoke{\lxSVG@closescope
}\pgfsys@endscope\hss}}\lxSVG@closescope\endpgfpicture}}}}u$ of total weight
at most $w_{e}(r_{1}+r_{2})$, again using only spanner edges. Fig. 3
illustrates this construction. So, we can conclude that the discarded edge of
weight $w_{e}$ can be replaced by a path of total weight at most
$w_{e}(2r_{1}+2r_{2}+1)$. Since Corollary 5.10 states that
$r_{1},r_{2}\leq\frac{k^{s}-1}{2}$, we conclude that the _stretch_ of edge $e$
is at most $2k^{s}$.

Figure 3: A figure used in the proof of Theorem 5.11.

###### Case $e=(v,u)$ was removed in Step B6 in epoch $i$, iteration $j$.

Let $c\in\mathcal{C}^{(i)}$ be the cluster from which $e$ was removed. This
means that both $v$ and $u$ were absorbed into the same sampled cluster
$c_{e}\in\mathcal{R}_{j}$ with center $\mathcal{F}_{e}$. Since $(v,u)$ was not
added to the spanner at Step B3 while processing the _super-node_ containing
$v$, the edge $e^{\prime}=(v,v^{\prime})$ that was actually added must have
weight $w_{e^{\prime}}\leq w_{e}$ (note that $v^{\prime}\in c_{e}$). Assuming
that the cluster $c_{e}$ has _weighted-stretch radius_ $r$, we can conclude
that there is a path $v\raisebox{2.15277pt}{ \leavevmode\hbox to15.09pt{\vbox
to0.86pt{\pgfpicture\makeatletter\hbox{\hskip 0.43056pt\lower-0.43056pt\hbox
to0.0pt{\pgfsys@beginscope\pgfsys@invoke{
}\definecolor{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@rgb@stroke{0}{0}{0}\pgfsys@invoke{
}\pgfsys@color@rgb@fill{0}{0}{0}\pgfsys@invoke{
}\pgfsys@setlinewidth{0.4pt}\pgfsys@invoke{ }\nullfont\hbox
to0.0pt{\pgfsys@beginscope\pgfsys@invoke{ }{}{{}}{}
{}{}\pgfsys@beginscope\pgfsys@invoke{
}\pgfsys@setlinewidth{0.86111pt}\pgfsys@invoke{
}{}{}{}{}{{}}\pgfsys@moveto{0.0pt}{0.0pt}\pgfsys@lineto{13.47818pt}{0.0pt}\pgfsys@stroke\pgfsys@invoke{
}{{}{{}}{}{}{{}}{{{}}{{{}}{\pgfsys@beginscope\pgfsys@invoke{
}\pgfsys@transformcm{1.0}{0.0}{0.0}{1.0}{13.47818pt}{0.0pt}\pgfsys@invoke{
}\pgfsys@invoke{ \lxSVG@closescope }\pgfsys@invoke{\lxSVG@closescope
}\pgfsys@endscope}}{{}}}} \pgfsys@invoke{\lxSVG@closescope }\pgfsys@endscope
\pgfsys@invoke{\lxSVG@closescope
}\pgfsys@endscope{}{}{}\hss}\pgfsys@discardpath\pgfsys@invoke{\lxSVG@closescope
}\pgfsys<EMAIL_ADDRESS>\leavevmode\hbox to15.09pt{\vbox to0.86pt{\pgfpicture\makeatletter\hbox{\hskip
0.43056pt\lower-0.43056pt\hbox to0.0pt{\pgfsys@beginscope\pgfsys@invoke{
}\definecolor{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@rgb@stroke{0}{0}{0}\pgfsys@invoke{
}\pgfsys@color@rgb@fill{0}{0}{0}\pgfsys@invoke{
}\pgfsys@setlinewidth{0.4pt}\pgfsys@invoke{ }\nullfont\hbox
to0.0pt{\pgfsys@beginscope\pgfsys@invoke{ }{}{{}}{}
{}{}\pgfsys@beginscope\pgfsys@invoke{
}\pgfsys@setlinewidth{0.86111pt}\pgfsys@invoke{
}{}{}{}{}{{}}\pgfsys@moveto{0.0pt}{0.0pt}\pgfsys@lineto{13.47818pt}{0.0pt}\pgfsys@stroke\pgfsys@invoke{
}{{}{{}}{}{}{{}}{{{}}{{{}}{\pgfsys@beginscope\pgfsys@invoke{
}\pgfsys@transformcm{1.0}{0.0}{0.0}{1.0}{13.47818pt}{0.0pt}\pgfsys@invoke{
}\pgfsys@invoke{ \lxSVG@closescope }\pgfsys@invoke{\lxSVG@closescope
}\pgfsys@endscope}}{{}}}} \pgfsys@invoke{\lxSVG@closescope }\pgfsys@endscope
\pgfsys@invoke{\lxSVG@closescope
}\pgfsys@endscope{}{}{}\hss}\pgfsys@discardpath\pgfsys@invoke{\lxSVG@closescope
}\pgfsys@endscope\hss}}\lxSVG@closescope\endpgfpicture}}}\mathcal{F}_{e}$, of
total weight $\leq(1+r)\cdot w_{e}$, only using edges in $E_{S}$. Similarly,
since $(v,u)$ was also not added to $E_{S}$ while processing the super-node
containing $u$, we can conclude that there is a path $u\raisebox{2.15277pt}{
\leavevmode\hbox to15.09pt{\vbox to0.86pt{\pgfpicture\makeatletter\hbox{\hskip
0.43056pt\lower-0.43056pt\hbox to0.0pt{\pgfsys@beginscope\pgfsys@invoke{
}\definecolor{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@rgb@stroke{0}{0}{0}\pgfsys@invoke{
}\pgfsys@color@rgb@fill{0}{0}{0}\pgfsys@invoke{
}\pgfsys@setlinewidth{0.4pt}\pgfsys@invoke{ }\nullfont\hbox
to0.0pt{\pgfsys@beginscope\pgfsys@invoke{ }{}{{}}{}
{}{}\pgfsys@beginscope\pgfsys@invoke{
}\pgfsys@setlinewidth{0.86111pt}\pgfsys@invoke{
}{}{}{}{}{{}}\pgfsys@moveto{0.0pt}{0.0pt}\pgfsys@lineto{13.47818pt}{0.0pt}\pgfsys@stroke\pgfsys@invoke{
}{{}{{}}{}{}{{}}{{{}}{{{}}{\pgfsys@beginscope\pgfsys@invoke{
}\pgfsys@transformcm{1.0}{0.0}{0.0}{1.0}{13.47818pt}{0.0pt}\pgfsys@invoke{
}\pgfsys@invoke{ \lxSVG@closescope }\pgfsys@invoke{\lxSVG@closescope
}\pgfsys@endscope}}{{}}}} \pgfsys@invoke{\lxSVG@closescope }\pgfsys@endscope
\pgfsys@invoke{\lxSVG@closescope
}\pgfsys@endscope{}{}{}\hss}\pgfsys@discardpath\pgfsys@invoke{\lxSVG@closescope
}\pgfsys<EMAIL_ADDRESS>\leavevmode\hbox to15.09pt{\vbox to0.86pt{\pgfpicture\makeatletter\hbox{\hskip
0.43056pt\lower-0.43056pt\hbox to0.0pt{\pgfsys@beginscope\pgfsys@invoke{
}\definecolor{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@rgb@stroke{0}{0}{0}\pgfsys@invoke{
}\pgfsys@color@rgb@fill{0}{0}{0}\pgfsys@invoke{
}\pgfsys@setlinewidth{0.4pt}\pgfsys@invoke{ }\nullfont\hbox
to0.0pt{\pgfsys@beginscope\pgfsys@invoke{ }{}{{}}{}
{}{}\pgfsys@beginscope\pgfsys@invoke{
}\pgfsys@setlinewidth{0.86111pt}\pgfsys@invoke{
}{}{}{}{}{{}}\pgfsys@moveto{0.0pt}{0.0pt}\pgfsys@lineto{13.47818pt}{0.0pt}\pgfsys@stroke\pgfsys@invoke{
}{{}{{}}{}{}{{}}{{{}}{{{}}{\pgfsys@beginscope\pgfsys@invoke{
}\pgfsys@transformcm{1.0}{0.0}{0.0}{1.0}{13.47818pt}{0.0pt}\pgfsys@invoke{
}\pgfsys@invoke{ \lxSVG@closescope }\pgfsys@invoke{\lxSVG@closescope
}\pgfsys@endscope}}{{}}}} \pgfsys@invoke{\lxSVG@closescope }\pgfsys@endscope
\pgfsys@invoke{\lxSVG@closescope
}\pgfsys@endscope{}{}{}\hss}\pgfsys@discardpath\pgfsys@invoke{\lxSVG@closescope
}\pgfsys@endscope\hss}}\lxSVG@closescope\endpgfpicture}}}\mathcal{F}_{e}$, of
total weight $\leq(1+r)\cdot w_{e}$, only using edges in $E_{S}$.
Concatenating these two paths, we see that $e$ has stretch at most $(2r+2)\leq
k^{s}$. ∎

Finally, we can use a very similar argument to the stretch analysis in Lemma
4.11 for edges removed in Phase 2. It follows that the overall stretch of our
spanner algorithm is $O(k^{s})$.

###  5.4 General Size Analysis

We now upper-bound the size of a spanner constructed by the algorithm from
this section. The analysis presented here is in many similar to the one given
in Section 4.2.2. The following claim is similar to Lemma 4.12.

######  Lemma 5.12.

At the end of epoch $i$, the number of super-nodes in the graph $G^{(i)}$
(which is the same as the number of clusters $\mathcal{D}^{(i)}_{t}$), is
$O\left(n^{1-\frac{(t+1)^{i}-1}{k}}+\log{n}\right)$ in expectation.

###### Proof.

A cluster $c\in\mathcal{D}^{(i-1)}_{t}$ belongs to $\mathcal{D}^{(i)}_{t}$
only if $c$ was sampled to $\mathcal{R}^{(i)}_{j}$ in Step B1 for each $1\leq
j\leq t$. This happens with probability
$\prod\limits_{j=1}^{t}n^{-\frac{(t+1)^{i-1}}{k}}=n^{-t\cdot\frac{(t+1)^{i-1}}{k}}$.
So, the probability that a specific _vertex_ $v\in V^{(0)}$ survives in
$V^{(i)}$ is:

$\Pr\left[v\in
V^{(i)}\right]=\prod\limits_{i^{\prime}=1}^{i}n^{-t\cdot\frac{(t+1)^{(i^{\prime}-1)}}{k}}=n^{-\frac{(t+1)^{i}-1}{k}}\implies\mathbb{E}\left[|V^{(i)}|\right]=n^{1-\frac{(t+1)^{i}-1}{k}}$

∎

######  Corollary 5.13.

The expected number of super-nodes in the final contracted graph $G^{(l)}$ is
$\mathcal{O}\left(n^{1/k}\right)$.

######  Lemma 5.14.

During Phase 1, in expectation there are $O\left(n^{1+1/k}\cdot(l+t)\right)$
edges added to $E_{S}$.

###### Proof.

We first analyze the contribution of Step A and then the contribution of Step
B to the size of spanner across all the epochs.

###### Analysis of Step A.

Let $n_{i}$ be the number of super-nodes at the beginning of epoch $i$. Then,
by following [BS07] analysis, this step adds $O\left(n_{i}^{1+1/k}\cdot
t\right)$ edges to the spanner. So, by Lemma 5.12 we have that across all the
epochs this step adds the following number of edges to the spanner

$\displaystyle\sum_{i=1}^{l}O\left(n_{i}^{1+1/k}\cdot t\right)$
$\displaystyle=\sum_{i=1}^{l}O\left(n^{(1-\frac{(t+1)^{i-1}-1}{k})(1+1/k)}\cdot
t\right)$ $\displaystyle\in O\left(n^{1+1/k}\cdot
t\right)\sum_{i=1}^{l}n^{-\frac{(t+1)^{i-1}-1}{k}}$
$\displaystyle=O\left(n^{1+1/k}\cdot t\right).$

###### Analysis of Step B.

Fix an epoch $i$. Observe that by letting $t=1$, then this step corresponds to
the algorithm given in Section 4.1. Hence, the size analysis of this case will
be similar to that in Theorem 4.13. We now discuss the differences.

Notice that the proof of Theorem 4.13 is parameterized by $p$. In our case,
$p=n^{-\frac{(t+1)^{i-1}}{k}}$. Following the same analysis as in Theorem
4.13, a cluster $c$ considered at iteration $j$ of epoch $i$ in expectation
adds $O(1/p)$ edges to $E_{S}$. Observe that $p$ is the same throughout the
entire epoch. We now sum contributions of the clusters across all iterations.
By applying Lemma 5.12 and the fact that a cluster proceeds from iteration $x$
to iteration $x+1$ with probability $p$, we derive

$O(1/p)\cdot\sum_{j=1}^{t}O\left(n^{1-\frac{(t+1)^{i-1}-1}{k}}\right)\cdot
p^{j-1}\in O(1/p)\cdot
O\left(n^{1-\frac{(t+1)^{i-1}-1}{k}}\right)=O\left(n^{1+1/k}\right).$

Since there are $l$ epochs, the claim for this step follows. ∎

Finally, we analyze the number of edges added in the second phase to conclude
the size argument. Recall that $l=\frac{\log k}{\log(t+1)}$. Re-phrasing
Corollary 5.13 in the terms defined in Section 5.2, we see that the expected
number of clusters in the final $\mathcal{C}^{(l)}$ is:

$|\mathcal{C}^{(l)}|=O\left(n^{1-\frac{(t+1)^{l}-1}{k}}\right)=O\left(n^{1-\frac{k-1}{k}}\right)=O\left(n^{1/k}\right)$

Hence, the number of edges added in this phase is clearly upper-bound by
$O(n^{1+1/k})$. To conclude, we get the following.

######  Theorem 5.15.

Given a weighted graph $G$ and a parameter $t$, there is an algorithm that
takes $O(\frac{t\log k}{\log(t+1)})$ iterations and outputs a spanner of size
$O(n^{1+1/k}\cdot(t+\log k))$ in expectation, and stretch $O(k^{s})$, where
$s=\frac{\log(2t+1)}{\log(t+1)}$.

##  6 Implementation in $\mathsf{MPC}$ and PRAM

The implementation of the algorithms described is straightforward when memory
per machine is $\Theta(n)$. In this case, each node along with all of its
incident edges can be assigned to one machine. We can maintain a label at each
edge to determine whether it is discarded or added to the spanner, and a label
for each node corresponding to the largest level cluster it belongs to. Nodes
can maintain all of these information simply by communicating with their
neighbors in each round, which is straightforward when memory per machine is
$\Theta(n)$. Maintaining these labels and performing contractions and merges
is somewhat more complicated in the low memory regime, since edges incident to
a node may not fit into one machine. Hence, the low memory regime is our main
focus for the rest of this section.

###### Input Configuration.

We will create and maintain the following configuration of the input
throughout the algorithm: Given a graph $G=(V,E)$, the goal is to store all
the edges incident to each node $v$ in a contiguous group of machines (based
on machine ID), which we denote by $M(v)$. We also denote a designated machine
in the set $M(v)$ by the leader, that represents the node. This could for
instance always be the first machine in the set.

Through out the algorithm we will append each edge with certain labels (e.g.,
“corresponding to a cluster”, “corresponding to a supernode”, etc). In order
to create such a setting we can use several subroutines from previous work.
The following subroutines can all be implemented in $O(1/\gamma)$ rounds when
memory per machine is $O(n^{\gamma})$, for any constant $\gamma>0$.

  * •

Sort ([GSZ11]). Given a set of $N$ comparable items, the goal is to have the
items sorted on the output machines, i.e., the output machine with smaller ID
holds smaller items.

  * •

Find Minimum ($v$) (e.g., [DN19]). Finds the minimum value over the set of
machines $M(v)$, i.e., machines containing edges incident to node $v\in V$.

  * •

Broadcast ($b,v$) (e.g., [DN19]). Broadcasts a message $b$ to all machine in
$M(v)$.

Most of these subroutines can be implemented using an (implicit) aggregation
tree, with branching factor $n^{\gamma}$, where the machines in $M(v)$ are the
leaves. In each round, the aggregate function is computed over a set of
$n^{\gamma}$ nodes in this tree and moved up to the higher levels (e.g. in
case of find minimum), or moved down the tree (in case of broadcast). For more
details on these standard technique, see [GSZ11].

First, using sorting and indexing subroutines we can create the configuration
described above. This can be done by sorting the edges of form $(u,v)$ based
on ID of the first node in the tuple. We also assume w.l.o.g that pairs
$(u,v)$ and $(v,u)$ are present in the input for each undirected edge. Any
time one of these tuples, say $(u,v)$ changes (or adds) a label, this label is
also added to the machine containing $(v,u)$ by using the sort subroutine
again but based on the smallest ID of the two endpoints. In this case the
tuples $(u,v)$ and $(v,u)$ will be place in the same machine (or machines next
to each other) and the new labels can be updated for both tuples. After this
process, we will sort the input again based on the ordered pairs to return to
the initial configuration.

In addition to the standard subroutines described, for implementing our
algorithm in $\mathsf{MPC}$ we also need the following subroutines:

  * •

Clustering: Each node maintains a label corresponding to the highest level
cluster it belongs to.

  * •

Merge: Merging two clusters into one cluster.

  * •

Contraction: Creating a supergraph by contracting a set of clusters to form
supernodes and the corresponding superedges.

######  Lemma 6.1.

Subroutines clustering, merge and contraction (as described above) can be
implemented in $O(1/\gamma)$ rounds of $\mathsf{MPC}$, when memory per machine
is $O(n^{\gamma})$, for any constant $\gamma>0$.

###### Proof.

Each of these operations can be performed by creating and updating labels for
each edge. In particular, we will maintain tuples of form
$((u,v),\mathcal{I}_{u},\mathcal{I}_{v},i)$, where $i$ represents the highest
level cluster center, and $\mathcal{I}_{u}$ represents the ID of the cluster
center node $u$ belongs to.

Clustering. Whenever the level of a cluster increments, we first update the
level label of the cluster center. Then we can sort all the tuples by the
cluster center ID of the first endpoint and increment the corresponding label.
We can then repeat the process again the second endpoint.

Merge. The merge operation can be performed similarly by relabeling the ID of
the center for each edge that is merging into the another cluster.

Contraction. For this operation, we again use the sorting subroutine to group
all the nodes in a cluster to a contiguous set of machines that are simulating
a supernode. We can then relabel the edge tuples so that $(u,v)$ is replaced
with $(\hat{u},\hat{v})$, where $\hat{u}$ and $\hat{v}$ are IDs of the cluster
centers that were contracted. Hence each edge is replaced with a new tuple
corresponding to the two supernodes that its endpoints belong to.

At the end of each of these operations, we will sort the tuples again based on
(possibly new) edge tuples to get back to the initial configuration, where all
edges incident to a node (or supernode) are in adjacent. All of these steps
can also be done in $O(1/\gamma)$ rounds when memory per machine is
$O(n^{\gamma})$. ∎

We will now argue how using these subroutines, we can implement the algorithm
of Section 5, and implementation of the algorithms of Section 4 and Section 3
will immediately follow.

See 1.1

###### Proof.

We now describe how operation needed for a single iteration of the our
algorithm can be implemented in $\mathsf{MPC}$ with $O(n^{\gamma})$ memory per
machine using the subroutines described. Sampling is straightforward: each
cluster center will be subsampled with probability $n^{\frac{(t+1)^{i-1}}{k}}$
(at iteration $t$ of the $i$-th epoch), and using the Clustering subroutine,
as described in Lemma 6.1, all other nodes in the subsampled cluster will
update their labels.

Recall that we always maintain the configuration in which the edges of each
node are grouped in a contiguous set of machines at any time for the quotient
graph of each epoch. This allows us to discard edges or add edges to the
spanner in a straightforward way by maintaining another label for each edge.

In Step B3 and Step B4, we use the subroutine Find Min($v$) to find the
minimum weight edge among a subset of nodes incident to a given node $v$.

After each iteration we will perform a Merge operation, and at the end of each
epoch we will perform a Contraction operation. All of these operation can be
performed in $O(1/\gamma)$ rounds.

Finally, for the overall number of rounds, recall that the algorithm proceeds
in $\ell=\frac{\log k}{\log(t+1)}$ epoches. For each epoch we run $t$
iterations of a set of operations all of which takes $O(1/\gamma)$ rounds
based on the subroutines explained. Finally, at an additional $O(\log n)$
overhead on the overall memory, we can repeat the algorithm in parallel
$O(\log n)$ rounds to turn the expected size guarantee into a high probability
bound using a simple Chernoff-bounds arguments. Hence, overall the algorithm
takes $O(\frac{1}{\gamma}\cdot\frac{t\log k}{\log(t+1)})$ rounds. ∎

###### PRAM

Using similar primitives as [BS07] we can obtain low depth CRCW PRAM
algorithms. Specifically, we can use the primitives of _hashing_ ,
_semisorting_ , and _generalized find min_ that were utilized in [BS07].
Additionally, we need a new primitive which has to merge two sets of vertices
(clusters). The _merge_ primitive can be implemented like a union find data
structure, where each set has a “leader” node, and all other nodes point to
the leader. The merge operation can be performed in $O(1)$ steps, by
identifying and changing all the leader pointers in parallel. The PRAM depth
is the same as the MPC round complexity, with an additional multiplicative
$\log^{*}n$ factor that arises from the hashing, semisorting and find min
primitives. We note that $O(k)$ depth PRAM algorithms for spanners were also
studied in [MPVX15], in addition to [BS07].

##  7 Application for Approximate Shortest Paths

While we focused on constructing spanners in a setting where each machine has
a memory of sublinear size, the same algorithm also works for the less
restrictive setting of $\mathsf{MPC}$ with linear memory, e.g., we can
consider each machine as subdivided into multiple machines of less memory. The
advantage in this model is that if we build a spanner of near-linear size, we
can allow to store it on one machine which leads to a $poly(\log
n)$-approximation for the all pairs shortest paths (APSP) problem. We next
elaborate on it.

As a reminder, our algorithm builds a spanner of size $O(n^{1+1/k}\cdot(t+\log
k))$ in $poly(\log k)$ rounds. If we focus on $t=O(\log{\log{n}})$ and plug in
$k=\log{n}$, we get a construction of spanner of near-linear size and
$poly(\log n)$ stretch in $poly(\log{\log n})$ time. Since the spanner has
size $O(n\log{\log n})$, if we allow each machine to have $\tilde{O}(n)$
memory, we can just send the whole spanner to one machine. As the spanner has
paths with stretch $poly(\log n)$ between all pairs of vertices, this gives
$poly(\log n)$ approximation for APSP, summarized as follows.

See 1.4

As two special cases, this gives $O(\log^{\log 3}n)$-approximation in
$O(\log\log n)$ time, and $O(\log^{1+o(1)}n)$-approximation in
$O(\log^{2}\log{n})$ time.

##  8 Applications in Congested Clique

We next discuss applications for the closely related distributed Congested
Clique model. In this model there are $n$ nodes that communicate by sending
$\Theta(\log n)$ bit messages in synchronous rounds. It was shown in [BDH18]
that a less restricted variant of MPC, called semi-MPC is equivalent to the
Congested Clique model. This is a variant of MPC where there are $n$ machines
with $\Theta(n)$ memory. Compared to the more standard MPC model, in this
model the total memory is $O(n^{2})$ and not $\tilde{O}(m)$. The spanner
algorithm also works in this less restricted variant, with the following
difference. The basic spanner algorithm gives a guarantee on the size of the
spanner in expectation. To get this guarantee w.h.p, we can run it $O(\log n)$
times in parallel in the MPC model which adds logarithmic factor to the total
size of memory. However, in the Congested Clique model, this approach is
problematic because it would multiply the complexity by an $O(\log{n})$
factor, which is too expensive as we aim for a $poly(\log{\log{n}})$
complexity. To avoid this, we next sketch how to do parallel repetitions in
the Congested Clique efficiently, which results in a similar spanner
construction for the Congested Clique model.

######  Theorem 8.1.

There is an algorithm that runs in $O(\frac{t\log k}{\log(t+1)})$ rounds of
Congested Clique and w.h.p. outputs a spanner of size $O(n^{1+1/k}\cdot(t+\log
k))$, and stretch $O(k^{s})$, where $s=\frac{\log(2t+1)}{\log(t+1)}$.

###### Proof.

As discussed above, we can run one run of the spanner algorithm in the semi-
MPC model, and hence also in the Congested Clique model using the simulation
described in [BDH18]. This gives $O(k^{s})$-spanner of expected size
$O(n^{1+1/k}\cdot(t+\log k))$ in $O(\frac{t\log k}{\log(t+1)})$ rounds. We
next explain how to run $O(\log n)$ runs of the algorithm in parallel, which
would enable us to build a spanner of size $O(n^{1+1/k}\cdot(t+\log k))$
w.h.p.

The size analysis of the spanner is based on the following randomized process.
In each iteration444This also refers to iterations where we apply Baswana-Sen,
as it is based on the same randomized process. of the algorithm, we have a set
of super-nodes $C$, and we sample from them a set of clusters $R$ such that
each vertex in $C$ is added to $R$ with probability $p$. The size analysis is
based on the following:

  1. 1.

The expected number of clusters is $O(|C|p)$.

  2. 2.

The expected number of edges added to the spanner in this iteration is
$O(|C|/p)$.

A standard application of Chernoff bound shows that 1 actually holds w.h.p (as
long as the number of clusters is $\Omega(\log{n})$, but when it is smaller it
is easy to show that the total number of edges added to the spanner is small
enough). Also, from Markov’s inequality, it follows that 2 happens with
constant probability. It follows that if we simulate this randomized process
$O(\log{n})$ times in parallel, we get w.h.p a run where both events hold,
which implies that we get the bound on the number of edges w.h.p. Hence, we
just need to simulate this part $O(\log{n})$ times (in each iteration), to
guarantee a total of $O(n^{1+1/k}\cdot(t+\log k))$ edges w.h.p.

This is done as follows. In the algorithm, first, each super-node from $C$ is
added to $R$ with probability $p$. The sampling is a completely local process
done by each super-node separately. Hence, each super-node can just simulate
it $O(\log{n})$ times. Then, we would like each super-node to let all other
nodes learn the outcome of the sampling process. This can be done by just
sending a single $O(\log{n})$ bit message from each super-node $v$ to all
nodes, where the $i$’th bit of the message indicates if $v$ is added to $R$ in
the $i$’th run of the algorithm. This takes only one round. Now, based on this
information, each super-node in $C$ knows exactly which edges adjacent to it
are taken to the spanner in each run of the algorithm. To conclude, we choose
$O(\log{n})$ nodes that would be responsible for the $O(\log{n})$ different
runs. Node $v_{i}$ would collect from all super-nodes the number of edges
adjacent to them added to the spanner in run $i$. In addition, all nodes know
how many vertices were added to $R$ in each one of the runs. Finally, we
choose a run where the number of nodes in $R$ is $O(|C|p)$, and the number of
edges added to the spanner is $O(|C|/p)$, which exists w.h.p as explained
above. We only added a constant number of rounds for each iteration, hence the
time complexity matches the complexity of the MPC algorithm. ∎

###### Approximate Shortest Paths.

The spanner algorithm results in a $poly(\log{n})$-approximation for weighted
APSP in $poly(\log{\log{n}})$ rounds in the Congested Clique model, as
follows. Choosing $k=\log{n}$ and $t=O(\log{\log{n}})$, results in a spanner
of size $O(n\log{\log{n}})$. We can let all vertices learn the whole spanner
in $O(\log{\log{n}})$ rounds using Lenzen’s routing [Len13], which results in
the following corollary.

See 1.5

## Acknowledgements

We thank Merav Parter, Michael Dinitz and Aditya Krishnan for fruitful
discussions.

AS. Biswas is supported by MIT-IBM Watson AI Lab and research collaboration
agreement No. W1771646, NSF awards CCF-1733808, IIS-1741137, Big George
Ventures Fund Fellowship. S. Mitrović is supported by the Swiss NSF grant No.
P400P2_191122/1 and<EMAIL_ADDRESS>Nazari is supported by NSF award
CCF-190911.

## References

  * [ABB+19] Sepehr Assadi, MohammadHossein Bateni, Aaron Bernstein, Vahab S. Mirrokni, and Cliff Stein.  Coresets meet EDCS: algorithms for matching and vertex cover on massive graphs.  In Timothy M. Chan, editor, Proc. Symposium on Discrete Algorithms (SODA), pages 1616–1635, 2019.
  * [ACK19] Sepehr Assadi, Yu Chen, and Sanjeev Khanna.  Sublinear Algorithms for $(\Delta+1)$ Vertex Coloring.  In Proceedings 30th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), 2019.
  * [AG15] Kook Jin Ahn and Sudipto Guha.  Access to data and number of iterations: Dual primal algorithms for maximum matching under resource constraints.  In SPAA, pages 202–211, 2015.
  * [AGM12] K. J. Ahn, S. Guha, and A. McGregor.  Analyzing graph structure via linear measurements.  In Proceedings of the 23rd Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), pages 459–467, 2012.
  * [ANOY14] Alexandr Andoni, Aleksandar Nikolov, Krzysztof Onak, and Grigory Yaroslavtsev.  Parallel algorithms for geometric graph problems.  In Proc. Symposium on Theory of Computation (STOC), pages 574–583, 2014.
  * [Ass17] Sepehr Assadi.  Simple round compression for parallel vertex cover.  arXiv preprint arXiv:1709.04599, 2017.
  * [ASS+18] Alexandr Andoni, Clifford Stein, Zhao Song, Zhengyu Wang, and Peilin Zhong.  Parallel graph connectivity in log diameter rounds.  In Proc. Foundations of Computer Science (FOCS), pages 674–685, 2018.
  * [ASW19] Sepehr Assadi, Xiaorui Sun, and Omri Weinstein.  Massively parallel algorithms for finding well-connected components in sparse graphs.  In Peter Robinson and Faith Ellen, editors, Proc. Principles of Distributed Computing (PODC), pages 461–470, 2019.
  * [ASZ19] Alexandr Andoni, Clifford Stein, and Peilin Zhong.  Log diameter rounds algorithms for 2-vertex and 2-edge connectivity.  In Christel Baier, Ioannis Chatzigiannakis, Paola Flocchini, and Stefano Leonardi, editors, Proc. ICALP, volume 132, pages 14:1–14:16, 2019\.
  * [ASZ20] Alexandr Andoni, Clifford Stein, and Peilin Zhong.  Parallel approximate undirected shortest paths via low hop emulators.  In Proc. Symposium on Theory of Computation (STOC), 2020.
  * [BBD+19] Soheil Behnezhad, Sebastian Brandt, Mahsa Derakhshan, Manuela Fischer, MohammadTaghi Hajiaghayi, Richard M. Karp, and Jara Uitto.  Massively parallel computation of matching and MIS in sparse graphs.  In Peter Robinson and Faith Ellen, editors, Proc. Principles of Distributed Computing (PODC), pages 481–490, 2019.
  * [BDE+19] Soheil Behnezhad, Laxman Dhulipala, Hossein Esfandiari, Jakub Lacki, and Vahab S. Mirrokni.  Near-optimal massively parallel graph connectivity.  In David Zuckerman, editor, Proc. Foundations of Computer Science (FOCS), pages 1615–1636, 2019.
  * [BDH18] Soheil Behnezhad, Mahsa Derakhshan, and MohammadTaghi Hajiaghayi.  Brief announcement: Semi-mapreduce meets congested clique.  CoRR, abs/1802.10297, 2018.
  * [BEG+18] Mahdi Boroujeni, Soheil Ehsani, Mohammad Ghodsi, MohammadTaghi HajiAghayi, and Saeed Seddighin.  Approximating edit distance in truly subquadratic time: quantum and MapReduce.  In Proc. Symposium on Discrete Algorithms (SODA), pages 1170–1189, 2018.
  * [BFU18] Sebastian Brandt, Manuela Fischer, and Jara Uitto.  Breaking the linear-memory barrier in MPC: Fast MIS on trees with $n^{\epsilon}$ memory per machine.  arXiv preprint arXiv:1802.06748, 2018.
  * [BHH19] Soheil Behnezhad, MohammadTaghi Hajiaghayi, and David G. Harris.  Exponentially faster massively parallel maximal matching.  In David Zuckerman, editor, Proc. Foundations of Computer Science (FOCS), pages 1637–1649, 2019.
  * [BKKL17] Ruben Becker, Andreas Karrenbauer, Sebastian Krinninger, and Christoph Lenzen.  Near-Optimal Approximate Shortest Paths and Transshipment in Distributed and Streaming Models.  In Proc. Symposium on DIStributed Computing (DISC), volume 91, pages 7:1–7:16, 2017.
  * [BKS13] Paul Beame, Paraschos Koutris, and Dan Suciu.  Communication steps for parallel query processing.  In Proceedings of the 32Nd ACM SIGMOD-SIGACT-SIGAI Symposium on Principles of Database Systems (PODS), pages 273–284, 2013.
  * [BKS14] Paul Beame, Paraschos Koutris, and Dan Suciu.  Skew in parallel query processing.  In Proceedings of the 33rd ACM SIGMOD-SIGACT-SIGART Symposium on Principles of Database Systems (PODS), pages 212–223, 2014.
  * [BLP20] Uri Ben-Levy and Merav Parter.  New ($\alpha$, $\beta$) spanners and hopsets.  In Proceedings of the Fourteenth Annual ACM-SIAM Symposium on Discrete Algorithms, pages 1695–1714. SIAM, 2020.
  * [BS07] Surender Baswana and Sandeep Sen.  A simple and linear time randomized algorithm for computing sparse spanners in weighted graphs.  Random Structures & Algorithms, 30(4):532–563, 2007.
  * [CFG+19] Yi-Jun Chang, Manuela Fischer, Mohsen Ghaffari, Jara Uitto, and Yufan Zheng.  The complexity of ($\Delta$+1) coloring in congested clique, massively parallel computation, and centralized local computation.  In Proc. Principles of Distributed Computing (PODC), pages 471–480, 2019.
  * [CHDKL19] Keren Censor-Hillel, Michal Dory, Janne H Korhonen, and Dean Leitersdorf.  Fast approximate shortest paths in the congested clique.  In Proceedings of the 2019 ACM Symposium on Principles of Distributed Computing (PODC), pages 74–83, 2019.
  * [CLM+18] Artur Czumaj, Jakub Lacki, Aleksander Madry, Slobodan Mitrovic, Krzysztof Onak, and Piotr Sankowski.  Round compression for parallel matching algorithms.  In Proc. Symposium on Theory of Computation (STOC), pages 471–484, 2018.
  * [Coh00] Edith Cohen.  Polylog-time and near-linear work approximation scheme for undirected shortest paths.  Journal of the ACM (JACM), 47(1):132–166, 2000.
  * [DG08] Jeffrey Dean and Sanjay Ghemawat.  Mapreduce: simplified data processing on large clusters.  Communications of the ACM, 51(1):107–113, 2008.
  * [DGPV08] Bilel Derbel, Cyril Gavoille, David Peleg, and Laurent Viennot.  On the locality of distributed sparse spanner construction.  In Proc. Principles of Distributed Computing (PODC), pages 273–282, 2008.
  * [DN19] Michael Dinitz and Yasamin Nazari.  Massively parallel approximate distance sketches.  In Proceedings of International Conference on Principles of Distributed Systems (OPODIS 2019). Schloss Dagstuhl-Leibniz-Zentrum fuer Informatik, 2019.
  * [DP20] Michal Dory and Merav Parter.  Exponentially faster shortest paths in the congested clique.  In PODC, 2020.
  * [FKN21] Arnold Filtser, Michael Kapralov, and Navid Nouri.  Graph spanners by sketching in dynamic streams and the simultaneous communication model.  In Proceedings of the 2021 ACM-SIAM Symposium on Discrete Algorithms (SODA). SIAM, 2021.
  * [FL18] Stephan Friedrichs and Christoph Lenzen.  Parallel metric tree embedding based on an algebraic view on moore-bellman-ford.  Journal of the ACM (JACM), 65(6):43, 2018.
  * [GGK+18] Mohsen Ghaffari, Themis Gouleakis, Christian Konrad, Slobodan Mitrović, and Ronitt Rubinfeld.  Improved massively parallel computation algorithms for mis, matching, and vertex cover.  In Proc. Principles of Distributed Computing (PODC). arXiv:1802.08237, 2018.
  * [GKMS19] Buddhima Gamlath, Sagar Kale, Slobodan Mitrovic, and Ola Svensson.  Weighted matchings via unweighted augmentations.  In Peter Robinson and Faith Ellen, editors, Proc. Principles of Distributed Computing (PODC), pages 491–500. ACM, 2019.
  * [GKU19] Mohsen Ghaffari, Fabian Kuhn, and Jara Uitto.  Conditional hardness results for massively parallel computation from distributed lower bounds.  In Proc. Foundations of Computer Science (FOCS), pages 1650–1663. IEEE Computer Society, 2019.
  * [GLM19] Mohsen Ghaffari, Silvio Lattanzi, and Slobodan Mitrovic.  Improved parallel algorithms for density-based network clustering.  In Kamalika Chaudhuri and Ruslan Salakhutdinov, editors, Proceedings of the International Conference on Machine Learning (ICML), volume 97, pages 2201–2210. PMLR, 2019.
  * [GN20] Mohsen Ghaffari and Krzysztof Nowicki.  Massively Parallel Algorithms for Minimum Cut.  In Proc. Principles of Distributed Computing (PODC), page to appear, 2020.
  * [GNT20] Mohsen Ghaffari, Krzysztof Nowicki, and Mikkel Thorup.  Faster Algorithms for Edge Connectivity via Random 2-Out Contractions.  In Proc. Symposium on Discrete Algorithms (SODA), pages 1260–1279, 2020.
  * [GSZ11] Michael T. Goodrich, Nodari Sitchinava, and Qin Zhang.  Sorting, searching, and simulation in the MapReduce framework.  In Proc. ISAAC, pages 374–383. Springer, 2011.
  * [GU19] Mohsen Ghaffari and Jara Uitto.  Sparsifying distributed algorithms with ramifications in massively parallel computation and centralized local computation.  In Proc. Symposium on Discrete Algorithms (SODA), pages 1636–1653, 2019.
  * [HLL18] Nicholas J. A. Harvey, Christopher Liaw, and Paul Liu.  Greedy and local ratio algorithms in the MapReduce model.  In Proceedings of the 30th on Symposium on Parallelism in Algorithms and Architectures (SPAA), pages 43–52, New York, NY, USA, 2018\. ACM.
  * [HLSS19] MohammadTaghi Hajiaghayi, Silvio Lattanzi, Saeed Seddighin, and Cliff Stein.  Mapreduce meets fine-grained complexity: Mapreduce algorithms for apsp, matrix multiplication, 3-sum, and beyond.  arXiv preprint arXiv:1905.01748, 2019.
  * [HP15] James W Hegeman and Sriram V Pemmaraju.  Lessons from the congested clique applied to MapReduce.  Theoretical Computer Science, 608:268–281, 2015.
  * [IBY+07] Michael Isard, Mihai Budiu, Yuan Yu, Andrew Birrell, and Dennis Fetterly.  Dryad: distributed data-parallel programs from sequential building blocks.  In Proceedings of the 2nd ACM SIGOPS/EuroSys European Conference on Computer Systems 2007, pages 59–72, 2007.
  * [ILMP19] Giuseppe F. Italiano, Silvio Lattanzi, Vahab S. Mirrokni, and Nikos Parotsidis.  Dynamic algorithms for the massively parallel computation model.  In SPAA, pages 49–58, 2019.
  * [IMS17] Sungjin Im, Benjamin Moseley, and Xiaorui Sun.  Efficient massively parallel methods for dynamic programming.  In Proc. Symposium on Theory of Computation (STOC), pages 798–811, 2017.
  * [KSV10] Howard Karloff, Siddharth Suri, and Sergei Vassilvitskii.  A model of computation for MapReduce.  In Proc. Symposium on Discrete Algorithms (SODA), pages 938–948, 2010.
  * [KW14] Michael Kapralov and David Woodruff.  Spanners and sparsifiers in dynamic streams.  In Proceedings of the 2014 ACM symposium on Principles of distributed computing, pages 272–281, 2014.
  * [Len13] Christoph Lenzen.  Optimal deterministic routing and sorting on the congested clique.  In Proceedings of the 2013 ACM symposium on Principles of distributed computing (PODC), pages 42–50, 2013.