On Efficient Distributed Construction of Near Optimal Routing
Schemes∗

arXiv:1602.02293v2 [cs.DC] 20 Nov 2016

Michael Elkin†1 and Ofer Neiman‡1
1

Department of Computer Science, Ben-Gurion University of the Negev, Beer-Sheva, Israel.
Email: {elkinm,neimano}@cs.bgu.ac.il

Abstract
Given a distributed network represented by a weighted undirected graph G = (V, E) on n vertices,
and a parameter k, we devise a distributed algorithm that computes a routing scheme in O(n1/2+1/k +
D) · no(1) rounds, where D is the hop-diameter of the network. Moreover, for odd k, the running time
of our algorithm is O(n1/2+1/(2k) + D) · no(1) . Our running time nearly matches the lower bound of
Ω̃(n1/2 + D) rounds (which holds for any scheme with polynomial stretch). The routing tables are of
size Õ(n1/k ), the labels are of size O(k log2 n), and every packet is routed on a path suffering stretch at
most 4k − 5 + o(1). Our construction nearly matches the state-of-the-art for routing schemes built in a
centralized sequential manner. The previous best algorithms for building routing tables in a distributed
small messages model were by [LP13a, STOC 2013] and [LP15, PODC 2015]. The former has similar
properties but suffers from substantially larger routing tables of size O(n1/2+1/k ), while the latter has
sub-optimal running time of Õ(min{(nD)1/2 · n1/k , n2/3+2/(3k) + D}).

1 Introduction
A routing scheme in a distributed network is a mechanism that allows packets to be delivered from any node
to any other node. The network is represented as a weighted undirected graph, and each node should be able
to forward incoming data by using local information stored at the node, and the (short) packet’s header. The
local routing information is often referred to as a routing table. The routing scheme has two main phases:
in the preprocessing phase, each node is assigned a routing table and a short label. In the routing phase,
each node receiving a packet should make a local decision, based on its own routing table and the packet’s
header (which contains the label of the destination), to which neighbor forward the packet to. The stretch of
a routing scheme is the worst ratio between the length of a path on which a packet is routed, to the shortest
possible path.
Designing efficient routing schemes is a central problem in the area of distributed networking, and
was studied intensively [PU89, ABLP90, Cow01, EGP03, GP03, AGM04, PU89, TZ01, Che13]. The first
general tradeoffs for this problem were given in pioneering works by [PU89, ABLP90]. In a seminal paper
[TZ01], Thorup and Zwick presented the following compact routing scheme: Given a weighted graph G on
∗

A preliminary version [EN16b] of this paper was published in PODC’16.
This research was supported by the ISF grant No. (724/15).
‡
Supported in part by ISF grant No. (523/12) and by BSF grant No. 2015813.
†

1

n vertices and a parameter k ≥ 1, the scheme has routing tables of size Õ(n1/k ),1 labels of size O(k log n)
and stretch 4k − 5. (Assuming that port numbers may be assigned by the routing process, otherwise the
label size increases by a factor of log n.)2 The state-of-the-art is a scheme of [Che13], which is based on
[TZ01], and improves the stretch to 3.68k.
All the results above assume that the preprocessing phase can be computed in a sequential centralized
manner. However, as the problem of designing a compact routing scheme is inherently concerned with a
distributed network, constructing the scheme efficiently in a distributed manner is a very natural direction.
We focus on the standard CONGEST model [Pel00a]. In this model, every vertex initially knows only the
edges touching it, and communication between vertices occurs in synchronous rounds. On every round,
each vertex may send a small message to each of its neighbors. Every message takes a unit time to reach the
neighbor, regardless of the edge weight. The time complexity is measured by the number of rounds it takes
to complete a task (we assume local computation does not cost anything). Often the time depends on n, the
number of vertices, and D, the hop-diameter of the graph. The hop-diameter is the maximum hop-distance
between two vertices, where the hop-distance is the minimal number of edges on a path between the vertices
(regardless of the weights). The hop-diameter is not to be confused with the shortest path diameter S, which
is the maximal number of hops a shortest path uses (assuming shortest paths are unique). We always have
D ≤ S, and typically D is small while S could be as large as Ω(n). We also assume, as common in the
literature [LP13a, Nan14, KP98, GK13, HKN16], that edge weights are integers and at most polynomial in
n (so that they could be sent in a single message).3
A rich research thread concerns with finding efficient distributed (approximation) algorithms for classical graph problems (e.g., minimum spanning tree, minimum cut, shortest paths), in sub-linear time [GKP98,
√
PR00, Elk06a, SHK+ 12, HKN16]. There are several results obtaining running times of the form Õ( n+D),
e.g. for MST, connectivity, minimum cut, approximate shortest path tree, etc. These results are often accompanied by a (nearly) matching lower bounds. The lower bound of [SHK+ 12], based on [PR00, Elk06b],
√
implies that devising a routing scheme with any polynomial stretch, requires Ω̃( n + D) rounds.
The first result on computing a routing scheme in a distributed manner within o(n) rounds (for general
graphs with D = o(n)), was shown by Lenzen and Patt-Shamir [LP13a].4 Their algorithm, given a graph
on n vertices and a parameter k, provides routing tables of size Õ(n1/2+1/k ), labels of size O(log n · log k),
stretch at most O(k log k), and has a nearly optimal running time of Õ(n1/2+1/k + D) rounds. Note that the
√
routing tables are of size Ω( n) for any value of k, which could be prohibitively large (the routing scheme
√
of [TZ01] supports stretch 3 with Õ( n) table size). They also show implications for related problems,
such as approximate diameter, generalized Steiner forest, and distance estimation. In a follow-up paper,
[LP15] showed how to improve the stretch of the above scheme to roughly 3k/2 (for any k divisible by 4).
They also exhibited a different tradeoff, that overcame the issue of large routing tables. They devised an
algorithm that produced routing tables of size Õ(n1/k ), labels of size O(k log2 n) and stretch 4k −3+o(1),5
but the number of rounds increases to Õ(min{(nD)1/2 · n1/k , n2/3+2/(3k) + D}). Note that for moderately
large hop-diameter D ≈ n1/3 , the number of rounds is bounded by only ≈ n2/3 for any value of k. (They
The Õ hides logO(1) n factors.
They also presented stretch 2k − 1, assuming ”handshaking”: allowing the source and destination to communicate before the
routing phase begins, but it is often desirable to avoid handshaking. Henceforth, we discuss only routing schemes that do not allow
handshaking.
3
We shall not consider name-independent routing, in which the label of a vertex is its ID, because [LP13a] showed a strong
lower bound: any such scheme with stretch ρ (even average stretch ρ) must take Ω̃(n/ρ2 ) rounds to compute in this model.
4
We remark that for the class of k-chordal graphs, [NRS12] showed a construction of a routing scheme that could be computed
efficiently in a distributed manner.
5
The paper [LP15] claimed label size O(k log n), but in [LP16] it was communicated to us that the actual size is O(k log2 n).
1

2

2

also show a variant where the number of rounds is Õ(S + n1/k ), but as was mentioned above, S might be
much larger than D.)
In the distance estimation problem (also known as sketching, or distance labeling), we wish to compute
a small sketch for each vertex, so that given any two sketches, one can efficiently compute the (approximate)
distance between the vertices. This problem was introduced in [Pel00b], who provided initial existential
results. In [SDP15], a distributed (randomized) algorithm running in Õ(S · n1/k ) rounds was shown, that
computes sketches of size O(kn1/k log n) with stretch at most 2k−1. While this essentially matches the best
sequential algorithm of [TZ05], the number of rounds could be Ω(n), even when D is small. In [LP13a], a
running time of Õ(n1/2+1/k + D) rounds was presented, at the cost of significantly increasing the stretch to
O(k2 ).6 Izumi and Wattenhofer [IW14] showed a lower bound of n1/2+Ω(1/k) rounds for this problem. In
the Conclusion part of their paper [IW14], Izumi and Wattenhofer posed an open problem:
“An open problem related to our results is to find algorithms whose running time gets close to our lower
bounds.”
Our contribution. We devise a randomized
distributed algorithm running in
√
1/2+1/k
O(k)
Õ(
log
n)
(n
+ D) · min{(log n)
,2
} rounds, that with high probability, computes a compact routing scheme with routing tables of size O(n1/k log2 n), labels of size O(k log2 n), and stretch at most 4k−5+
√
o(1). Moroever, for odd k, the running time of our algorithm is (n1/2+1/(2k) +D)·min{(log n)O(k) , 2Õ( log n) }.
Note that our result nearly matches the construction of [TZ01], up to logarithmic terms in the size and o(1)
additive term in the stretch. This is even though the latter is computed in a sequential centralized manner.
Observe that our running time nearly matches the lower bound of [SHK+ 12], and is substantially better
than that of [LP15] whenever D ≥ nΩ(1) (which achieved similar size-stretch tradeoff). The previous result
obtaining near optimal running time [LP13a], suffers from excessive routing table size.
As a corollary, we show a distance estimation
scheme, that can be computed in a distributed manner
√
1/2+1/k
O(k)
Õ(
log
n)
in (n
+ D) · min{(log
n)
,2
} rounds for even k, and for odd k in (n1/2+1/(2k) + D) ·
√
min{(log n)O(k) , 2Õ( log n) } rounds, providing sketches of size O(n1/k log n) with stretch 2k − 1 + o(1).
Each distance estimation takes only O(k) time. Our result combines the improved running time of [LP13a]
(up to lower order terms), with the near optimal size-stretch tradeoff of [SDP15]. Moreover, our bound for
the running time of distance estimation scheme nearly matches the lower bound n1/2+Ω(1/k) of Izumi and
Wattenhofer [IW14], addressing their open problem. See Table 1 for a concise summary of previous and our
results.
We note that to the best of our knowledge, all existing routing schemes [PU89, ABLP90, TZ05, AGM04,
Che13, LP16], as well as the routing scheme that we present in this paper, enable distance estimation,
i.e., given routing tables and labels of a pair u, v of vertices, one can compute (without communication) a
ˆ v), which approximates the actual distance dG (u, v) between u and v up to the stretch
distance estimate d(u,
factor of the routing scheme. All routing schemes of this type require, by the lower bound of [IW14], at
least n1/2+Ω(1/k) rounds to compute.
When preparing this submission, we learnt that concurrently√and independently of us [LPP16] came
up with a distributed algorithm running in (n1/2+1/k + D) · 2Õ( log n) rounds, that with high probability,
computes a routing scheme with routing tables of size Õ(n1/k ), labels of size O(k log2 n), and stretch
at most
p 4k − 3 + o(1). Their result has slightly worse stretch, and a larger number of rounds whenever
k < log n/ log log n, or if k is odd.
6

In fact, they showed a scheme in which it suffices to have a sketch of one vertex, and a O(k log n) size label of the other vertex,

3

[TZ01, Che13]
[LP15]
[LP13a, LP15]
[LP15]
This paper,
even k
This paper,
odd k

Number of Rounds
O(m)
1
Õ(S + n k )
1
1
Õ(n 2 + 4k + D)
1
2
2
1
Õ(min{(nD) 2 · n k , n 3 + 3k + D})
√
1
1
(n 2 + k + D)·min{(log n)O(k) , 2Õ( log n) }
1

√

1

(n 2 + 2k + D)·min{(log n)O(k) , 2Õ(

Table size
1
Õ(n k )
1
Õ(n k )
1
1
Õ(n 2 + 4k )
1
Õ(n k )
1
Õ(n k )

log n) }

1

Õ(n k )

Label size
O(k log n)
O(k log n)
O(log n)
O(k log2 n)
O(k log2 n)

Stretch
3.68k
4k − 3
6k − 1 + o(1)
4k − 3 + o(1)
4k − 5 + o(1)

O(k log2 n)

4k − 5 + o(1)

Table 1: Comparison of compact routing schemes for graphs with n vertices, m edges, hop-diameter D, and
shortest path diameter S.

1.1 Overview of Techniques
Let us first briefly sketch the Thorup-Zwick construction of a routing scheme. First they designed a routing
scheme for trees, with routing tables of constant size and logarithmic label size. (Throughout the paper, the
size is measured in RAM words, i.e., each word is of size O(log n).) For a general graph G = (V, E) on n
vertices, they randomly sample a collection of sets V = A0 ⊇ A1 · · · ⊇ Ak = ∅, where for each 0 < i < k,
each vertex in Ai−1 is chosen independently to be in Ai with probability n−1/k . The cluster of a vertex
u ∈ Ai \ Ai+1 is defined as
C(u) = {v ∈ V : dG (u, v) < dG (v, Ai+1 )} .

(1)

They proved that each cluster C(x) can be viewed as a tree rooted at x, and showed an efficient procedure
that given a pair u, v ∈ V , finds a vertex x so that routing in the tree C(x) has small stretch. So each vertex
u maintains in its routing table the routing information for all trees C(x) containing it, while the label of u
consists of the tree-labels for a few special trees. They also show that (with high probability) every vertex is
contained in at most Õ(n1/k ) trees.
The first difficulty we must deal with is that the routing scheme of Thorup-Zwick for a (single) tree
could take a linear number of rounds to construct. We thus develop a variation on that scheme, that can
be implemented efficiently in a distributed network. The basic idea is inspired by [KP98] (and also used
√
in [Nan14]), which is to select ≈ n vertices that partition the tree into bounded depth subtrees. We then
apply the TZ-scheme locally in every subtree. The subtler part is to design a global routing scheme for the
virtual tree7 induced on the sampled vertices, which must incorporate the local routing information.
Approximate Clusters. Once we have a distributed algorithm for routing in trees, we set off to apply the
TZ-scheme for general graphs. Unfortunately, it is not known how to compute the exact clusters efficiently
in a distributed manner. In order to circumvent this barrier, we introduce the notion of approximate clusters.
An approximate cluster is a subset of a cluster, that may exclude vertices that are ”near” the boundary.
(Slightly more formally, we may omit vertices for which the inequality (1) becomes false if we multiply
the left hand side by a 1 + ǫ factor, for a small ǫ > 0.) Our main technical contributions are: exhibiting
to derive the distance estimation. Our result has a similar property.
7
By a virtual tree we mean a tree whose edges are not present in the network.

4

a procedure that computes these approximate clusters, and showing that these approximate clusters are
sufficient for constructing a routing scheme, with nearly matching size and stretch as in [TZ01].
The construction of clusters C(u) for u ∈ Ai \ Ai+1 , where i < k/2, can be done in a straightforward
√
manner (within the allotted number of rounds), since the depth of the corresponding tree is Õ( n) with
high probability, and since the overlap (the number of clusters containing a fixed vertex) is only Õ(n1/k ).
The main challenge is computing the approximate clusters in the large scales, for i ≥ k/2. To this end,
we employ several tools. The first is approximate multi-source hop-bounded distance computation, which
appeared recently in [Nan14] (a certain variant of it appeared also in [LP13b]). This enables us to compute
approximations for B-hops shortest paths (paths that use at most B edges), from a given m sources to every
vertex, in Õ(B + m + D) rounds. The second tool we use is hopsets. The notion of hopsets was introduced
by [Coh00] in the context of parallel approximate shortest path algorithms, and it has found applications in
dynamic, streaming and distributed settings as well [Ber09, HKN14, HKN16]. A (β, ǫ)-hopset is a (small)
set of edges F , so that every shortest path has a corresponding β-hops path, whose weight is at most 1 + ǫ
larger.
√
We compute the approximate clusters in the large scales as follows. First we sample ≈ n vertices
√
(those in Ak/2 ), and compute approximate n-hops shortest paths from all the sampled vertices. Next we
√

apply a (β, ǫ)-hopset on the graph induced by these sampled vertices, where β ≤ 2Õ( log n) and ǫ ≈ 1/k4 .
(A pair of sampled vertices is connected in this graph if and only if one is reachable from the other via an
√
approximate n-hop-bounded shortest path.) An efficient distributed algorithm to construct such hopsets is
given by [HKN16, EN16a]. We shall use the construction of [EN16a], since it facilitates much smaller β,
whenever k is small. (There are also some additional properties of hopsets from [EN16a], that make them
more convenient in the context of routing. See Section 2.) This enables us to compute the approximate
clusters on the sampled vertices, since we need only β steps of exploration from each source u, using again
that the overlap is small. Finally, we extend each approximate cluster to the other vertices, by initiating
√
an exploration from each sampled vertex to hop-distance ≈ n in the original graph (in fact, one can use
the multi-source hop-bounded distance computation of [Nan14]). The correctness follows since with high
probability, every vertex that should be included in some approximate cluster C̃(u), has either u or a sampled
√
vertex within ≈ n hops on the shortest path to it. The thresholds for entering an approximate cluster must
be set carefully, so that every vertex on that shortest path will also join C̃(u), in order to guarantee that the
trees will indeed be connected (which is clearly crucial for routing), and on the other hand, to make sure that
no vertex participates in too many trees. Unlike the exact TZ clusters, approximate clusters generally do not
have to be connected.
The fact that our clusters are only approximate induces increased stretch. The analysis is similar to that
of [TZ05], which consists of k iterations of searching for the ”right” tree. We must pay a factor of 1 + O(ǫ)
in every one of these iterations, but fortunately, the hopset construction allows us to take sufficiently small
ǫ, so that all the additional stretch accumulates to an additive o(1).
From a high level, our approach is similar to those of [LP13a, LP15]. In [LP15], they also use a variant
of the TZ-routing scheme, which allows small errors in the distance estimations. The main difference is
√
in handling the large scales. In [LP13a], the idea was to build a spanner on a sample of ≈ n vertices,
which reduces the number of edges. So a routing scheme can be efficiently computed on the spanner, and
then extended to the entire graph. This approach inherently suffers from large storage requirement, since
every vertex needs to know all the spanner edges. In [LP15] the idea was to ”delay” the start of large scales
from k/2 to roughly l0 = (k/2) · (1 + log D/ log n). Then they apply a distance estimation on the sampled
vertices at scale l0 (those in Al0 ) to construct the routing tables for all higher scales, and extend these to
the remainder of the graph. However, the exploration in the graph on Al0 may need to be of ≈ n1−l0 /k
5

hops, which induces a factor of D · n1−l0 /k = (nD)1/2 to the number of rounds. The use of hopsets allows
us to avoid the large memory requirement, since the routing is oblivious to the hopset, while significantly
shortening the exploration range. Since the exploration range is proportional to the running time, the latter
also decreases.

1.2 Organization
After stating in Section 2 some of the tools we shall apply, in Section 3 we describe the notion of approximate clusters, and show how to compute these efficiently in a distributed manner. Then in Section 4,
we demonstrate how these approximate clusters could be used for a routing scheme in general graphs. In
Section 5 we show the distance estimation scheme. Finally, in Section 6 we show our distributed tree routing.

2 Preliminaries
Let G = (V, E, w) be a weighted graph on n vertices. We assume that w : E → {1, . . . , poly(n)} (without
this assumption, there will be a logarithmic dependence on the aspect ratio in the data structures’ size and
running times). Let D be the hop-diameter of G, that is, the diameter of G if all weights were 1. Denote
(t)
by dG the shortest path metric on G. Let dG be the t-hops shortest path distance (abusing notation, since
(t)
this is not a metric). That is, dG (u, v) is the shortest length of a path from u to v, that has at most t edges
(t)
(set dG (u, v) = ∞ if every path from u to v has more than t edges). For each u, v ∈ V , define hG (u, v)
as the number of hops on the shortest path in G between u and v. We shall always use this notation with
respect to the input graph G, and thus will omit the subscript. A (dominating) virtual graph on G is a graph
G′ = (V ′ , E ′ , w′ ) with V ′ ⊆ V , and for every u, v ∈ V ′ we have that dG′ (u, v) ≥ dG (u, v). Every vertex
in V ′ should know all the edges of E ′ touching it. The following lemma formalizes the broadcast ability of
a distributed network (see, e.g., [Pel00a]).
P
Lemma 1. Suppose every v ∈ V holds mv messages, each of O(1) words, for a total of M = v∈V mv .
Then all vertices can receive all the messages within O(M + D) rounds.

2.1 Tools
We will make use of the following theorem due to [Nan14, Theorem 3.6], which shows how to compute
hop-bounded distances from a given set of sources, efficiently in a distributed manner.
Theorem 1 ([Nan14]). Given a weighted graph G = (V, E, w) of hop-diameter D, a set V ′ ⊆ V , and
parameters B ≥ 1 and 0 < ǫ < 1, there is a (randomized) distributed algorithm that w.h.p runs in
Õ(|V ′ | + B + D)/ǫ rounds, so that every u ∈ V will know values {duv }v∈V ′ satisfying8
(B)

(B)

dG (u, v) ≤ duv ≤ (1 + ǫ)dG (u, v) ,

(2)

Remark 1. While not explicitly stated in [Nan14], the proof also provides that each u ∈ V knows, for every
v ∈ V ′ , a vertex p = pv (u) which is a neighbor of u satisfying
duv ≥ w(u, p) + dpv .
8

The computed values are symmetric, that is, duv = dvu whenever u, v ∈ V ′ .

6

(3)

Hopsets.

The following notion of hopsets was introduced by [Coh00].

Definition 1 (Hopsets). A set of (weighted) edges F is a (β, ǫ)-hopset for a graph G = (V, E), if in the
graph H = (V, E ∪ F ), for every u, v ∈ V ,
(β)

dG (u, v) ≤ dH (u, v) ≤ dH (u, v) ≤ (1 + ǫ)dG (u, v) .

(4)

We will need the following path-reporting property from our hopset. This property will be crucial for
the connectivity of the trees corresponding to the approximate clusters.
Property 1. A hopset F for a graph G is called path-reporting, if for every hopset edge (u, v) ∈ F of weight
b, there exists a corresponding path P in G between u and v of length b. Furthermore, every vertex x on P
knows dP (x, u) and dP (x, v), and its neighbors on P .
The following result is from [EN16a], which provides a path-reporting hopset. We remark that the
original hopset construction of [Coh00] could be made path-reporting. Also, in [HKN16, Theorem 4.10],
a distributed algorithm constructing a hopset is provided, which√ possibly could be made path-reporting,
however, it inherently cannot provide a better hopbound than 2Õ( log n) .
Theorem 2 ([EN16a]). Let G be a weighted graph on n vertices with hop-diameter D, let 0 < ǫ < 1, and let

O(1/ρ)
m
G′ be a virtual graph on G with m vertices. Let 0 < ρ < 1/2 be a parameter, and write β = log
.
ǫ·ρ

Then there is a randomized distributed algorithm that w.h.p computes in Õ(m1+ρ + D) · β 2 rounds, a
path-reporting (β, ǫ)-hopset F for G′ .
We remark that in many applications (see, e.g., applications in [Coh00, EN16a]) the size of the hopset
is important. However, here we only care about the size to the extent that it affects the number of rounds
required to compute the hopset.
Approximate Shortest Path Tree (SPT). Recently, [HKN16] obtained an efficient distributed algorithm
for computing an approximate SPT, which we shall use. Let us first define the problem formally. Let
G = (V, E, w) be a weighted graph. Given a set of vertices A ⊆ V , computing an (1 + ǫ)-approximate SPT
ˆ satisfying
rooted at A, means that every vertex u ∈ V will know a value d(u)
ˆ ≤ (1 + ǫ)dG (u, A) ,
dG (u, A) ≤ d(u)

(5)

ˆ
and that u will know a vertex ẑ(u) ∈ A so that dG (u, ẑ(u)) ≤ d(u).
The following theorem is a slight
variation on a theorem shown in [HKN16]. Here we use the hopsets of [EN16a] for an improved running
time.
Theorem 3. Let G = (V, E, w) be a weighted graph on n vertices with hop-diameter D. Given a set
√
1
A ⊆ V of size |A| ≤ 2 n ln n, and polylog
n < ǫ < 1, there is a distributed algorithm that computes an
√

(1 + ǫ)-approximate SPT rooted at A in (n1/2+1/(2k) + D) · min{(log n)O(k) , 2Õ(
We defer the proof to Appendix A.

7

log n) }

rounds.

3 Distributed Routing Scheme
In this section we define the notions of approximate pivots and approximate clusters, and describe an efficient
distributed algorithm that computes these. Let us first recall the basic definitions from [TZ05].
Let G = (V, E, w) be a weighted graph, fix k ≥ 1. Sample a collection of sets V = A0 ⊇ A1 · · · ⊇
Ak = ∅, where for each 0 < i < k, each vertex in Ai−1 is chosen independently to be in Ai with probability
n−1/k . A point z ∈ Ai is called an i-pivot of v, if dG (v, z) = dG (v, Ai ). The cluster of a vertex u ∈
Ai \ Ai+1 is defined as
C(u) = {v ∈ V : dG (u, v) < dG (v, Ai+1 )} .
(6)
We quote a claim from [TZ05], which provides a bound on the overlap of clusters.
Claim 2. With high probability, each vertex is contained in at most 4n1/k log n clusters.
The following claim shows that (with high probability) the sets Ai have favorable properties.
Claim 3. With high probability the following holds for every 0 ≤ i ≤ k − 1: (1) |Ai | ≤ 4n1−i/k ln n,
and (2) For every u, v ∈ V such that h(u, v) > 4ni/k ln n, there exists a vertex of Ai on the shortest path
between u and v.
Proof. Fix i. The first assertion holds by a simple Chernoff bound, since every vertex is chosen to be in Ai
independently with probability n−i/k , and the expected size of Ai is n1−i/k . For the second assertion, let
u, v be such that h(u, v) > 4ni/k ln n (recall that h(u, v) is the number of hops on the shortest path from u
to v in G). The probability that none of the vertices on the u to v shortest path is included in Ai is at most
4ni/k ln n

1 − n−i/k
≤ n−4 .
Taking a union bound on the k possible values of i and

n
2

pairs completes the proof.

From now on assume that all the events in the claims above hold, which yields the following corollary.
Corollary 4. For any 0 ≤ i < k − 1, u ∈ Ai \ Ai+1 and v ∈ C(u), it holds that h(u, v) ≤ 4n(i+1)/k ln n.
Proof. If it were the case that h(u, v) > 4n(i+1)/k ln n, then Claim 3 would imply that there exists a vertex
of Ai+1 on the shortest path from v to u. In particular, dG (v, u) > dG (v, Ai+1 ), which contradicts (6).

3.1 Approximate Clusters and Pivots
Since we do not know how to compute efficiently in a distributed manner the pivots and clusters, we settle
1
for an approximate version, which is formally defined in this section. Fix the parameter ǫ = 48k
4 . For each
v ∈ V and 0 ≤ i ≤ k − 1, a point ẑ ∈ Ai is called an approximate i-pivot of v if
dG (v, ẑ) ≤ (1 + ǫ)dG (v, Ai ) .

(7)

Now we define for each 0 ≤ i ≤ k − 1 and each vertex u ∈ Ai \ Ai+1 , a set of vertices which we call an
approximate cluster. The approximate cluster is a subset of the cluster C(u), and it is allowed to exclude
vertices of C(u) which are ”close” to the boundary. First define the vertices that are far from the boundary
(with respect to ǫ), as
dG (v, Ai+1 )
}.
(8)
Cǫ (u) = {v ∈ V : dG (u, v) <
1+ǫ
8

The approximate cluster C̃(u) will be a set that satisfies the following:
C6ǫ (u) ⊆ C̃(u) ⊆ C(u) .

(9)

Each approximate cluster C̃(u) we compute, will be stored as a tree rooted at u, that is, each vertex
v ∈ C̃(u) will store a pointer to its parent in the tree. This tree (abusing notation, we call this tree C̃(u) as
well) has the property that distances to the root u are approximately preserved, that is, for any v ∈ C̃(u) we
have that
dG (u, v) ≤ dC̃(u) (u, v) ≤ (1 + ǫ)4 dG (u, v) .
(10)
Remark 2. Since C̃(u) ⊆ C(u), Claim 2 implies that with high probability, each vertex is contained in at
most 4n1/k log n approximate clusters.
In the remainder of this section we devise an efficient distributed algorithm for computing the approximate pivots and the trees built from approximate clusters, and show the following.
Theorem 4. Let G = (V, E) be a weighted graph with n vertices and hop-diameter D, and let k ≥ 1 be an
integer. Set ǫ = 1/(48k4 ). Then there is a randomized distributed algorithm that w.h.p computes all approxi√
mate pivots and approximate clusters (with respect to ǫ) within (n1/2+1/k +D)·min{(log n)O(k) , 2Õ( log n) }
rounds.9
Computing Pivots. We first compute the pivots for 0 ≤ i ≤ ⌈k/2⌉. For these values of i we can compute
the exact pivots. We conduct 4ni/k · ln n iterations of Bellman-Ford rooted in the vertex set Ai . As a result,
every v ∈ V learns the exact value dˆi (v) = dG (v, Ai ) and a pivot ẑi (v) ∈ Ai . Indeed, for any v ∈ V , if
u ∈ Ai is a vertex such that dG (v, u) = dG (v, Ai ), then Claim 3 implies that h(v, u) ≤ 4ni/k · ln n, so
the exploration will detect this shortest path. As every message consists of O(1) words (every vertex sends
to its neighbors the name of the vertex in Ai and the current distance to it), the total number of rounds is
P⌈k/2⌉
i/k · ln n) ≤ Õ(n1/2+1/(2k) ).
i=0 O(n
For ⌈k/2⌉ < i ≤ k − 1 we can only compute approximate pivots ẑi (v) for each v ∈ V . For each such
i, apply Theorem 3 with root set Ai and the parameter ǫ (indeed by Claim 3, |Ai | ≤ 4n1−(⌈k/2⌉+1)/k√ln n ≤
√
2 n ln n, and ǫ = Ω(1/k 4 ) ≥ Ω(1/ log 4 n)). This will take (n1/2+1/(2k) +D)·min{(log n)O(k) , 2Õ( log n) }
rounds. At the end, every vertex v ∈ V will know its approximate pivot ẑi (v), and the (approximate) distance
dˆi (v), as returned by the algorithm. By (5), ẑi (v) satisfies the requirement from an approximate pivot (see
(7)).

3.2 Building the Small Trees
For 0 ≤ i < ⌈k/2⌉, we can compute the trees C(u) corresponding to the actual clusters. We need to find
such a tree for every u ∈ Ai \ Ai+1 , and it is done in the following manner. For each such u in parallel,
we initiate a bounded-depth Bellman-Ford exploration for 4n(i+1)/k ln n iterations. By bounded-depth we
mean the following: each v ∈ V that receives a message originated at u, and computes that its (current)
distance to u is bv (u), will join C(u) and broadcast the message to its neighbors in G iff
bv (u) < dG (v, Ai+1 ) .
9

For odd k the number of rounds becomes (n1/2+1/(2k) + D) · min{(log n)O(k) , 2Õ(

9

(11)
√

log n)

}.

(Recall that for i ≤ ⌈k/2⌉, each vertex stores the distance to the exact i-th pivot dˆi (v) = dG (v, Ai ).) The
vertex v will also store the name of its parent in C(u), the neighbor p ∈ V that sent v the message which
last updated bv (u).
We now argue that if v ∈ C(u), then v will surely receive a message from u and will have bv (u) =
dG (u, v). Let P be the shortest path in G between u and v. Note that every vertex y on P has y ∈ C(u),
because
(6)
dG (y, u) = dG (v, u) − dG (v, y) < dG (v, Ai+1 ) − dG (v, y) ≤ dG (y, Ai+1 ) .
It follows by a simple induction that every such y will receive a message with the exact distance by (u) =
dG (y, u) and thus will send it onwards, after at most h(u, y) steps of the algorithm. In particular, distances
to the root u in C(u) are preserved exactly. Corollary 4 asserts that for all v ∈ C(u) we have that h(u, v) ≤
4n(i+1)/k ln n. So there are enough Bellman-Ford iterations to reach all vertices of C(u).
The middle level. When k is odd, the level i = (k − 1)/2 induces a relatively large running time
Õ(n1/2+3/(2k) ) (see the upcoming paragraph on running-time analysis), if one uses the algorithm that was
described above. To overcome this, we use a different method for this level. We apply Theorem 1 on the set
of sources S = Ai \ Ai+1 , with B = 4n(i+1)/k · ln n and ǫ, each vertex v ∈ V will get a distance estimate
bv (u) for each u ∈ S. Indeed, if v ∈ C(u) then by Corollary 4, h(u, v) ≤ B, so that the distance estimate
(B)
returned by the theorem is a 1 + ǫ approximation to dG (u, v) = dG (u, v).
We say that v joins the (approximate) cluster C̃(u) of u ∈ S if the following holds
bv (u) < dG (v, Ai+1 ),
(recall that v knows the exact distance to its i + 1 = (k + 1)/2-pivot). The parent p of v in the tree induced
by C̃(u) will be the parent given by Remark 1. We show that this p will join C̃(u) as well. This holds
because
(3)

bp (u) ≤ bv (u) − w(v, p) < dG (v, Ai+1 ) − dG (v, p) ≤ dG (p, Ai+1 ) .
Finally, we note that this is an approximate cluster; since dG (u, v) ≤ bv (u) it follows that C̃(u) ⊆ C(u),
while if v ∈ Cǫ (u) then
(2)

(8)

bv (u) ≤ (1 + ǫ)dG (u, v) < dG (v, Ai+1 ) ,
so C̃(u) ⊇ Cǫ (u), satisfying (9). (We remark that the middle level is the only one in which one may
use Theorem 1. In all other levels, either the number of sources |Ai | ≈ n1−i/k or the required depth
B ≈ n(i+1)/k will be larger than n1/2+1/k .)
Running time. By Claim 2, every vertex can belong to at most Õ(n1/k ) clusters. Hence, the congestion
at every Bellman-Ford iteration is at most Õ(n1/k ). Thus the number of rounds required to implement
each of the 4n(i+1)/k ln n iterations of Bellman-Ford is Õ(n1/k ). When k is even, the total running time is
Pk/2−1
Õ(n(i+2)/k ) = Õ(n1/2+1/k ). When k is odd, the middle level (k − 1)/2 will take time Õ(|S| +
i=0
P(k−3)/2
B + D) = Õ(n1/2+1/(2k) + D), while the lower levels will take i=0
Õ(n(i+2)/k ) = Õ(n1/2+1/(2k) ).
1/2+1/(2k)
So for odd k, the total running time is Õ(n
+ D) .

10

3.3 Building the Large Trees
Building the trees C̃(u) for u ∈ Ai \ Ai+1 when i ≥ ⌈k/2⌉ is more involved, since the number of iterations
for the simple Bellman-Ford style approach grows like ≈ n(i+2)/k . We will use the fact that there are only
few vertices in Ai , and divide the computation into two phases. In the first phase we compute virtual trees
√
only on ≈ n vertices, and in the second phase we extend the trees to the entire graph. Before we turn to
the two-phase construction, we describe the preprocessing stage, in which we build structures that are later
used in both phases.
3.3.1

Preprocessing

Let V ′ = A⌈k/2⌉ , and set B = 4n/E[|V ′ |] · ln n. That is, for even k we set B = 4n1/2 · ln n, while for odd
k, B = 4n1/2+1/(2k) · ln n. Apply Theorem 1 to G with the set V ′ and parameters B and ǫ/2. By Claim 3
we may assume |V ′ | ≤ 4n1/2 ln n, and since 1/ǫ ≤ 48 log 4 n, the number of rounds required is w.h.p
Õ(n1/2+1/(2k) + D). From now on assume that (2) indeed holds (with ǫ replaced by ǫ/2). This happens
w.h.p. Let G′ = (V ′ , E ′ , w′ ) be a (virtual) graph on G, and for each u, v ∈ V ′ with duv < ∞, set the
weight of the edge connecting them to be w′ (u, v) = duv (where duv is the value computed in Theorem 1).
Following [Nan14], it can be shown that for any u, v ∈ V ′ ,
dG (u, v) ≤ dG′ (u, v) ≤ (1 + ǫ/2)dG (u, v) .

(12)

√
ǫ/3 and ρ = max{1/k, log log n/ log n}. We obtain a
Apply Theorem 2 on G′ with parameters
√
n) , (log n)O(k) }. The number of rounds required is Õ(|V ′ |1+ρ +
(β, ǫ/3)-hopset F with β = min{2Õ( log
√
D) · β 2 = (n1/2(1+1/k) + D) · min{2Õ( log n) , (log n)O(k) }.
Let G′′ = (V ′ , E ′ ∪ F, w′′ ) be the graph obtained from G′ by adding all the hopset edges. (Note that
some edges may have their weight replaced. In the case of conflict, the weights w′′ agree with the weights
of the hopset F .) By (4) and (12) we have that G′′ is indeed a virtual graph since dG′′ (u, v) ≥ dG′ (u, v) ≥
dG (u, v). On the other hand,
(β)

dG′′ (u, v) ≤ (1 + ǫ/3)dG′ (u, v) ≤ (1 + ǫ/2)(1 + ǫ/3)dG (u, v)
≤ (1 + ǫ)dG (u, v) .

We conclude that the graph G′′ satisfies the following property: for every u, v ∈ V ′ ,
(β)

dG (u, v) ≤ dG′′ (u, v) ≤ (1 + ǫ)dG (u, v) .
3.3.2

(13)

Construction

Fix ⌈k/2⌉ ≤ i ≤ k − 1. We build the trees C̃(u) for all u ∈ Ai \ Ai+1 in parallel, in two main phases.
Phase 1. For each such u, conduct β iterations of depth-bounded Bellman-Ford in the graph G′′ .10 (Since
this is a virtual graph, all the messages will be collected at the root of some BFS tree of G via pipelined
convergecast, and then broadcasted to the entire graph G via pipelined broadcast. See Lemma 1.) If v ∈ V ′
10

See (14) below for the required condition on depth.

11

receives a message originated at u with (current) distance to u which is bv (u), it will join the approximate
cluster of u and forward the message to its neighbors in G′′ iff
bv (u) <

dˆi+1 (v)
.
(1 + ǫ)3

(14)

(Recall that dˆi+1 (v) is the approximate distance from v to the its (approximate) level i + 1 pivot.) The vertex
v will also store its virtual parent, the neighbor p ∈ V ′ that sent v the message which last updated bv (u). For
each u ∈ Ai \ Ai+1 , we have a (virtual) tree C̃ ′ (u) on the vertices of V ′ that received a message originated
at u and satisfy (14).
Phase 1.5. The purpose of this step is to guarantee that every vertex which was added to the (virtual) tree
being built for some u ∈ Ai \ Ai+1 , will have an appropriate parent in G (through which it will route later
on). The issue is that hopset edges are not equipped with parents in G, unlike the edges of G′ , for which
Remark 1 provides parents. We deal with this by using the path-reporting property of hopset edges – each
such edge is realized by a path in G′ , so we ensure the vertices of this path join the tree as well, and set
parents accordingly. We now describe this formally.
When the first phase ends after β iterations, for every hopset edge (x, y) ∈ F such that x is the virtual
parent of y we do the following. Let P be the path in G′ realizing this edge. Each v ∈ V ′ (P ) \ {x} that
has bv (u) value (for some u ∈ Ai \ Ai+1 ) at least bx (u) + dP (x, v), updates its distance estimate to be
bv (u) = bx (u) + dP (x, v), joins C̃ ′ (u) (if it hasn’t already), and sets its virtual parent as v ′ , where v ′ is the
neighbor of v on P closer to x (recall Property 1, which guarantees that v knows the relevant information).
Finally, set the real parents: for each vertex v ∈ C̃ ′ (u) with a virtual parent v ′ , set p(v) = pv′ (v) (see
Remark 1 for the definition and computation of pv′ (v)). Recall that (v, v ′ ) is a virtual edge (of the graph
G′ ), while (v, p(v)) is a “real” edge from G.
Phase 2. Here we extend each virtual tree C̃ ′ (u) to the vertices of V . For all u ∈ Ai \ Ai+1 , every vertex
v ∈ C̃ ′ (u) broadcasts to the entire graph its value bv (u) (and the name of u). A vertex y ∈ V will add itself
to C̃(u) if
dˆi+1 (y)
dyv + bv (u) <
,
(15)
1+ǫ
where dyv is the value computed in Theorem 1. Also, y will set p(y) = pv (y) as its (real) parent in C̃(u) for
the v minimizing by (u) = dyv + bv (u) (breaking ties arbitrarily). We remark that the condition of (15) is
less stringent than that of (14). Thus vertices of V ′ who did not join C̃ ′ (u), may now be included in C̃(u).
First we argue that for any u ∈ Ai \ Ai+1 , the vertices v ∈ V ′ added to C̃ ′ (u) in phase 1.5 with distance
estimate bv (u) satisfy the following:
dˆi+1 (v)
.
(16)
bv (u) <
(1 + ǫ)2
To see this, let (x, y) ∈ F be the hop-set edge which triggered the addition of v to C̃ ′ (u) at phase 1.5, and
let P be the path in G′ realizing this edge, then
bv (u) = dP (x, v) + bx (u) = dP (x, y) − dP (v, y) + bx (u) = by (u) − dP (v, y) .
It follows that
(14)

bv (u) = by (u)−dP (v, y) <

(5) dG (y, Ai+1 ) − dG (v, y)
dG (v, Ai+1 ) (5) dˆi+1 (v)
dˆi+1 (y)
−d
(v,
y)
≤
,
≤
≤
G
(1 + ǫ)3
(1 + ǫ)2
(1 + ǫ)2
(1 + ǫ)2

12

which proves (16). The next lemma asserts that the values bv (u) approximate well the distances to the root
u of the virtual tree.
Lemma 5. For any u ∈ Ai \ Ai+1 and v ∈ C̃(u) with the corresponding value bv (u), we have that
dG (u, v) ≤ bv (u) ≤ (1 + ǫ)4 dG (u, v) .

(17)

Proof. First we prove for v ∈ C̃ ′ (u) added at phase 1. Note that the left hand side of (17) can be verified
by induction on the iteration in which bv (u) was last updated. The base case u = v clearly holds, assume it
holds for v ′ (the virtual parent of v). Recall that w′′ is the weight function in G′′ . We have
(13)

bv (u) = w′′ (v, v ′ ) + bv′ (u) ≥ dG′′ (v, v ′ ) + dG (u, v ′ ) ≥ dG (u, v) .
We now turn to the right hand side of (17). Seeking contradiction, assume
bv (u) > (1 + ǫ)4 dG (u, v) .

(18)

Let P be the shortest β-hops path in G′′ from u to v, and we will show (by induction) that every vertex
z on P , which lies h hops from u, must join C̃ ′ (u) with value bz (u) ≤ dP (u, z) by the iteration h of the
Bellman-Ford exploration of phase 1. The base case for z = u clearly holds. Fix any other z ∈ P with h
hops to u on P , and assume it holds for p, the neighbor of z on P (the one closer to u), so we have that
bp (u) ≤ dP (u, p) by iteration h − 1. At iteration h, p will broadcast its value bp (u), and thus z could have
updated its value to be bp (u) + w′′ (p, z). In particular,
bz (u) ≤ bp (u) + w′′ (p, z) ≤ dP (u, p) + w′′ (p, z) = dP (u, z).

(19)

We now argue bz (u) satisfies (14), which would cause z to join C̃ ′ (u),
bz (u)

(19)

≤

dP (u, z)

≤

dG′′ (u, v) − dG (v, z)

=

(13)

dP (u, v) − dP (v, z)
(β)

≤ (1 + ǫ)dG (u, v) − dG (v, z)
(18)
bv (u)
≤
− dG (v, z)
(1 + ǫ)2
(14)
dˆi+1 (v)
<
− dG (v, z)
(1 + ǫ)4
(5)
dG (v, Ai+1 ) − dG (v, z)
≤
(1 + ǫ)3
dG (z, Ai+1 )
≤
(1 + ǫ)3
(5)
dˆi+1 (z)
,
≤
(1 + ǫ)3

(20)

(21)
(22)

where (20) uses that P is the shortest β-hops path in G′′ , and (21) uses the contradiction assumption (18)
(note that it was used with the term (1 + ǫ)3 rather than (1 + ǫ)4 ). Hence z joins C̃ ′ (u), and so bv (u) ≤
dP (u, v). Hence
(β)

(13)

bv (u) ≤ dP (u, v) = dG′′ (u, v) ≤ (1 + ǫ)dG (u, v),
13

which contradicts our assumption that (17) does not hold.
We now turn to vertices v ∈ C̃ ′ (u) who joined in phase 1.5. The left hand side holds since if (x, y) ∈ F
is the hop-set edge that triggered the addition of v, and P ′ is the path in G′ realizing this edge, we have that
bv (u) = dP ′ (v, x) + bx (u) ≥ dG (v, x) + dG (x, u) ≥ dG (v, u). For the right hand side, note that we only
used the fact that v joined in phase 1 at (22), so we can repeat the argument, replacing the use of (14) by
(16). We indeed lose a factor of 1 + ǫ, but the inequality is still valid, yielding the same contradiction.
Finally, we turn to v ∈ C̃(u) joining at phase 2. Note that for each such v, there exists some x ∈ V ′ for
which v sets its value to be bv (u) = dvx + bx (u) ≥ dG (v, x) + dG (x, u) ≥ dG (v, u), which proves the left
hand side of (17). For the right hand side, consider first the case that h(v, u) ≤ B. Since v could update
bv (u) directly from the broadcast of u itself, we have
(2)

(B)

bv (u) ≤ 0 + dvu ≤ (1 + ǫ)dG (v, u) = (1 + ǫ)dG (v, u) .
The other case is when h(v, u) > B, but then Claim 3 (with i = ⌈k/2⌉) suggests that there exists x ∈ V ′ on
(B)
the shortest path in G from v to u, with h(v, x) ≤ B. In particular, dG (x, v) = dG (x, v). Again seeking
contradiction, assume (17) does not hold for v. Let P be the shortest (at most) β-hops path from u to x in G′′ .
We claim that every z ∈ P must have joined C̃ ′ (u) at phase 1. To see this by induction, fix z ∈ P with h hops
from u on P , and assume p (the neighbor of z closer to u) did join by the h−1 iteration of Bellman-Ford, with
bp (u) ≤ dP (u, p). When p broadcasts bp (u) at step h, then indeed bz (u) ≤ bp (u) + w′′ (p, z) = dP (u, z).
Now,
bz (u)

≤

dP (u, z)
(β)

≤

dG′′ (u, x) − dP (z, x)

≤

(1 + ǫ)dG (u, x) − dG (z, x)

(13)

=
≤
(15)

<

(7)

≤

≤
≤

(23)

(1 + ǫ)[dG (u, v) − dG (x, v)] − dG (z, x)
bv (u)
− dG (x, v) − dG (z, x)
(1 + ǫ)3
dˆi+1 (v)
− dG (x, v) − dG (z, x)
(1 + ǫ)4
dG (v, Ai+1 ) − dG (x, v) − dG (z, x)
(1 + ǫ)3
dG (z, Ai+1 )
(1 + ǫ)3
dˆi+1 (z)
.
(1 + ǫ)3

((23) is because x lies on the shortest u − v path in G.)
This implies bz (u) satisfies (14) and thus z indeed joins C̃ ′ (u) by iteration h of phase 1. In particular, x
joins by the end of phase 1, and broadcasts bx (u) at phase 2. Then we have that
(17)

4
bv (u) ≤ bx (u) + dxv ≤ (1 + ǫ)4 dG (u, x) + (1 + ǫ)dB
G (x, v) ≤ (1 + ǫ) dG (u, v) ,

(Recall that dxv is the value computed by the algorithm of Theorem 1.) This yields a contradiction to (18)
and concludes the proof.
14

The following lemma shows that the sets C̃(u) satisfy the requirement from approximate clusters. The
proof is similar to that of Lemma 5, though it uses the definition of Cǫ (u), rather than the (contradiction)
assumption that bv (u) is large.
Lemma 6. For any u ∈ Ai \ Ai+1 , the set C̃(u) satisfies (9).
Proof. For the right hand side of (9), note that if v ∈ C̃ ′ (u), then
(17)

dG (u, v) ≤ bv (u)

(14)∧(16)

<

dˆi+1 (v) (5)
≤ dG (v, Ai+1 ) ,
(1 + ǫ)2

so v ∈ C(u) as well. For the left hand side of (9) (at this point we only show that C̃ ′ (u) ⊇ C6ǫ (u) ∩ V ′ ),
consider v ∈ C6ǫ (u) ∩ V ′ , and let P be the (at most) β-hops shortest path from v to u in G′′ . It suffices to
show that every vertex y along this path which is h hops from u, will join C̃ ′ (u) and have by (u) ≤ dP (y, u)
by the iteration h of Bellman-Ford in phase 1. Assume (by induction) that p, the predecessor of y on P ,
joins C̃ ′ (u) and satisfies bp (u) ≤ dP (p, u) by iteration h − 1. Thus, p sends at iteration h the value bp (u).
Since by (u) ≤ w′′ (y, p) + bp (u) ≤ w′′ (y, p) + dP (u, p) = dP (u, y), it remains to show that this value of
by (u) satisfies (14), and thus y joins C̃ ′ (u). To this end,
by (u)

≤

dP (u, y)

≤

dG′′ (u, v) − dP (y, v)

≤

(1 + ǫ)dG (u, v) − dG (y, v)
(1 + ǫ)dG (v, Ai+1 )
− dG (y, v)
1 + 6ǫ
dG (v, Ai+1 ) − dG (y, v)
(1 + ǫ)3
dG (y, Ai+1 )
(1 + ǫ)3
dˆi+1 (y)
.
(1 + ǫ)3

(13)

≤
<
≤
(5)

≤

(β)

where the fourth inequality uses that v ∈ C6ǫ (u) (recall (8)). This implies v will join C̃ ′ (u) in phase 1.
We now prove that (9) holds for C̃(u). For the right hand side, let y ∈ C̃(u) \ C̃ ′ (u), then there exists
v ∈ V ′ for which y satisfies (15). So we obtain
dG (y, u) ≤ dG (y, v) + dG (v, u)

(2)∧(17)

≤

(15)

dyv + bv (u) <

dˆi+1 (y) (5)
≤ dG (y, Ai+1 ) .
1+ǫ

This implies that y ∈ C(u). For the left hand side of (9), assume y ∈ C6ǫ (u). Consider first the case that
h(u, y) ≤ B. Then when u broadcasts bu (u) = 0 at phase 2, y will add itself to C̃(u) because
(2)

(8)

(B)

dyu + 0 ≤ (1 + ǫ)dG (y, u) = (1 + ǫ)dG (y, u) ≤

(5) dˆi+1 (y)
1+ǫ
· dG (y, Ai+1 ) <
.
1 + 6ǫ
1+ǫ

(24)

The other case is that h(y, u) > B. Then by Claim 3 there is a vertex v ∈ V ′ on the shortest path from y to
u so that h(y, v) ≤ B. We now argue that v ∈ C̃ ′ (u), by a similar (though slightly more involved) argument
15

as above. To see this, consider the shortest path P with (at most) β-hops in G′′ from u to v, and we claim
that each vertex z on this path with h hops from u, will join C̃ ′ (u) with bz (u) ≤ dP (u, z) by iteration h of
the Bellman-Ford of phase 1. Again by induction, at step h the vertex z heard bp (u) ≤ dP (u, p) from its
predecessor p on P . Then indeed bz (u) ≤ bp (u) + w′′ (p, z) ≤ dP (u, z). Now we show that z joins C̃ ′ (u).
bz (u)

≤

=

(13)

≤

=
≤

≤
≤
(5)

≤

dP (u, z)
(β)

dG′′ (u, v) − dP (z, v)
(1 + ǫ)dG (u, v) − dG (z, v)

(1 + ǫ)[dG (u, y) − dG (y, v)] − dG (z, v)
(1 + ǫ)dG (y, Ai+1 )
− dG (y, v) − dG (z, v)
1 + 6ǫ
dG (y, Ai+1 ) − dG (y, v) − dG (z, v)
(1 + ǫ)3
dG (z, Ai+1 )
(1 + ǫ)3
dˆi+1 (z)
,
(1 + ǫ)3

(25)
(26)

where (25) uses that v is on the shortest path in G from u to y, and (26) uses that y ∈ C6ǫ (u). In particular,
(β)
we have shown v ∈ C̃ ′ (u) by the end of phase 1. It follows that v will broadcast the value bv (u) ≤ dG′′ (u, v)
in the second phase. Since h(y, v) ≤ B,
by (u)

≤

dyv + bv (u)

≤

(1 + ǫ)dB
G (y, v) + dG′′ (u, v)

≤

(1 + ǫ)[dG (y, v) + dG (u, v)]

(2)
(13)

=

(8)

≤

<

(β)

(1 + ǫ)dG (y, u)
1+ǫ
· dG (y, Ai+1 )
1 + 6ǫ
dˆi+1 (y)
.
1+ǫ

So y will be added to C̃(u). This concludes the proof of the lemma.
Our next goal to to argue that the parent setting ensures that root-vertex distances in each cluster tree
satisfy (10), i.e., are approximated up to a factor (1 + ǫ)4 . It suffices to prove the following claim.
Claim 7. For any u ∈ Ai \ Ai+1 , and any v ∈ C̃(u), if p = p(v) is the (real) parent of v with corresponding
value bp (u), then p ∈ C̃(u) and
bv (u) ≥ w(v, p) + bp (u) .
(27)
Once this claim is established, we get by induction on the depth of the tree that dC̃(u) (u, v) ≤ bv (u).
The base case when u = v clearly holds, assume for p = p(v) that dC̃(u) (u, p) ≤ bp (u), and now
(27)

dC̃(u) (u, v) = w(v, p) + dC̃(u) (u, p) ≤ w(v, p) + bp (u) ≤ bv (u) .
16

Combining this with Lemma 5 establishes (10).
Proof of Claim 7. Consider first the case that v ∈ C̃ ′ (u), and there are two sub-cases to consider. In the first
sub-case, v updated bv (u) in phase 1 from some x ∈ C̃ ′ (u), who sent bx (u) over the (virtual) edge (x, v) ∈
E ′ (which is not a hop-set edge). Then by the definition of G′ , bv (u) = w′ (x, v) + bx (u) = dxv + bx (u),
the virtual parent of v is set to x, and the real parent is thus p = px (v). Since p receives a message from x
in the second phase, it sets bp (u) to at most dpx + bx (u). It follows that
(3)

bp (u) ≤ dpx + bx (u) ≤ dvx − w(v, p) + bx (u) = bv (u) − w(v, p) ,

(28)

which satisfies (27). But we must also argue that p indeed joins the tree C̃(u). Here we use the relaxed
condition of (15) (compared to (14)), and obtain that
bp (u)

(28)

≤

(14)

<

(7)

≤

≤
≤

bv (u) − w(v, p)
dˆi+1 (v)
− dG (v, p)
(1 + ǫ)3
dG (v, Ai+1 ) − dG (v, p)
1+ǫ
dG (p, Ai+1 )
1+ǫ
dˆi+1 (p)
,
1+ǫ

(29)
(30)
(31)

which satisfies (15).
The second sub-case is that v updated bv (u) in phase 1 or 1.5 due to some hop-set edge (x, y) ∈ F , so
that v lies on the path P in G′ realizing this edge (it could be that y = v, if it happened in phase 1). We set
bv (u) = bx (u) + dP (x, v), and the virtual parent of v is v ′ ∈ V ′ , its neighbor on P which is closer to x.
Recall that in G′ , the weight w′ (v, v ′ ) = dvv′ , so that
dP (x, v) = dP (x, v ′ ) + dvv′ .
The real parent of v is set as p = pv′ (v). Since
dP (x, v ′ ), it follows that
bp (u)

v′

broadcasts in phase 2 its estimate bv′ (u) ≤ bx (u) +

≤

dpv′ + bv′ (u)

≤

(dvv′ − w(v, p)) + (bx (u) + dP (x, v ′ ))

=

bx (u) + dP (v, x) − w(v, p)

(3)
(32)

=

(32)

bv (u) − w(v, p) ,

as required in (27). Again, to see that p ∈ C̃(u), we repeat the calculation of (29) with one change: In (30),
replace the use of (14) by (16), which will have the factor of (1 + ǫ)3 replaced by (1 + ǫ)2 , but this suffices
to satisfy (31).
We turn to the case that v ∈ C̃(u) \ C̃ ′ (u). Let x ∈ C̃ ′ (u) be the vertex which broadcasts in phase 2 a
value bx (u) minimizing bv (u) = dvx + bx (u). The parent of v is thus set to be p = px (v), and now
(3)

bp (u) ≤ dpx + bx (u) ≤ dvx − w(v, p) + bx (u) = bv (u) − w(v, p) ,

The proof that p ∈ C̃(u) is again similar to (29).

17

Running Time.
We noted that the number of rounds required for the preprocessing is Õ(n1/2+1/(2k) +
√
D)·min{2Õ( log n) , (log n)O(k) }. Since by (9) we have C̃ ′ (u) ⊆ C(u), then Remark 2 suggests that v ∈ V ′
sends at most Õ(n1/k ) distance estimates bv (·). As |V ′ | ≤ Õ(n1/2 ), by Lemma 1, implementing a single
Bellman-Ford iteration will take Õ(n1/2+1/k + D) rounds. As there are β iterations
in phase 1 (and a single
√
one in phases 1.5 and 2), the total number of rounds is Õ(n1/2+1/k + D)·min{2Õ( log n)√, (log n)O(k) }. (For
odd k, both |V ′ | · n1/k , B ≤ Õ(n1/2+1/(2k) ), so we get Õ(n1/2+1/(2k) + D) · min{2Õ( log n) , (log n)O(k) }
rounds.)

4 Routing Based on Approximate Clusters
In this section we show that approximate pivots and approximate clusters suffice for a compact routing
scheme, and prove our main result.
Theorem 5. Let G = (V, E) be a weighted graph with n vertices and hop-diameter D, and let k ≥ 1 be a
parameter. Then there exists a routing scheme with stretch at most 4k − 5 + o(1), labels of size O(k log2 n)
and routing tables of size √O(n1/k log2 n), that can be computed in a distributed manner within (n1/2+1/k
+
√
O(k)
Õ(
log
n)
1/2+1/(2k)
O(k)
Õ(
log
n)
} rounds, and for odd k only (n
+D)·min{(log n)
,2
}
D)·min{(log n)
,2
rounds.
Construction. Apply Theorem 4 on G to obtain approximate pivots and approximate clusters for all vertices. For each 0 ≤ i ≤ k − 1 and each u ∈ Ai \ Ai+1 , construct the routing scheme for trees given
by Theorem 7 on C̃(u). (We postpone the proof of Theorem 7, i.e., the description of the algorithm that
constructs routing tables and labels for each tree, to Section 6.) Specifically, in each tree, every vertex stores
a table of size O(log n) and has a label of size O(log2 n). The routing table of each v ∈ V consists of all the
tree-routing tables, for every u ∈ V such that v ∈ C̃(u). The label of v consists of the tree-labels for the (at
most) k trees C̃(ẑ0 (v)), . . . , C̃(ẑk−1 (v)), where ẑi (v) is the approximate i-pivot of v (note that it could be
that v does not belong to some of these trees, the label of v will mark these as missing). By Remark 2 there
are at most O(n1/k log n) trees containing v, and as each tree-table is of size O(log n), the routing table size
is as promised. Since each tree-label is of size O(log2 n), the label size also obeys the given bound.
Finding a Tree. Assume we would like to route from vertex u to vertex v. The routing protocol will find
a vertex w = ẑi (v) for some 0 ≤ i ≤ k − 1, such that the stretch of the (unique) path from u to v in the tree
C̃(w) is at most 4k − 5 + o(1). The algorithm to find such a vertex appears in Algorithm 1.
Algorithm 1 Find-tree(u, v)
1: i ← 0;
2: while |{u, v} ∩ C̃(ẑi (v))| < 2 do
3:
i ← i + 1;
4: end while
5: return ẑi (v);
We note that our algorithm differs slightly from that of [TZ01], since it could be the case that v does not
belong to the cluster centered at the pivot of v at level i. For this reason we keep searching until we find a
cluster containing both u, v.
18

First we claim that the algorithm is correct. Note that the definition of approximate cluster (9) implies
that C̃(x) = V for every x ∈ Ak−1 (this holds since the distance to Ak is defined as ∞). Therefore when
i = k − 1 it must be that both u, v ∈ C̃(ẑk−1 (v)), and the algorithm indeed halts. The tree C̃(w) contains
both u, v (where w = ẑi (v) is the vertex returned by the algorithm), by definition. Finally, the information
from the label of v indicates which of these trees contain it, and the routing table of u also lists the names of
all trees containing it. So we can run the algorithm from u knowing the label of v.
Once u computes the root w, it appends w to the message header along with the label of v. From this
point on the header does not change, and we route in the tree C̃(w). Since this routing is exact, it remains
to bound the stretch incurred by using the tree.
Bounding Stretch. We distinguish between two types of iterations i that the algorithm did not stop at. Let
Iu = {0 ≤ i ≤ k − 1 : u ∈
/ C̃(ẑi (v))} be the iterations in which {u, v} ∩ C̃(ẑi (v)) is empty or contains
just v, and let Iv = {0 ≤ i ≤ k − 1 : {u, v} ∩ C̃(ẑi (v)) = {u}} be the remaining iterations in which
the algorithm did not halt. For any i ∈ Iu , by (9) it holds that C6ǫ (ẑi (v)) ⊆ C̃(ẑi (v)). Hence, we have
u∈
/ C6ǫ (ẑi (v)), which suggests that
(7)

dG (u, ẑi+1 (u)) ≤ (1 + ǫ)dG (u, Ai+1 )
(8)

≤ (1 + ǫ)(1 + 6ǫ)dG (u, ẑi (v))

≤ (1 + 8ǫ)dG (u, ẑi (v)) .

(33)

Similarly for i ∈ Iv ,
dG (v, ẑi+1 (v)) ≤ (1 + ǫ)dG (v, Ai+1 )

≤ (1 + ǫ)(1 + 6ǫ)dG (v, ẑi (v))

≤ (1 + 8ǫ)dG (v, ẑi (v)) .

(34)

Define the following values y0 = dG (u, v), x0 = 0, and for 0 < i ≤ k − 1 define recursively yi =
(1 + 10ǫ)[y0 + xi−1 ], and xi = (1 + ǫ)[y0 + yi ]. Assume that the algorithm halted at iteration i′ . Then for
each 0 ≤ i ≤ i′ we claim that
dG (v, ẑi (v)) ≤ xi .
(35)
We verify the validity of (35) by induction. The base case trivially holds since ẑ0 (v) = v and x0 = 0. Fix
0 < i ≤ i′ . The algorithm did not halt at iteration i − 1. If it is the case that i − 1 ∈ Iu , then we have that
dG (u, ẑi (u))

(33)

≤

(1 + 8ǫ)dG (u, ẑi−1 (v))

≤

(1 + 8ǫ)[dG (u, v) + dG (v, ẑi−1 (v))]

≤

(1 + 8ǫ)[y0 + xi−1 ]

(35)

≤

yi .

19

(36)

The other case is that i − 1 ∈ Iv . Since ẑi (u) ∈ Ai we obtain
dG (u, ẑi (u))

(7)

≤

≤

(1 + ǫ)dG (u, Ai )

(37)

(1 + ǫ)dG (u, ẑi (v))

≤

(1 + ǫ)[dG (u, v) + dG (v, ẑi (v))]

≤

(1 + ǫ)[dG (u, v) + (1 + 8ǫ)dG (v, ẑi−1 (v))]

(34)

≤

=

(1 + 10ǫ)[y0 + xi−1 ]
yi

We conclude that in both cases,
dG (v, ẑi (v))

≤

≤

(1 + ǫ)dG (v, Ai )
(1 + ǫ)dG (v, ẑi (u))

≤

(1 + ǫ)[dG (u, v) + dG (u, ẑi (u))]

≤

(1 + ǫ)[y0 + yi ]

(36)∧(37)

=

(38)

xi .

We now have a recurrence xi = (1 + ǫ)(2 + 10ǫ)y0 + (1 + ǫ)(1 + 10ǫ)xi−1 . Solving it, yields
xi = (1 + ǫ)(2 + 10ǫ)y0

i−1
X
[(1 + ǫ)(1 + 10ǫ)]j .
j=0

We use the fact that for any real x ≥ 0 and positive integer r such that xr ≤ 1/2, the following holds
(1 + x)r ≤ 1 + 2xr. Now we may bound xi by
xi ≤ (2 + 13ǫ)y0

i−1
X

(1 + 12ǫ)j

≤ (2 + 13ǫ)y0

i−1
X

(1 + 24ǫj)

(39)

j=0

j=0

≤ (2 + 13ǫ)y0 (i + 12ǫi2 )

≤ (2 + 13ǫ)y0 (i + 1/(4k2 )) ,

where in the last inequality we use that ǫ =
the stretch is given by

1
48k 4

≤

1
.
48k 2 i2

Finally, using that i′ ≤ k −1 and that w = ẑi′ (v),

dC̃(w) (u, w) + dC̃(w) (w, v)
(10)

≤

(1 + ǫ)4 [dG (u, w) + dG (v, w)]

≤

(1 + 5ǫ)[dG (u, v) + 2xi′ ]

≤

(1 + 5ǫ)[1 + (4 + 26ǫ)(k − 1 + 1/(4k 2 ))] · dG (u, v)

(35)
(39)

≤

(4k − 3 + o(1)) · dG (u, v) .
20

In order to improve the stretch to the promised 4k − 5 + o(1), we use same trick as in [TZ01]. Each
vertex u ∈ A0 \ A1 will store in its routing table all the labels for vertices in C(u), which enables to save an
additive term of dG (u, v) in both xi and yi . We refer the reader to [TZ01] for the details.
Running time. By Theorem 4, the time required to compute
the approximate pivots and the trees C̃(u) for
√
1/2+1/k
O(k)
Õ(
log
n) }, when k is even, and (n1/2+1/(2k) +D)·
every u ∈ Ai \Ai+1 is√(n
+D)·min{(log n)
,2
min{(log n)O(k) , 2Õ( log n) }, when k is odd. By Claim 2, each vertex participates in at most Õ(n1/k ) trees.
Hence, by Remark 3, which will be stated and proven in Section 6, it will take only Õ(n1/2+1/(2k) + D)
rounds to compute the routing tables √
for all trees in parallel. We conclude that the total number of rounds
is
√
1/2+1/k
O(k)
Õ(
log
n)
1/2+1/(2k)
O(k)
Õ(
log
n)
(n
+D)·min{(log n)
,2
}, for even k, and (n
+D)·min{(log n)
,2
},
for odd.

5 Distance Estimation
In this section we sketch how the routing tables can be used for distance estimation, and prove the following.
Theorem 6. Let G = (V, E) be a weighted graph with n vertices and hop-diameter D, and let k ≥ 1 be a
parameter. Then there exists a distance estimation scheme, that assigns a sketch of size O(n1/k log n) for
each node, and has stretch 2k−1+o(1),√that can be computed by a randomized distributed algorithm within
(n1/2+1/k + D) · min{(log n)O(k) , 2Õ( log n) } rounds √(whp). In the case of odd k, the running time can be
decreased to (n1/2+1/(2k) + D) · min{(log n)O(k) , 2Õ( log n) }. Furthermore, the distance computation can
be done in time O(k).
Apply Theorem 4, which computes all the approximate pivots and approximate clusters. Each vertex
v ∈ V include in its sketch for every u ∈ V so that v ∈ C̃(u), the pair (u, bv (u)), where bv (u) is the
approximate distance to u computed in Section 3. Also for every 0 ≤ i ≤ k − 1, add (ẑi (v), dˆi (v)), which
is the approximate i-pivot and distance to it. By Remark 2, every sketch is of size O(n1/k log n). The
algorithm that computes a distance estimate given two sketches is similar to that of [TZ05]. We state it
formally in Algorithm 2.
Algorithm 2 Dist(u, v)
1: i ← 0;
2: w ← u;
3: while v ∈
/ C̃(w) do
4:
i ← i + 1;
5:
(u, v) ← (v, u);
6:
w ← ẑi (u);
7: end while
8: return dˆi (u) + bv (w);
Observe that the sketch contains all the relevant information for executing Algorithm 2. When the while
loop terminates v ∈ C̃(w), so it has the estimate bv (w), while u stores the approximate distance dˆi (u)
to every one of its approximate pivots. The stretch analysis is a variant of the analysis of [TZ05], similar
in spirit to that of Section 4. Roughly speaking, on the stretch 2k − 1 achieved by [TZ05], we pay a
21

multiplicative factor of (1 + O(ǫ))k due to the fact that distances are approximated. However, this boils
1
down to an o(1) additive term, since ǫ = 48k
4 . We leave the details to the reader.

6 Distributed Tree Routing
In this section we present a modification of the (exact) routing scheme of Thorup-Zwick for rooted trees,
that can be implemented efficiently in a distributed manner. The price is that the size of the labels and tables
increases by a factor of log n, compared to what [TZ01] achieved.
Theorem 7. Fix a graph G = (V, E) on n vertices with hop-diameter D. For any tree T which is a
subgraph of G, there is a routing scheme with stretch 1, routing tables of size O(log n) and labels of size
√
O(log2 n), that can be computed in a distributed manner within Õ( n + D) rounds.
Remark 3. If we are given n trees, each a sub-graph of G = (V, E), so that each vertex v ∈ V participates
√
in at most s trees, then routing schemes for all the trees can be computed in Õ( n · s + D) rounds.
Let us first recall briefly how (a simplified version of) the TZ scheme works. For every non-leaf vertex,
define a heavy child as the child with the largest subtree. Run a Depth First Search (DFS) on the tree, each
vertex u receives an entry time au and exit time bu . The routing table stored at each vertex u consists of the
name and port number of its parent p(u) in the tree, the name (and port) of its heavy child h(u), and the
numbers au , bu . The label of a vertex u contains the number au and additional ⌈log n⌉ words: consider the
path P from the root to u, for every vertex w on this path such that its heavy child is not on P , we append
to the label of u the name of w and the port number leading from w to its child on P . The observation is
that whenever the path does not use the heavy child, the size of the subtree shrinks by a factor of at least 2,
so this can happen only ⌈log n⌉ times. In order to route from u to v, every intermediate vertex x does as
follows: if ax = av we are done, if av ∈
/ (ax , bx ), we know the DFS did not find v in the subtree rooted at
x, so x sends the message to its parent, and if av ∈ (ax , bx ) then v lies in the subtree of x. In the latter case,
x examines the label of v for an entry of the form (x, x′ ), if it exists it sends to its child x′ , if not, x sends
the message to its heavy child.
In order to obtain a scheme that runs efficiently in a distributed manner, we cannot compute heavy
children and run DFS on the entire tree. Instead, we shall apply certain variants of the TZ-scheme in two
levels. Let T be a tree on the vertices V (T ) ⊆ V , rooted at z. For u ∈ V (T ), denote by p(u) the parent
of u in T . We assume that every vertex knows the names of its parent and its children. The basic idea is to
randomly sample γ ≥ c · ln n, for a sufficiently large constant c, vertices U ⊆ V . (γ here is a parameter.)
Each vertex in V chooses itself to U independently with probability nγ . Partition the tree T into subtrees
according to the vertices of U (T ) = (U ∩ V (T )) ∪ {z}, by removing each edge from a vertex of U (T ) to
its parent. Note that this partitions T into a forest F of |U (T )| subtrees, each of these subtrees is rooted at
a vertex of U (T ). For w ∈ U (T ), denote by Tw the subtree in F rooted in w. Let T ′ denote the virtual tree
on the vertices of U (T ), where w is a parent of u in T ′ , if p(u) lies in Tw . We shall devise a routing scheme
for each Tw , and a global scheme that routes in T ′ . We begin by bounding the depth of each subtree; let
B = 4n
γ · ln n.
Claim 8. With high probability, |U | = O(γ), and for each w ∈ U (T ), the tree Tw has depth at most B.
Proof. The first event holds with high probability by a simple Chernoff bound. For the second: by independence, the probability that a path P in T of length B has P ∩ U = ∅, is

1
γ 4n/γ ln n
≤ 4 .
1−
n
n
22

Taking a union bound on the O(n2 ) possible paths (in a tree, choosing the path’s endpoints determines it)
completes the proof.
Remark: Observe that we still have high probability that the events of Claim 8 hold over n different trees
of the Thorup-Zwick cover.
From now on assume the events of Claim 8 hold. The assignment has two phases.
Phase 1. In the first phase we compute a routing scheme for each Tw in the forest F , in parallel. In each
round, every vertex u that received messages from all its children, sends to its parent in F the size of its
subtree (by summing up the sizes of the subtrees of the children of u). By Claim 8, the depth of each tree in
F is at most B, and in each round we send one word per vertex. Hence after B rounds every vertex knows
the size of its subtree (in F ), and in particular, can infer who is its heavy child. Now each w ∈ U (T ) can
start a parallel DFS of Tw – that is, every vertex assigns entry and exit times to all if its children in parallel
(it is possible since it knows the sizes of every child’s subtree). Each vertex in Tw adds to its routing table
(p(x), h(x), ax , bx , w), which are the name of the parent of x, the heavy child of x, the entry and exit times,
and the name w. This computation (parallel DFS) will also require O(B) rounds, since all subtrees work in
parallel.
The (local) label assignment for vertices in Tw is done in the following manner. Starting from w (which
has empty label), every vertex x that receives a label ℓ from its parent, and has children x1 , . . . , xl , sends ℓ
to its heavy child, and ℓ ◦ (x, xi ) to xi for each non-heavy child xi . The label ℓ(x) will consist of ax and the
list ℓ of edges that was given to x.
Phase 2. In the second phase we compute a routing scheme on T ′ . Every u ∈ U (T ) sends a message
to its parent x in T , and receives from x the following message: ℓ(x), the name w such that x ∈ Tw (so
that the edge (w, u) should be in T ′ ), and also the port number e(x, u) of x leading to u. Then every such
u broadcasts ((w, u), x, ℓ(x), e(x, u)) to the entire graph. Once the root vertex z has full information on
T ′ , it may locally compute the TZ routing scheme for T ′ . The routing table given to u ∈ U (T ) is slightly
different than in the usual scheme, as it will contain local routing information for the vertex leading to the
heavy child. More formally, the table will be (h′ (u), ℓ(y), e(y, h′ (u)), a′u , b′u ). Here h′ (u) is the name of
heavy child of u in T ′ , y ∈ Tu is the portal vertex which is the parent of h′ (u) in T , and e(y, h′ (u)) is the
port of y leading to h′ (u). Note that z has the name, label and the appropriate port of y when h′ (u) reported
the edge (u, h′ (u)). Finally a′u , b′u are the entry and exit times of the DFS run by z on T ′ . Observe that ℓ(y)
has size O(log n), and this term dominates the size of a routing table. There are at most O(γ) such tables.
Hence Lemma 1 implies that we can broadcast to the entire graph all these messages within O(γ log n + D)
rounds. In addition, every vertex u ∈ U (T ) sends the routing table given to it to all the vertices in Tu . Since
we can send the information inside each subtree in parallel, it will take only O(B log n) rounds.
The label assignment to the vertices of T ′ is also modified, since for every possible edge taken in T ′
which is not leading to a heavy child, we must add the local routing information. Fix u ∈ U (T ). Assume
((v1 , w1 ), . . . , (vl , wl )) is the list of all edges in the path of T ′ from z to u, so that each wi is a non-heavy
child of vi . Ordinarily, this list would have been the label of u (along with a′u ). However, in order to be able
to route in T ′ , we replace each such edge with (vi , wi , ℓ(xi ), e(xi , wi )), where xi is the parent of wi in T ,
ℓ(xi ) is the label xi received in the first phase (for local routing within Tvi ), and e(xi , wi ) is the port leading
from xi to wi . Recall that z knows the label and appropriate port of every such xi . Since each ℓ(xi ) has size
at most O(log n) words, and l ≤ log n, we have that the label size is O(log2 n). As before, each u ∈ U (T )
propagates this label ℓ′ (u) to every vertex in Tu . The number of rounds is therefore O(γ log2 n + D).

23

Protocol. The routing from u to v will be done as follows. Assume we have arrived to an intermediate
vertex x that lies in Tw . First x checks if routing in T ′ is required, by comparing a′v with a′x , b′x (recall that
a′v is part of the label of v, and the routing table of x contains a′x = a′w and b′x = b′w ). If a′v = a′x then
/ (a′x , b′x ), we need to route to the subtree rooted at the
v ∈ Tw , and we proceed to route inside Tw . If a′v ∈
parent of w in T ′ , and if a′v ∈ (a′x , b′x ) then we need to route to the appropriate child of w in T ′ ,
Routing inside Tw : This is done exactly as in the TZ scheme, while considering the local routing tables
of vertices in Tw and ℓ(v). If ax = av we are done. If av ∈
/ (ax , bx ) we route to the parent of x (stored
in the local routing table of x), and when av ∈ (ax , bx ), we inspect ℓ(v): if it contains an edge of the form
(x, x′ ), for some x′ , we route to x′ . Otherwise to the heavy child of x (the heavy child’s name is also in the
local routing table of x).
Routing to the parent of w in T ′ : This is simple, x just routes to its parent, its name is stored in the
local routing table of x. Eventually we will reach w (since all vertices in Tw have the same ℓ′ label), and
route from it to vertex in the tree of w’s parent in T ′ .
Routing to a child of w in T ′ : Here we inspect ℓ′ (v), if it contains an entry of the form (w, w′ , ℓ(y), e(y, w′ ))
then we know we have to route in T ′ from w to its child w′ in T ′ . Fortunately, the label ℓ(y) provides us the
required routing information to route in Tw to the portal vertex y (that has w′ as a child in T ). From y we
go to its child w′ using the port e(y, w′ ). If the label ℓ′ (v) contains no such entry, then we know we need
to route to the heavy child of w in T ′ . Here the label of v is useless, but we stored the label of y ′ ∈ Tw ,
the portal vertex which is the parent of this heavy child, in the routing table of each vertex of Tw . Using the
label of y ′ we can route locally in Tw , and from y ′ route to h′ (w) (using the port number for heavy child
stored in the routing table).
When constructing routing tables and labels for one single tree, the overall running time is O(γ ·log2 n+
√
√
D) + O(B · log n) = O(γ · log2 n + nγ · log2 n + D), i.e., O(D + n · log2 n), by setting γ = n.
Proof of Remark 3. To avoid high running time, we shall perform the routing tables and labels computations
in parallel in all cluster trees, while appending to each message the name of the relevant tree. In the first
√
phase, which can be implemented in Õ( n) rounds for each tree, we send information on the graph edges
(every vertex notifies all its neighbors in each round), so the overhead due to participation in up to s trees
is only a factor of s. In the second phase, however, we broadcast messages to the entire graph. So we need
a bound on the number of these messages. For each tree T ′ (which consists of the vertices of U alone) we
broadcast 2 messages per vertex: the first informing the root of its existence, its parent, and the local routing
information. In the second message, the root broadcasts routing information and a label for the vertex. Each
message is of size O(log2 n). By charging these messages to the vertices of U , each such vertex pays for 2
messages per tree containing it. But the number of these trees is at most s, so we need to broadcast at most
√
√
Õ( n · s) words. By Lemma 1, these can be broadcast to the entire graph in Õ( n · s + D) rounds.
√
We next argue that this bound can be further improved to Õ( n · s + D).
Every root w of a tree Tw in one of the forests F (each cluster tree gives rise to one such a forest) tosses
√
a starting time start(w) uniformly at random from the interval [1, c · ln n · ns], for a sufficiently large
constant c. It then starts broadcasting to vertices of Tw at time 20 · start(w). (It broadcasts to them the value
start(w).) Each round of this broadcast is replaced by stages consisting of 20 rounds each. Specifically,
a vertex x in Tw that already received the message from its parent tries to deliver it to its children for 20
consecutive rounds. We will show that, whp, for every edge, on one of these rounds no congestion will be
experienced. Only when these 20 rounds are over, the children of x will start broadcasting.
Consider a specific edge e = (x, y) in a tree Tw . Let w1 , w2 , . . . , ws be the roots of trees Twi that
contain this edge. (Recall that, by Claim 2, whp, s = O(n1/k · log n).) Let t1 , t2 , . . . , ts be the respective
hop-distances between wi and the closer endpoint of ei to wi . In other words, for every i ∈ [s], if wi
24

broadcasted a message over Twi , and no other messages would have interfered with its broadcast, then the
broadcast of wi would traverse ei on step ti . (For convenience, we number the steps starting from 0.)
For any index R, the probability that the broadcast of wi will want to traverse e on stage R, conditioned
on the assumption that it experienced no congestion whatsoever before that, is the probability that wi starts
broadcasting at stage R − ti , i.e., this is equal to IP(start(wi ) = R − ti ). The latter probability is at most
√ 1
. For a positive integer α ≤ s, the probability that α cluster trees wish to employ e on stage R,
c ns ln n
conditioned on the assumption that no congestion was experienced by any of them so far, is at most
α


α  
α

s
1
s
1
√
√
.
·
≤
≤
α
c ln n · ns
c ln n · ns
n1/2−1/(2k)
1
For α = 20, this probability is at most n10−10/k
≤ n15 . By union-bound over all stage indices R ≤ n, and
all the |E| ≤ n2 edges, we still have an only negligible probability that a congestion was ever experienced
throughout the algorithm. (Here we say that a congestion is experienced if a vertex v wishes to broadcast a
message m on a stage R of the algorithm through an edge (v, u) incident on v, and v cannot do it for the
entire α = 20 rounds of this stage, because of other transmissions that employ the same edge.)
√
Hence, whp, in O(B · α) + O( ns ln n) = Õ(B + n1/2+1/(2k) ln n) rounds, all broadcasts of the values
of starting times will be completed. (Recall that B is an upper bound on the depth of trees Twi .) This
completes Phase 0 of the algorithm.
Now the algorithm proceeds to Phase 1, on which convergecasts are conducted in all these trees. As a
result of these convergecasts, every vertex x ∈ Twi knows the size of its subtree in Twi . These convergecasts are conducted by a similar procedure to the one that was described above, i.e., all leaves of Twi start
broadcasting at stage start(wi ), and each stage lasts for α = 20 rounds. Hence these convergecasts are
√
also completed in O(B + ns · ln n) rounds. Then the “parallel DFSs” are conducted in all the trees in
parallel by the same procedure of tree broadcast. As a result, all vertices x in these trees Twi learn their
√
routing tables within Twi . They also learn their routing labels within additional O(B log n + ns log2 n)
time. (Note that for labels one may need to send messages of size O(log n) words, and so stages of length
O(α · log n) = O(log n) are needed.)
Phase 2 is performed in the same way as was already described. Specifically, the algorithm conducts
convergecasts of messages (ℓ(x), w, e(x, u)), where u ∈ U (T ) and x is its parent in T , for some cluster
tree T , over the BFS tree τ of the entire graph G. Since every selected vertex u may participate in up to s
trees, and there are O(γ) selected vertices, this convergecast requires O(γ · s + D) time. Analogously, the
broadcast of the computed routing tables requires O(γ · s log n + D) time.
Then each u ∈ U (T ) sends its routing table to all vertices of Tu . This is done using the tossed starting
√
times and with stages of α rounds each, as in Phase 1. Hence this step requires O(B log n + ns log2 n)
time. Finally, the labels of selected nodes in T ′ are broadcasted over the BFS tree τ within additional
O(γ · s · log2 n + D) time.
√
To summarize, the overall running time of the algorithm is Õ(B + D + ns + γ · s) = Õ( nγ + D +
p
√
1/2−1/(2k)
n1/2+1/(2k) + γ · s). By setting γ = n/s = n √log n , we get the running time of Õ( ns + D) =

Õ(n1/2+1/(2k) + D).

25

References
[ABLP90] Baruch Awerbuch, Amotz Bar-Noy, Nathan Linial, and David Peleg. Improved routing strategies with succinct tables. J. Algorithms, 11(3):307–341, 1990.
[AGM04] Ittai Abraham, Cyril Gavoille, and Dahlia Malkhi. Routing with improved communication-space
trade-off. In Distributed Computing, 18th International Conference, DISC 2004, Amsterdam,
The Netherlands, October 4-7, 2004, Proceedings, pages 305–319, 2004.
[Ber09]

Aaron Bernstein. Fully dynamic (2 + epsilon) approximate all-pairs shortest paths with fast
query and close to linear update time. In 50th Annual IEEE Symposium on Foundations of
Computer Science, FOCS 2009, October 25-27, 2009, Atlanta, Georgia, USA, pages 693–702,
2009.

[Che13]

Shiri Chechik. Compact routing schemes with improved stretch. In ACM Symposium on Principles of Distributed Computing, PODC ’13, Montreal, QC, Canada, July 22-24, 2013, pages
33–41, 2013.

[Coh00]

Edith Cohen. Polylog-time and near-linear work approximation scheme for undirected shortest
paths. J. ACM, 47(1):132–166, 2000.

[Cow01]

Lenore Cowen. Compact routing with minimum stretch. J. Algorithms, 38(1):170–183, 2001.

[EGP03]

Tamar Eilam, Cyril Gavoille, and David Peleg. Compact routing schemes with low stretch
factor. J. Algorithms, 46(2):97–114, 2003.

[Elk06a]

Michael Elkin. A faster distributed protocol for constructing a minimum spanning tree. J.
Comput. Syst. Sci., 72(8):1282–1308, 2006.

[Elk06b]

Michael Elkin. An unconditional lower bound on the time-approximation trade-off for the distributed minimum spanning tree problem. SIAM J. Comput., 36(2):433–456, 2006.

[EN16a]

Michael Elkin and Ofer Neiman. Hopsets with constant hopbound, and applications to approximate shortest paths. In 57th IEEE Annual Symposium on Foundations of Computer Science,
FOCS, 2016.

[EN16b]

Michael Elkin and Ofer Neiman. On efficient distributed construction of near optimal routing
schemes: Extended abstract. In Proceedings of the 2016 ACM Symposium on Principles of
Distributed Computing, PODC 2016, Chicago, IL, USA, July 25-28, 2016, pages 235–244,
2016.

[GK13]

Mohsen Ghaffari and Fabian Kuhn. Distributed minimum cut approximation. In Distributed
Computing - 27th International Symposium, DISC 2013, Jerusalem, Israel, October 14-18,
2013. Proceedings, pages 1–15, 2013.

[GKP98]

Juan A. Garay, Shay Kutten, and David Peleg. A sublinear time distributed algorithm for
minimum-weight spanning trees. SIAM J. Comput., 27(1):302–316, 1998.

[GP03]

Cyril Gavoille and David Peleg. Compact and localized distributed data structures. Distributed
Computing, 16(2-3):111–120, 2003.
26

[HKN14] Monika Henzinger, Sebastian Krinninger, and Danupon Nanongkai. Decremental single-source
shortest paths on undirected graphs in near-linear total update time. In 55th IEEE Annual Symposium on Foundations of Computer Science, FOCS 2014, Philadelphia, PA, USA, October
18-21, 2014, pages 146–155, 2014.
[HKN16] Monika Henzinger, Sebastian Krinninger, and Danupon Nanongkai. A deterministic almosttight distributed algorithm for approximating single-source shortest paths. In Proceedings of the
48th Annual ACM SIGACT Symposium on Theory of Computing, STOC 2016, Cambridge, MA,
USA, June 18-21, 2016, pages 489–498, 2016.
[IW14]

Taisuke Izumi and Roger Wattenhofer. Time lower bounds for distributed distance oracles.
In Principles of Distributed Systems - 18th International Conference, OPODIS 2014, Cortina
d’Ampezzo, Italy, December 16-19, 2014. Proceedings, pages 60–75, 2014.

[KP98]

Shay Kutten and David Peleg. Fast distributed construction of small k-dominating sets and
applications. J. Algorithms, 28(1):40–66, 1998.

[LP13a]

Christoph Lenzen and Boaz Patt-Shamir. Fast routing table construction using small messages.
In Symposium on Theory of Computing Conference, STOC’13, Palo Alto, CA, USA, June 1-4,
2013, pages 381–390, 2013.

[LP13b]

Christoph Lenzen and David Peleg. Efficient distributed source detection with limited bandwidth. In ACM Symposium on Principles of Distributed Computing, PODC ’13, Montreal, QC,
Canada, July 22-24, 2013, pages 375–382, 2013.

[LP15]

Christoph Lenzen and Boaz Patt-Shamir. Fast partial distance estimation and applications. In
Proceedings of the 2015 ACM Symposium on Principles of Distributed Computing, PODC 2015,
Donostia-San Sebastián, Spain, July 21 - 23, 2015, pages 153–162, 2015.

[LP16]

Christoph Lenzen and Boaz Patt-Shamir. Personal communication, 2016.

[LPP16]

Christoph Lenzen, Boaz Patt-Shamir, and David Peleg. Distributed distance computation and
routing with small messages. 2016.

[Nan14]

Danupon Nanongkai. Distributed approximation algorithms for weighted shortest paths. In
Symposium on Theory of Computing, STOC 2014, New York, NY, USA, May 31 - June 03, 2014,
pages 565–573, 2014.

[NRS12]

Nicolas Nisse, Ivan Rapaport, and Karol Suchan. Distributed computing of efficient routing
schemes in generalized chordal graphs. Theor. Comput. Sci., 444:17–27, 2012.

[Pel00a]

David Peleg. Distributed Computing: A Locality-sensitive Approach. Society for Industrial and
Applied Mathematics, Philadelphia, PA, USA, 2000.

[Pel00b]

David Peleg. Proximity-preserving labeling schemes. J. Graph Theory, 33(3):167–176, March
2000.

[PR00]

David Peleg and Vitaly Rubinovich. A near-tight lower bound on the time complexity of
distributed minimum-weight spanning tree construction. SIAM J. Comput., 30(5):1427–1442,
2000.
27

[PU89]

David Peleg and Eli Upfal. A trade-off between space and efficiency for routing tables. J. ACM,
36(3):510–530, 1989.

[SDP15]

Atish Das Sarma, Michael Dinitz, and Gopal Pandurangan. Efficient distributed computation of
distance sketches in networks. Distributed Computing, 28(5):309–320, 2015.

[SHK+ 12] Atish Das Sarma, Stephan Holzer, Liah Kor, Amos Korman, Danupon Nanongkai, Gopal Pandurangan, David Peleg, and Roger Wattenhofer. Distributed verification and hardness of distributed approximation. SIAM J. Comput., 41(5):1235–1265, 2012.
[TZ01]

Mikkel Thorup and Uri Zwick. Compact routing schemes. In Proceedings of the Thirteenth
Annual ACM Symposium on Parallel Algorithms and Architectures, SPAA ’01, pages 1–10,
New York, NY, USA, 2001. ACM.

[TZ05]

Mikkel Thorup and Uri Zwick. Approximate distance oracles. J. ACM, 52(1):1–24, 2005.

A

Proof of Theorem 3

√
Let X ⊆ V be a set of vertices so that each v ∈ V is sampled to X independently with probability 1/ n.
√
Define V ′ = A ∪ X, and note that with high probability B = 4 n ln n ≥ |V ′ | (since it is given that
√
|A| ≤ 2 n ln n). Apply the same preprocessing steps as in Section 3.3.1 with V ′ as defined here, to obtain
a graph G′′ on V ′ satisfying (13).
ˆ
Computing Approximate SPT for V ′ . The first step is to compute the values (d(v),
ẑ(v)) for vertices
′
v ∈ V . √Every vertex in v ∈ A initializes its values as (0, v), while v ∈
/ A sets (∞, ⊥). Conduct β =
min{2Õ( log n) , (log n)O(k) } iterations of Bellman-Ford rooted at A: at every iteration, every vertex v ∈ V ′
ˆ
ˆ < d(u),
ˆ
broadcasts its pair (d(v),
ẑ(v)) to the entire graph, and if u ∈ V ′ has w′′ (u, v)+ d(v)
then u updates
′′
′′
′′
ˆ
its pair to be (w (u, v) + d(v), ẑ(v)). (Recall that w is the edge weight function of G , where the latter is
the virtual graph given by Theorem 1 augmented with the hopset edges of Theorem√ 2.)
The number of rounds required to construct G′′ is (n1/2+1/(2k) + D) · min{2Õ( log n) , (log n)O(k) }, and
by Lemma 1 this term also bounds the number of rounds it takes to broadcast the O(|V ′ | · β) messages for
the Bellman-Ford iterations.
Extending the SPT to V . At the end of the β iterations of Bellman-Ford, every vertex u ∈ V knows
ˆ
(d(v),
ẑ(v)) for every v ∈ V ′ . Every vertex u ∈ V computes
ˆ = min {duv + d(v)}
ˆ
d(u)
,
′
v∈V

(40)

and sets ẑ(u) = ẑ(v), where v ∈ V ′ is the minimizer of (40). (Recall that duv is the value computed in
Theorem 1.)
Analysis. We assume all the events of Claim 3 hold (which happens with high probability). For u ∈ V
let zu ∈ A be a vertex satisfying dG (u, zu ) = dG (u, A). Since we performed β iterations of Bellman-Ford,
using (13) with v ∈ V ′ and zv ∈ A ⊆ V ′ we have that v ′ satisfies (5).

28

Consider now some u ∈ V , and let v ∈ V ′ be the minimizer in (40). The left hand side of (5) holds, as
the fact that v ∈ V ′ satisfies (5) implies
(2)

(B)

ˆ ≥ d (u, v) + dG (v, A) ≥ dG (u, v) + dG (v, A) ≥ d(u, A) .
duv + d(v)
G
For the right hand side of (5): In the case that h(u, zu ) ≤ B, by (2) we get that
ˆ ≤ duz + d(z
ˆ u ) ≤ (1 + ǫ)d(B) (u, zu ) + 0 = (1 + ǫ)dG (u, zu ) .
d(u)
u
G
Otherwise h(u, zu ) > B, and by Claim 3 there exists v ∈ X ⊆ V ′ on the shortest path in G from u to zu
with h(u, v) ≤ B. Since (5) holds for v,
ˆ
ˆ
d(u)
≤ duv + d(v)
(2)

(B)

≤ (1 + ǫ)dG (u, v) + (1 + ǫ)dG (v, A)
≤ (1 + ǫ)dG (u, v) + (1 + ǫ)dG (v, zu )

= (1 + ǫ)dG (u, zu ) .

29

