Round- and Message-Optimal Distributed Graph Algorithms
Bernhard Haeupler∗ , D. Ellis Hershkowitz∗ , David Wajc∗

arXiv:1801.05127v2 [cs.DC] 27 Feb 2018

Carnegie Mellon University, {haeupler,dhershko,dwajc}@cs.cmu.edu

Abstract

Distributed graph algorithms that separately optimize for either the number of
rounds used or the total number of messages sent have been studied extensively. However, algorithms simultaneously efficient with respect to both measures have been elusive. For example, only very recently was it shown that for Minimum Spanning Tree
(MST), an optimal message and round complexity is achievable (up to polylog terms)
by a single algorithm in the CONGEST model of communication.
In this paper we provide algorithms that are simultaneously round- and messageoptimal for a number of well-studied distributed optimization problems. Our main
result is such a distributed algorithm for the fundamental primitive of computing simple
functions over each part of a graph partition. From this algorithm we derive round- and
message-optimal algorithms for multiple problems, including MST, Approximate MinCut and Approximate Single Source Shortest Paths, among others. On general graphs
√
all of our algorithms achieve worst-case optimal Õ(D + n) round complexity and Õ(m)
message complexity. Furthermore, our algorithms require an optimal Õ(D) rounds and
Õ(n) messages on planar, genus-bounded, treewidth-bounded and pathwidth-bounded
graphs.1

∗

Supported in part by NSF grants CCF-1527110, CCF-1618280 and NSF CAREER award CCF-1750808.
Throughout this paper, n, m and D denote respectively the number of nodes, number of edges and the graph
diameter respectively. In addition, we use tilde notation, Õ, Ω̃ and Θ̃, to suppress polylogarithmic terms in n.
1

1

Introduction

Over the years, a great deal of research has focused on characterizing the optimal runtime for
distributed graph algorithms in the CONGEST model of communication. Fundamental problems
studied include Shortest Paths [10, 22, 23, 27, 28, 31], MST [13, 24, 25, 36], Min-Cut [16, 32], and
Max Flow [17]. Runtime is measured by the number of synchronous rounds of communication, and
√
for these problems Θ̃(D + n) rounds are known to be necessary and sufficient [5, 7, 16, 36].
Another common performance metric optimized for in the CONGEST model is the total number of messages sent. For MST, an Ω̃(m) lower bound is known [2].1 However, for several decades
the only MST algorithms known to match this message lower bound had sub-optimal round complexity [1, 2, 3, 9, 11, 12]. The question of whether algorithms attaining both optimal round and
message complexity has been a long-standing problem. For instance, Peleg and Rubinovich [36]
asked whether it might be achievable for MST. In a recent breakthrough work Pandurangan et al.
[34] answered this question in the affirmative, providing a randomized MST algorithm with simulataneously optimal round and message complexities (up to polylog terms). Shortly thereafter Elkin
[8] provided the same result without randomization. However, algorithms which are simultaneously
round- and message-optimal for other fundamental problems have remained elusive.

1.1

Our Main Result

In this paper we advance the study of simultaneously round- and message-optimal distributed
algorithms. In particular, we provide such algorithms for multiple distributed graph problems.
Underlying these contributions is our main result – a round- and message-optimal algorithm for a
fundamental distributed problem, which we refer to as Part-Wise Aggregation (or PA for short).
We elaborate on some such applications of this algorithm in Section 1.2, as well as Appendix A.
Informally, Part-Wise Aggregation is the problem of computing the result of a function applied to
each part of a graph partition. Formally, the problem is as follows.
Definition 1.1 (Part-Wise Aggregation). The input to the Part-Wise Aggregation (PA) problem
consists of a graph G = (V, E), a partition (Pi )N
i=1 of V , where each G[Pi ] is connected, and a
commutative binary operator f . Each node v ∈ Pi knows a value associated with it and which of its
neighbors are in Pi . The problem is solved if for every Pi every v ∈ Pi knows its part’s aggregate
value f (Pi ) = f (v1 , f (v2 , . . . )), where Pi = {v1 , v2 , . . . }.2
The performance of our algorithm is determined by the quality of the shortcuts that the input
graph admits. Shortcuts, as well as the parameters which determine their quality – termed the
block parameter, b, and congestion, c – are formally defined in Section 2. For now, we note only
√
that every graph admits a shortcut with b = 1 and c = n. Our main result is as follows.
Theorem 1.2. There exists a Part-Wise Aggregation on a graph G admitting a tree-restricted
shortcut with congestion c and block parameter b w.h.p.3 in Õ(bD + c) rounds and Õ(m) messages,
and deterministically in Õ(b(D + c)) rounds and Õ(m) messages.
1

Strictly speaking, the Ω̃(m) message lower bound for MST only holds if the algorithm is (1) deterministic (2) in
the KT0 model, or (3) “comparison-based". (Our deterministic algorithm satisfies (1),(2) and (3).) If these conditions
are not met it is possible to solve MST using Õ(n) messages – beating the Ω̃(m) bound for sufficiently dense graphs.
For more see Mashreghi and King [29].
2
Throughout this paper, f will have O(log n)-bit output, transmittable in one round of CONGEST communication.
3
1
Throughout the paper, by w.h.p. we mean with probability poly(n)
.

1

1.2

Applications of Our Main Result

The power of Part-Wise Aggregation – and by extension Theorem 1.2 – is that numerous distributed
primitives can be cast as instances of this problem. For example, it is not hard to see that electing
a leader, computing the number of nodes in each tree in a forest or having every part of a graph
partition agree on a minimum value are all instances of this problem. Consequently, many previous
algorithms rely on subroutines which are implementable using Part-Wise Aggregation [5, 6, 12, 13,
14, 15, 16, 17, 18, 25, 32]. Perhaps unsurprisingly then, using our new PA algorithm as a subroutine
in some of these previous works’ algorithms, we obtain round- and message-optimal solutions to
numerous problems.
In the following three corollaries we highlight three such applications of our algorithm: roundand message-optimal algorithms for MST, Approximate Min-Cut and Approximate SSSP. In Appendix A we discuss more applications of our PA algorithm to optimization and verification problems, and outline proofs of the following three corollaries for completeness. For a flavor of these
corollaries’ proofs, we note that Borůvka’s MST algorithm [33] can be implemented easily using
O(log n) applications of Part-Wise Aggregation, implying Corollary 1.3. Corollaries 1.4 and 1.5 are
obtained by using our PA algorithm in the algorithms of [15] and [18], respectively.
Corollary 1.3. Given a graph G admitting a tree-restricted shortcut with congestion c and block
parameter b, one can solve MST w.h.p in Õ(bD+c) rounds and Õ(m) messages and deterministically
in Õ(b(D + c)) rounds with Õ(m) messages.
Corollary 1.4. For any  > 0 and graph G admitting a tree-restricted shortcut with congestion c
and block parameter b, one can (1 + )-approximate min-cut w.h.p. in Õ (bD + c) · poly(1/) rounds
and Õ (m) · poly(1/) messages.
Corollary 1.5. For any β = O(1/poly log n), given a graph G admitting a tree-restricted shortcut
with
b, one can LO(log log n)/ log(1/β) -approximate SSSP w.h.p in
 congestion
 c and block parameter
 
Õ β1 (bD + c) rounds and Õ m
messages.
β
The value of β determines a tradeoff between the quality of the SSSP approximation and the
round and message complexity of our algorithm. Taking β = log−Θ(1/) n, Corollary 1.5 yields an
e we
O(L )-approximation algorithm (for L = max
mine we ) using Õ(bD + c) rounds and Õ(m) messages.

1.3

Discussion of Our Results

There are a few salient points worth noting regarding our results, on which we elaborate below.
Round- and Message-Optimality of our Algorithms. As all graphs admit a tree-restricted
√
shortcut with block parameter b = 1 and congestion c = n, our algorithms all terminate within
√
Õ(D + n) rounds, which is optimal for all our applications of our PA algorithm, by [5]. As for
message complexity, our Õ(m) bound is tight for MST in the KT0 model by [2]. For the other
problems an Ω(n) message lower bound is trivial; for sparse graphs, then, our message complexity
bound is tight for these problems. Finally, we note that our proof of Corollary 1.3 relies on solving
Part-Wise Aggregation O(log n) times to solve MST, which implies that our algorithms for PA are
both round- and message-optimal (again, up to polylog terms).4
4

Alternatively, the Completeness Theorem of Awerbuch [1] (whose proof is unpublished) asserts that any message
or round lower bound for MST carries over unchanged to PA, implying our algorithm’s optimality.

2

Beyond Worst-Case Optimality. As stated above, every graph admits tree-restricted shortcuts
√
√
with block parameter b = 1 and congestion c = n, which implies an Õ(D + n) bound for our
algorithms’ round complexity on general graphs. However, as observed in prior work, a number
of graph families of interest – planar, genus-bounded, bounded-treewidth and bounded-pathwidth
graphs – admit shortcuts with better parameters [15, 19, 20]. As a result, our algorithms have
a round complexity of only Õ(D) times the relevant parameter of interest (e.g., genus, treewidth
or pathwidth). Provided these parameters are constant or even polylogarithmic, our algorithms
run in Õ(D) rounds. Another recent result [21] implies that our algorithms run in Õ(D2 ) time on
minor-free graphs. We elaborate on our results for all the above graphs in Appendix F. We also
note that our algorithms need not know the optimal values of block parameter and congestion,
as a simple doubling trick can be used approximate the best values (see [19]). In particular, our
algorithms perform as well as the parameters of the best shortcut that the input graph admits.
Future Applications of This Work. Non-trivial shortcuts likely exist for graph families beyond
those mentioned above. As such, demonstrating even better runtimes for our algorithms on many
networks may be achieved in the future by simply proving the existence of efficient shortcuts on said
networks. Moreover, given the pervasiveness of PA in distributed graph algorithms, the applications
of our PA algorithm we present are likely non-exhaustive. We are hopeful that our PA algorithm
will find applications in deriving round- and message-optimal bounds for even more problems.

2

Preliminaries

Before moving onto our formal results, we explicitly state the model of communication we consider
and then review relevant concepts from previous work in low-congestion shortcuts.
Throughout this paper we work in the classic CONGEST model of communication [35]. In
this model, the network is modeled as a graph G = (V, E) of diameter D with n = |V | nodes
and m = |E| edges. Communication is conducted over discrete, synchronous rounds. During each
round each node can send an O(log n)-bit message along each of its incident edges. Every node
has an arbitrary and unique ID of O(log n) bits, first only known to itself (this is the KT0 model
of Awerbuch et al. [2]).
Low-congestion shortcuts were originally introduced by Ghaffari and Haeupler [15] to solve PA.
These shortcuts allow high-diameter parts to communicate efficiently, by using edges outside of
parts; this effectively decreases the diameter of the parts. Ghaffari and Haeupler [15] showed how,
given a simple low-congestion shortcut, PA can be solved in an optimal number of rounds – i.e.
√
Õ(D + n) – w.h.p. Formally, a low congestion shortcut is as follows.
Definition 2.1 (Low-Congestion Shortcuts [15]). Let G = (V, E) be a graph and (Pi )N
i=1 be a
partition of G’s vertex set. A c-congestion shortcut with dilation d with respect to (Pi )N
,
i=1 H, is a
collection of sub-graphs of G, H1 , . . . , HN , satisfying
1. The diameter of G[Pi ] + Hi for any i is at most d.
2. Each e ∈ E occurs in at most c of the Hi .
However, it was not until the work of Haeupler, Izumi, and Zuzic [19] that it was demonstrated
that shortcuts could be efficiently computed in general. This work showed that high quality instances of a certain type of shortcut – tree-restricted shortcuts – can be efficiently approximated.
These types of shortcuts are defined as follows.
3

Definition 2.2 (Tree-Restricted Shortcuts [19]). Let G = (V, E) be a graph and (Pi )N
i=1 be a
N
partition of G’s vertex set. A shortcut H = (Hi )i=1 is a T -restricted shortcut with respect to
(Pi )N
i=1 if there exists a rooted spanning tree T of G with Hi ⊆ E[T ] for all i ∈ [N ].
Since a rooted BFS tree has minimal depth, and the Õ(D)-round Õ(m)-message deterministic
leader election algorithm of Kutten et al. [26] allows us to compute a BFS tree in the same bounds,
throughout this paper T will be a rooted BFS tree. The same work that introduced tree-restricted
shortcuts also introduced a convenient alternative to dilation, block parameter.
Definition 2.3 (Block Parameter [19]). Let H = (Hi )ni=1 be a T -restricted shortcut on the graph
G = (V, E) with respect to the parts (Pi )ni=1 . For any part Pi , we call the non-empty connected
components (V, Hi ) the blocks of Pi , and the number of blocks of Pi its block parameter. The block
parameter of H, b, is the maximum block parameter of any part Pi .
As shown in [19], if T is a depth-D tree, the dilation of a T -restricted shortcut with block
parameter b is at most O(bD). As such, block parameter is a convenient alternative to dilation.

3

Techniques

In this section we outline our general algorithmic approach. We begin by demonstrating the message
sub-optimality of previous shortcut algorithms for Part-Wise Aggregation on a particular example.
We then give a workaround for this example and sketch how we develop this workaround into a
full-fledged algorithm.

3.1

Bad Example for Previous Shortcut-Based Algorithms

Several prior round-optimal randomized algorithms for PA used tree-restricted shortcuts [19, 20].
To solve PA, these algorithms repeatedly aggregate within blocks. To aggregate within a block,
every node in the block transmits its value up the block (along the tree’s edges); when values from
the same part arrive at a node in the block, they are aggregated by applying f and then forwarded
up the block as a single value. By the end of this process, the root of the block has computed f
of the block and can broadcast the result back down. This approach can be implemented using an
√
optimal Õ(D + n) rounds.
Unfortunately, there exist PA instances for which the above approach requires ω(m) messages.
For example, consider the D × (n − 1)/D grid graph with an additional node, r, neighboring all
of the top row’s nodes. Suppose each row is its own part, and all the column edges are shortcut
edges, forming a single block rooted at r. See Figure 1a. Aggregating within this block requires
Ω(nD) messages: a message cannot be combined with other messages in its part until it has at least
reached r and so each node is responsible for sending a unique message to r along a path of length
D/2 on average. Thus, aggregating in blocks in this way to solve PA requires Ω(nD) messages,
which is sub-optimal for any D = ω(1), since m = O(n) for this network.
A Workaround. We can improve the poor message complexity of aggregating within blocks on
this particular network as follows. Partition each of the D parts into sub-parts, each with O(D)
connected nodes; we have O(n/D) sub-parts in total. See Figure 1b. First, sub-parts aggregate:
the right-most node in the sub-part broadcasts its value left and every other node broadcasts left
the aggregation of its own value and what it receives from its neighbor to the right. The leftmost
4

(b) A workaround.
Here sub-parts are indicated by (smaller)
dotted rectangles.

(a) Ω(nD) message example.
Parts are indicated by dashed rectangles.
Tree edges are directed towards the root.

Figure 1: A bad example for prior shortcut algorithms, and a workaround.
node of a sub-part then uses the block’s edges to transmit the sub-part’s aggregate value to r,
which then computes the aggregate value for each part. Symmetrically to the above procedure, r
then broadcasts to every node the aggregate value for its part.
Aggregating within each sub-part requires O(n) messages, as it requires each node to broadcast
at most once. Moreover, there are O(n/D) sub-parts, each responsible for broadcasting up and
down the block once and so using the shortcut requires O(n/D)·O(D) = O(n) messages. Therefore,
for this network, our workaround requires an optimal O(m) = O(n) messages.

3.2

Overview of Our Approach

The workaround of the previous subsection is heavily tailored to the particular example of Figure 1a.
Moreover, it requires that nodes know significantly more about the network topology than we allow.
However, the above example and workaround motivate and highlight some of the notable strategies
of our algorithm for Part-Wise Aggregation.
Sub-Part Divisions. As illustrated in the example, having all nodes use a shortcut in order to
send their private information to their part leader rapidly exhausts our Õ(m) message budget. To
solve this issue, we refine the partition of our network into what we call a sub-part division. In a
sub-part division each part Pi containing more than D nodes is partitioned into Õ(|Pi |/D) sub-parts
each with a spanning tree rooted at a designated node termed the representative of the sub-part.
In the preceding example the representatives are the left-most nodes of each sub-part. Each subpart uses its spanning tree to aggregate towards its representative, who then alone is allowed to
use shortcut edges to forward the result toward the part leader. This decreases the number of
nodes that use the shortcut from O(n) to Õ(n/D), thereby reducing the message complexity of
aggregating within a block from O(nD) to Õ(n).
Message-Efficient (and Deterministic) Shortcut Construction. If our algorithms are to
use shortcuts as we did in the preceding example, they must construct them message efficiently; i.e.,
with Õ(m) messages. No previous shortcut construction algorithm achieves low message complexity.
We show that not only do sub-part divisions allow us to use shortcuts message efficiently, but they
also allow us to construct shortcuts message efficiently. In particular, we give both randomized
5

and deterministic message-efficient shortcut construction algorithms. The latter is the first roundoptimal deterministic shortcut construction algorithm and is based on a divide-and-conquer strategy
that uses heavy path decompositions [38].
Star Joinings. To use sub-part divisions as above, we must demonstrate how to compute them
within our bounds. To do so, we begin with every node in its own sub-part and repeatedly merge
sub-parts until the resulting sub-parts are sufficiently large. However, it is not clear how many
sub-parts can be efficiently merged together at once, as obtained sub-parts can have arbitrarily
large diameter, rendering communication within a sub-part infeasible. We overcome this issue by
always forcing sub-parts to merge in a star-like fashion; this limits the diameter of the new subpart, enabling the new sub-part to adopt the representative of the center of the star. We call this
behavior star joinings. As we show, enforcing this behavior is easily accomplished with random coin
flips. We also accomplish the same behavior deterministically but with significantly more technical
overhead, drawing on the coloring algorithm of Cole and Vishkin [4].

4

Solving PA

In this section we show how to solve PA, given shortcuts and a sub-part division. The subroutines
necessary to compute shortcuts and sub-part divisions randomly and deterministically within our
time and message bounds are given in Section 5 and Section 6, respectively. Those subroutines
together with our algorithm for PA given a sub-part division and shortcuts imply our main result,
Theorem 1.2. We outline the algorithms here, and sketch their proofs of correctness and analysis,
deferring formal pseudocode and proofs to Appendix C.
For our purposes it is convenient to assume that in our PA instance each part Pi also has a
leader li ∈ Pi where every v ∈ Pi knows the ID of li . As we show in Appendix B, we can dispense
with this assumption at the cost of logarithmic overhead in round and message complexity. As
we ignore multiplicative polylogarithmic terms, for the remainder of the paper we assume that a
leader for each part is always known in our PA instances.
One of the crucial ingredients we will rely on to solve PA instances as above is sub-part divisions.
Definition 4.1 (Sub-part
Given partition (Pi )N
i=1 of V , a sub-part division is a partition
 division).

|Pi |
of every part Pi into Õ 1 + D sub-parts S1 , . . . , Ski . Each sub-part Sj also has a spanning tree
of diameter O(D) rooted at a node r ∈ Sj , termed the sub-part’s representative.
We note that sub-parts need not coincide with blocks in a meaningful way. See Figure 2.
The second ingredient we rely on is tree-restricted shortcuts, along which we will route (some
of) our messages. To do so, we must first restate an algorithm of Haeupler, Izumi, and Zuzic
[19] which we refer to as BlockRoute, that convergecasts/broadcasts within shortcut blocks. As
convergecast and broadcast are symmetric, we only discuss convergecast.
Lemma 4.2. ([19, Lemma 2]) Let T be a tree of depth D. Given a family of subtrees such that
any edge of T is contained in at most c subtrees, there is a simple deterministic algorithm that can
perform a convergecast/broadcast on all of the subtrees in O(D + c) CONGEST rounds.
Specifically, for convergecasts, if multiple messages are scheduled over the same edge, the algorithm forwards the packet with the smallest depth of the subtree root, breaking ties with the smallest
ID of the subtree.
6

One observation we make about this algorithm, and which will prove crucial since we only allow
representatives to use shortcuts, is the following.
Observation 4.3. At most D messages are sent per node which requires its information to be
convergecasted (symmetrically, which requires to be broadcast to) in the algorithm of Lemma 4.2.
We now show how given a sub-part division and a T -restricted shortcut, we can round- and
message-efficiently solve PA with and without randomization. Our method is given by Algorithm 2
(which incorporates both our deterministic and randomized algorithm), and works as follows. First,
each leader li of part Pi broadcasts an arbitrary message mi to all nodes in Pi . Then, symmetrically
to how mi was broadcast, each li computes f (Pi ) (here nodes also aggregate while convergecasting
to li ) and then broadcasts f (Pi ) to all nodes of Pi . The most technically involved aspect of our
algorithm is how li broadcasts mi to all nodes in Pi . If |Pi | is smaller than D, broadcast can be
trivially performed along the spanning tree of the single sub-part of Pi in O(D) rounds with O(|Pi |)
messages. However, if Pi is larger than D, we use shortcuts, as follows.
For our deterministic algorithm, we repeat the following b times: every representative in a block
which received the message mi spreads mi to other representatives in its block using BlockRoute
along the shortcut (convergecasting and broadcasting from/to representatives in the part). Next,
representatives with mi spread mi to nodes in their sub-part. Lastly, nodes with mi spread mi to
neighboring nodes in adjacent sub-parts. Crucially, only our representatives use shortcuts, thereby
limiting our message complexity, by Observation 4.3. We illustrate the broadcast of mi in Figure 3
in Appendix C.
Our randomized algorithm works similarly, with the following modification: each part leader
independently delays itself – and subsequently, its entire part – before sending its first message at
the beginning of the algorithm, by a delay chosen uniformly in the range [c] (here c is the shortcut’s
congestion). This limits the number of parts which would use any given edge during any round – in
a simpler model where arbitrarily large messages could be sent along an edge – to O(log n) w.h.p.
As only one message can be sent along an edge, we execute BlockRoute as before, but rather
than break ties as in Lemma 4.2, we simply spend O(log n) rounds between each “meta-round” of
the algorithm in this idealized world, to allow each node to forward all of its O(log n) messages.
This broadcast within blocks requires O(D log n) CONGEST rounds.
The following lemma states the performance of our algorithms.
Lemma 4.4. Given a sub-part division and a T -restricted shortcut with congestion c and block
parameter b, Algorithm 2 uses Õ(m) messages to solve PA either w.h.p in Õ(bD + c) rounds or
deterministically in Õ(b(D + c)) rounds.
Proof (Sketch). The deterministic round complexity follows by summing the round complexities of
sub-routines. The randomized round complexity results similarly (taking into account the delay
of c rounds), but requires noting that a Chernoff and union bound shows that w.h.p. no more
than O(log n) messages are scheduled over any edge in any given meta round.
The

 only nuance
|Pi |
to message complexity is that when BlockRoute is run, each of the Õ 1 + D sub-parts use
O(D) messages, by Observation 4.3. It remains to prove this algorithm’s correctness. Correctness
of broadcasting mi is trivial if |Pi | < D. Moreover, if |Pi | > D, a simple argument by induction over
blocks shows that b iterations suffices for parts of more than D nodes. Correctness of computing
f (Pi ) and broadcasting f (Pi ) symmetrically follow.

7

Because our PA algorithm is essentially the same algorithm we use to verify that our shortcuts
have good block parameter, we now describe this second algorithm. We verify the block parameter
of a fixed part Pi as follows. Run Algorithm 2 to broadcast an arbitrary message mi . If our block
parameter is sufficiently small then every node will receive mi and assume it as such. Moreover,
if our block parameter is too large but Algorithm 2 succeeds we can still use Algorithm 2 to
inform all nodes in Pi of Pi ’s block parameter symmetrically to how mi was broadcast. However,
if Algorithm 2 fails –i.e. some node does not receive mi – then we must somehow inform all nodes
that the block parameter is too large. We do so by having each node that does not receive mi
inform its neighbors in Pi that it did not receive mi . There must be some such neighbor in Pi that
did receive mi . By one additional call to Algorithm 2 this neighbor can inform all nodes that did
receive mi that the block parameter is, in fact, too large. This algorithm gives the following lemma.
Lemma 4.5. Given parts (Pi )N
i=1 , a sub-part division, a c-congestion T -restricted shortcut, H, and
desired block parameter b, one can deterministically (resp., w.h.p.) inform every node whether its
part’s block parameter in H exceeds b in Õ(b(D +c)) (resp. Õ(bD +c)) rounds with Õ(m) messages.

5

Randomized Subroutines

In this section we outline how we construct sub-part divisions and shortcuts round- and messageoptimally using randomization. Pseudocode and full proofs are deferred to Appendix E.
We first show how a sub-part division can be computed with randomization, by randomly
sampling sub-part representatives. In particular, for large parts (|Pi | ≥ D), every node decides to
n
be a representative with probability min{1, log
D } and then representatives claim balls of radius D
around them as their sub-part. This is Algorithm 3, whose properties are given below.
Lemma 5.1. Algorithm 3 computes a sub-part division of a part with a known leader w.h.p in
O(D) rounds with O(m) messages.
Proof (Sketch). Chernoff and union bounds prove the sub-part division is of the appropriate size.
This fails for small parts Pi (with |Pi | < D), but for these parts it is trivial to compute a sub-part
division by having the part’s leader be the representative.
We now show in Algorithm 4 how we message-efficiently construct a T -restricted shortcut with
randomization. We rely on the CoreFast shortcut construction algorithm of Haeupler et al. [19].
In CoreFast, a sub-sampled set of vertices broadcast up T , attempting to “claim” edges; edges
with too many vertices trying to claim them are discarded. To control the message complexity,
we only have the Õ(n/D) sub-part representatives attempt to claim edges. The correctness and
runtime of Algorithm 4 is given by Lemma 5.2.
Lemma 5.2. Given partition partition of V , (Pi )N
i=1 where v ∈ Pi knows leader li , a sub-part
division, spanning tree T and the existence of a T -restricted shortcut with congestion c and block
parameter b, Algorithm 4 computes a T -restricted shortcut with congestion at most Õ(c) and block
parameter at most 3b in Õ(bD + c) rounds with O(n) messages w.h.p.
Proof (Sketch). Since only the Õ(n/D) sub-part representatives broadcast up a tree of depth O(D),
each uses O(D) messages and so we use O(n) messages. Round complexity is trivial. Congestion
of the shortcut follows by construction. The block parameter can be shown by arguing that we can
only discard so many extra edges relative to the optimal shortcut and each extra discarded edge
induces a new block.
8

6

Deterministic Subroutines

In this section we show how to construct sub-part divisions and shortcuts deterministically. Again,
we defer pseudocode and full proofs to Appendix E.

6.1

Computing Sub-Part Divisions

Our algorithm for constructing sub-part divisions repeatedly merges together sub-parts until they
are of sufficient size. However, if sub-parts are allowed to merge arbitrarily, the resulting subparts may have prohibitively large diameter. The diameter of resulting sub-parts can be limited by
forcing sub-parts to always join in a star-like fashion. As such, we begin by providing a deterministic
algorithm to enable such behavior. We term this behavior a star joining.
Definition 6.1 (Star joining). Let (Pi )N
i=1 partition V . We say a star joining is computed over
parts (Pi )N
if
the
following
holds:
a
constant
fraction of the parts Pi are designated as receivers,
i=1
and the other parts Pi are designated as joiners. For every joiner part Pi , all v ∈ Pi knows some
(common) edge with one endpoint in Pi and another end-point in some receiver part Pj .
We now show how a star joining can be computed deterministically, given a deterministic PA
solution. We use as a sub-routine the 3-coloring algorithm of Cole and Vishkin [4]. Roughly,
the Cole and Vishkin [4] algorithm works as follows. Every node begins with its ID as its color,
meaning there are initially n colors. Next, every node updates its color based on its neighbors’
colors, logarithmically reducing the number of possible colors. This is then repeated log∗ n times.
For more, see Cole and Vishkin [4]. The properties of this algorithm are as follows.
Lemma 6.2. ([4, Corollary 2.1]) An oriented n-vertex graph with maximum out-degree of one can
be 3-colored in O(log∗ n) rounds with O(m log∗ n) messages.
We give our algorithm for deterministically computing star joinings in Algorithm 5 which works
as follows. Take the super-graph whose nodes are parts and whose edges are the chosen (directed)
edges. First, designate parts with at least two incoming edges receivers and all parts with an
outgoing edge into one such part a joiner. These parts constitute all trees in our super-graph and
so we next remove them from the super-graph, leaving only (directed) paths and (directed) cycles.
On the remaining paths and cycles, simulate the Cole-Vishkin algorithm to compute a 3-coloring
of the remaining nodes in the super-graph. For colors k = 1, 2, 3 make all k-colored parts receivers,
their neighbors joiners and remove these parts from this process. The properties of our deterministic
star joining algorithm are given by the following lemma.
Lemma 6.3. Let (Pi )N
i=1 partition V and suppose that every v ∈ Pi knows some edge ei ∈ E exiting
Pi . Moreover, suppose algorithm A solves PA over (Pi )N
i=1 . Then, Algorithm 5 computes a star
∗
N
joining over (Pi )i=1 with O(log n) repetitions of A.
Proof (Sketch). Standard graph-theoretic arguments show that a constant fraction of nodes are
receivers. Moreover, it is not too hard to see that the Cole-Vishkin algorithm can be efficiently
simulated within our bounds.
We now use star joinings to deterministically compute sub-part divisions in Algorithm 6 as
follows: start with each node in its own sub-part; compute star joinings and merge stars of joiners centered around receivers O(log n) times, fixing sub-parts once they have at least D nodes.
Correctness and runtime of Algorithm 6 are given by the following lemma.
9

N
Lemma 6.4. Given partition (Pi )N
i=1 of V , Algorithm 6 computes a sub-part division of (Pi )i=1 in
Õ(D) rounds with Õ(n) messages.

6.2

Computing Shortcuts Deterministically

Having shown how sub-part divisions can be computed in a deterministic fashion, we now turn to
our deterministic shortcut construction. We rely on heavy path decompositions [38].
Definition 6.5 (Heavy Path Decomposition [38]). Given a directed tree T , an edge (u, v) of T is
heavy if the number of v’s descendants is more than half the number of u’s descendants; otherwise,
the edge is light. A heavy path decomposition of T consists of all the heavy edges in T .
It is immediate from the definition that each leaf-to-root path on an n-node tree T intersects
at most blog2 nc different paths of T ’s heavy path decomposition. Given a rooted tree T of depth
D, a heavy path decomposition of T can be easily computed in O(D) rounds using O(n) messages.
Our deterministic shortcut construction algorithm, Algorithm 8, first computes a heavy path
decomposition and then computes shortcuts on the obtained paths in a bottom-up order. Thus,
we first provide a sub-routine, Algorithm 7, that computes shortcuts of congestion O(c log D) on
a path P . Algorithm 7 iteratively extends paths used for shortcuts, repeatedly doubling them in
length, unless too much congestion results. See Figure 4 in Appendix E. This algorithm’s properties
are as follows.
N

Lemma 6.6. Given directed path P of length D, desired congestion c and S : V → 2(Pi )i=1 which
denotes for each vertex v which parts want to use v’s parent edge in P , Algorithm 7 returns Sf :
N
V → 2(Pi )i=1 s.t. for every v ∈ P it holds that |Sf (v)| = O(c log D) in O(c log D + D) rounds.
We now turn to describing the overall shortcut construction algorithm, Algorithm 8, and analyze
the resulting block parameter there. We limit message complexity by only allowing sub-part representatives to send a message requesting that an edge be used in their part’s shortcut. As we show,
each bottom-up computation yields good shortcuts for a constant fraction of parts. Thus, after
each bottom-up computation, we can use our block parameter verification algorithm – Lemma 4.5
– to identify the parts for which our shortcut construction succeeded and freeze the shortcut edges
of said parts. The correctness and runtime of Algorithm 8 is given by Lemma 6.7.
Lemma 6.7. Given: partition (Pi )N
i=1 where v ∈ Pi knows leader li ∈ Pi ; a tree T of depth D
which admits a T -restricted shortcut of congestion c and block parameter b; and a sub-part division,
Algorithm 8 deterministically computes in Õ(b(c + D)) rounds and Õ(m) messages, a shortcut with
congestion O(c log n) and block parameter O(b).
Proof (Sketch). The stated round complexity comes from summing sub-routines. The message
complexity follows similarly and requires noting that only the Õ(n/D) sub-part representatives
forward their part ID up at most D nodes when running Algorithm 7. Lastly, there can only
be a constant number of parts with bad block parameter in each iteration. Each extra block we
introduce corresponds to a broken edge that is not broken by the original shortcut. However, each
such edge also corresponds to some number of parts that tried to use it and since a part can only
try to use so many edges in our shortcut we have that not that many extra edges can be broken.

10

Appendix
A

Applications of Our PA Algorithms

Here we outline the applications of our round- and message-optimal PA algorithms for multiple
distributed graph problems. We start with a discussion of the problems referred to in Section 1.2,
and then discuss additional applications of our PA algorithm to optimization as well as verification
problems, in Appendix A.2.

A.1

Deferred Proofs of Section 1.2

Here we address how to apply our PA algorithm to solve MST, Approximate Min-Cut and Approximate SSSP, starting with a formal definition of these problems.
The input to all three problems consists of an undirected weighted graph, with edge weights in
[1, poly(n)]. Initially, every node knows its neighbors’ IDs and the weight associated with each of
its incident edges.
MST. MST is solved when every node knows which of its incident edges are in the MST.
Approximate Min-Cut. Min-cut is (1 + )-approximated when every node knows whether or
not it belongs to a set S ⊂ V such that the size of the cut given by (S, V \ S) is at most (1 + )λ,
where λ is the size of the minimum cut of G with the prescribed weights.
Approximate SSSP. An instance of α-approximate single source shortest paths (SSSP) consists of an undirected weighted graph G as above and a source node s, which knows that it
is the source node. For v ∈ V we denote by d(s, v) the shortest path length between s and
v in G and L = maxu,v d(u, v). The problem is solved once every node v knows dv such that
d(s, v) ≤ dv ≤ α · d(s, v).
We now restate the round and message complexities we obtain for these problems using our
new PA algorithm and discuss the algorithms used to achieve these bounds. As before, recall that
√
since every graph admits a shortcut with b = 1 and c = n, our algorithms simultaneously achieve
√
worst-case optimal Õ(m) message complexity and worst-case optimal Õ(D + n) round complexity.
Corollary 1.3. Given a graph G admitting a tree-restricted shortcut with congestion c and block
parameter b, one can solve MST w.h.p in Õ(bD+c) rounds and Õ(m) messages and deterministically
in Õ(b(D + c)) rounds with Õ(m) messages.
Proof. Our algorithm uses Theorem 1.2 to simulate Borůvka’s classic MST algorithm [33]. In
Borůvka’s algorithm every node initially belongs to its own part. Then, for O(log n) rounds each
part merges with the part it is connected to by its minimum outbound edge. The problem of
determining the minimum-weight outbound edge of a part is an example of Part-Wise Aggregation,
which we solve with the algorithm of Theorem 1.2. Whenever a node v is incident to this edge it
remembers that the neighbor along that edge is now in the same part as v. Round and message
complexities are trivial and correctness follows from that of Borůvka’s algorithm.

11

Corollary 1.4. For any  > 0 and graph G admitting a tree-restricted shortcut with congestion c
and block parameter b, one can (1 + )-approximate min-cut w.h.p. in Õ (bD + c) · poly(1/) rounds
and Õ (m) · poly(1/) messages.
Proof. Haeupler and Li [18] provide a distributed algorithm with the stated round complexity and
approximation factor based on a solution to PA. Roughly the algorithm works as follows. We
compute O( logβ n ) low diameter decomposition; in particular, as in Miller et al. [30] every node
starts a weighted BFS at a randomly-chosen time and runs this weighted BFS for O( logβ n ) rounds.
During this weighted BFS, nodes claim as part of their ball any nodes they reach that have not
yet been claimed or started their weighted BFS. The weights used for the weighted BFS change
in each round: any weight strictly inside a claimed ball is updated to have weight 0 and any edge
incident to two claimed balls is additively increased. Moreover, the increments used by the weighted
BFS geometrically increase in each iteration so that despite increasing edge weights, the weighted
BFS can still efficiently proceed. Lastly, the union of all BFS trees returned by every weighted
BFS is returned as a tree, T ∗ , that approximates distance in the graph; to inform nodes of their
approximate distance from the source, the source can simply broadcast on T ∗ .
What makes this algorithm difficult to implement is that running a weighted BFS with edge
weights set to 0 requires that a weighted BFS traverse components connected by weight-zero edges
of potentially large diameter “in a single round”. To overcome this issue, Haeupler and Li [18] use
PA to efficiently traverse these connected components. For more see Haeupler and Li [18]. Relying
on our algorithm for PA and observing that these dominate the round and message complexity of
the weighted BFS calls, our claimed round and message complexities follow.
Corollary 1.5. For any β = O(1/poly log n), given a graph G admitting a tree-restricted shortcut
with
b, one can LO(log log n)/ log(1/β) -approximate SSSP w.h.p in
 congestion
 c and block parameter
 
Õ β1 (bD + c) rounds and Õ m
messages.
β
Proof. Haeupler and Li [18] provide a distributed algorithm with the stated round complexity and
approximation factor based on a solution to PA. Roughly the algorithm works as follows. We
compute O( logβ n ) low diameter decomposition; in particular, as in Miller et al. [30] every node
starts a weighted BFS at a randomly-chosen time and runs this weighted BFS for O( logβ n ) rounds.
During this weighted BFS, nodes claim as part of their ball any nodes they reach that have not
yet been claimed or started their weighted BFS. The weights used for the weighted BFS change
in each round: any weight strictly inside a claimed ball is updated to have weight 0 and any edge
incident to two claimed balls is additively increased. Moreover, the increments used by the weighted
BFS geometrically increase in each iteration so that despite increasing edge weights, the weighted
BFS can still efficiently proceed. Lastly, the union of all BFS trees returned by every weighted
BFS is returned as a tree, T ∗ , that approximates distance in the graph; to inform nodes of their
approximate distance from the source, the source can simply broadcast on T ∗ .
What makes this algorithm difficult to implement is that running a weighted BFS with edge
weights set to 0 requires that a weighted BFS traverse components connected by weight-zero edges
of potentially large diameter “in a single round”. To overcome this issue, Haeupler and Li [18] use
PA to efficiently traverse these connected components. For more see Haeupler and Li [18]. Relying
on our algorithm for PA and observing that these dominate the round and message complexity of
the weighted BFS calls, our claimed round and message complexities follow.

12

A.2

Further Applications of Our PA Algorithms

Here we mention some further applications of PA, all of which prior work has show to have PA
as their round and communication bottleneck. For all of these problems our new PA algorithm of
√
Theorem 1.2 therefore yields Õ(D + n)-round and Õ(m)-message algorithms.
Graph Verification Problems. In [5], Das Sarma et al. provided an extensive list of lower
bounds for optimization problems (many of which we referred to throughout this paper, as their
lower bounds prove our algorithms’ round complexity to be optimal). Das Sarma et al. further
showed that their lower bounds carry over to verification problems. For these problems, the input
is a graph G and a subgraph H of G and an algorithm must verify whether this subgraph satisfies
some property, such as whether H is a spanning tree or H is a cut (see [5] for more).
Das Sarma et al. also provided algorithms for this long list of verification problems, relying heavily on an optimal MST algorithm and the following connected component algorithm of Thurimella
[39, Algorithm 5]. Thurimella’s algorithm, given a graph G and subgraph H as above, outputs a
label `(v) for each vertex v ∈ V (G) such that `(u) = `(v) if and only if u and v are in the same
connected component of H. The problem solved by Thurimella is easily cast as an instance of PA,
by having each part elect a leader in a connected component in H – say, a node of minimum ID
– and use the leader’s ID as a label.5 Without repeating the arguments of Das Sarma et al. [5],
√
we note that as MST and Thurimella’s algorithm require Õ(D + n) rounds (based on [25]), so
do the algorithms of Das Sarma et al., and this is tight for these verification problems by their
lower bounds. Our MST and PA algorithms show that for the long list of verification problems Das
Sarma et al. considered, optimal round complexity does not preclude optimal message complexity,
as we can attain both simultaneously.
Corollary A.1. All the graph verification problems considered in [5, Section 8] can be solved in
√
an optimal Õ(D + n) rounds and Õ(m) messages.
Approximation of Minimum-Weight Connected Dominating Set Another application of
our PA algorithms follows from the work of Ghaffari [14]. In that work, Ghaffari shows that the
algorithm of Thurimella [39], discussed above, can be used to to compute an O(log n)-approximate
minimum weight connected dominating set (a set of nodes S such that all vertices in G are at
distance at most one from a node in S). In particular, Ghaffari relied on the ability to extend
Thurimella’s algorithm to the case where nodes also have some value x(v) assigned to them so
that the label of nodes in a connected component can be equal to: (A) the list of the k = O(1)
largest values x(v) in the component, or (B) the sum of values x(v) in the component. Both these
applications can be cast as instances of PA. Plugging in our PA algorithm into Ghaffari’s algorithm
[14], we obtain the following.
√
Corollary A.2. There exists an Õ(D + n)-round, Õ(m)-message algorithm which computes an
O(log n)-approximate minimum weight connected dominating set.
5

We note that for bipartiteness verification, Das Sarma et al. relied on the algorithm of [39] also outputting a
rooted spanning tree of each connected component of H with each vertex knowing its level in the tree. As our PA
algorithm maintains such rooted spanning trees, it can also be used to solve this verification problem within the same
bounds.

13

k-dominating sets. Another distributed primitive used in multiple distributed graph algorithms
is the problem of computing an O(n/k)-node k-dominating set. That is, a set of nodes S such that
every node in G is at distance at most k from some node in S. This problem has found applications in
distributed algorithm for MST [25] and (1 + )-approximate eccentricity computation [22]. For this
problem Õ(k)-round algorithms are known, [25]), including some with linear message complexity
√
√
[37]. However, for large k, i.e. k  max{D, n}, no Õ(D + n)-round, Õ(m)-message algorithm
was known. Such an algorithm follows immediately from a simple generalization of our sub-part
division algorithm, as follows. As in Algorithm 6, we repeatedly merge sub-parts, marking a subpart as complete when it attains some size. Unlike the above algorithm, this threshold is chosen to
be k/6 rather than D. By arguments which are a simple generalization of Algorithm 6’s analysis,
this implies that the obtained sub-parts have diameter at most k, and that each sub-part contains
at least k/6 nodes, one of which is its representative. This set of representatives therefore has
cardinality at most 6n/k and it forms a k-dominating set. The one delicate point to notice is
that now we can solve Part-Wise Aggregation using our round- and message-optimal algorithm
for PA – unlike in Algorithm 6, which is a sub-routine in our PA algorithm. In particular, even if
√
√
k  max{D, n}, this can be done in Õ(D + n) rounds (and Õ(m) messages). Therefore, as each
of the O(log n) iterations of this algorithm can be implemented using some O(log∗ n) many calls
to PA (by Lemma 6.3), together with some local computation, we obtain the following corollary of
Theorem 1.2.
√
Corollary A.3. For any integer k, there exists an Õ(D + n)-round, Õ(m)-message algorithm
which computes a k-dominating set of size O(n/k).
√
This last corollary bolsters our confidence that the ubiquitous Θ̃(D+ n) bounds for distributed
graph algorithms can be matched with Õ(m) messages for an even wider range of problems not
discussed in this paper.

B

Dispensing with Known Leader Assumption

Throughout this paper we have assumed that parts always know a leader. That is for every part
Pi every node v ∈ Pi knows the ID of some leader li ∈ Pi . We solved PA assuming that this holds.
We now show that this assumption can dispensed with. In particular, we demonstrate that an
algorithm that solves PA with the assumption of a known leader for each part can be converted
into one that makes no such assumption with only logarithmic overhead in round and message
complexities. The conversion is deterministic and so it demonstrates that a known leader is not
required for either or deterministic or our randomized results.
Our algorithm is Algorithm 1 and works as follows: start with the singleton partition where
every node is its own leader; repeatedly coarsen this partition O(log n) times until it matches the
input PA partition by applying our PA solution that assumes that a leader is known to merge the
stars given by a star joining. At each step in the coarsening we maintain the invariant that every
part knows a leader and so in the end we need only solve PA with a known leader which we can
do by assumption.
Lemma B.1. Given a PA instance where no leaders are known and a PA algorithm, A, that
assumes leaders are known using R rounds and M messages, Algorithm 1 solves the PA instance
with no leaders in Õ(R) rounds and Õ(M ) messages.
14

Algorithm 1 PA without leaders.
Input: PA instance with parts (Pi )N
i=1 ;
Input: PA algorithm, A, that assumes every part knows a leader.
Output: a solution to the input PA problem.
1: for all i ∈ |V | do
2:
Set Pi0 ← {i} and li ← i.
. Each Pi0 maintains a leader li , initially set to i
for O(log n) rounds do
4:
for all part Pi0 do
5:
Pick some ei = (u, v) ∈ Pi0 × (V \ Pi0 ) by running A where u, v are in the same Pi .
3:

6:
7:
8:
9:
10:

Compute a star joining with Algorithm 5 over the Pi0 s using edges {ei }.
for all part Pi0 which joined Pj0 in the star joining do
Inform each v ∈ Pi0 that their leader is now lj by running A.
Merge Pi0 into Pj0 .
Run A on the PA instance consisting of the Pi0 s, each with a known leader li .

Proof. We first prove round and message complexities. Our algorithm runs A to solve PA with a
known leader and Algorithm 5 to compute a star-joining logarithmically many times. The latter
consists of O(log∗ n) calls to A. Thus, the stated round and message complexities follow trivially.
We now argue correctness. Each round a constant fraction of the Pj0 s participating in the
algorithm get to merge by definition of a star joining and so O(log n) repetitions are sufficient to
coarsen every Pj0 to a Pi . Moreover, P10 , . . . , PN0 0 is valid input to A since we maintain the invariant
that every node in a Pj0 has an elected leader. At the end of this coarsening our PA instance now
has elected leaders. By the correctness of A our algorithm is correct.

C

Deferred Proofs, Pseudocode and Figures of Section 4

In this section we give pseudo-code for and the correctness and runtime proofs of our main PA
algorithm that takes a sub-part division and shortcut as input. We also do the same for the
algorithm of Haeupler, Izumi, and Zuzic [19] which we use to aggregate within shortcut blocks and
our algorithm for verifying block parameter.
Lemma 4.4. Given a sub-part division and a T -restricted shortcut with congestion c and block
parameter b, Algorithm 2 uses Õ(m) messages to solve PA either w.h.p in Õ(bD + c) rounds or
deterministically in Õ(b(D + c)) rounds.
Proof. We first prove our round complexities. We start by proving the stated round complexity
for broadcasting mi . Any part that is of fewer than D nodes clearly only requires O(D) rounds.
For any part of more than D nodes, we argue that each of the b iterations requires only Õ(D + c)
rounds or O(D log n) if a random delay of U (c) is added. Running BlockRoute only requires
O(D + c) rounds by Lemma 4.2. Moreover, if a random delay is added, a Chernoff and union
bound show that w.h.p a node never has more than O(log n) outstanding messages. By allowing
each node to flush up to O(log n) outstanding messages after each round, BlockRoute requires
O(D log n) rounds by Lemma 4.2. Next, broadcasting mi within any sub-part requires Õ(D) rounds
as sub-parts are of diameter Õ(D). Broadcasting mi to adjacent subparts requires only a single
round. Lastly, computing f (Pi ) and broadcasting f (Pi ) symmetrically require Õ(b(D + C)) rounds.
15

Algorithm 2 PA given shortcut and sub-part division.
Input: PA instance;
Input: sub-part division;
Input: T -restricted shortcut
Notation: for any v ∈ V , S(v) ⊆ V and r(v) ∈ V denote v’s sub-part and its representative;
S
Notation: for any U ⊆ V we let S(U ) = u∈U S(u) and R(U ) = {r(U ) | u ∈ U };
Notation: for a part Pi we denote by Ri = {r(U ) | u ∈ U } the set of representatives in Pi ;
Notation: for part Pi and node v ∈ V , we denote by Bi (v) ⊆ V the block of Pi incident to v;
Output: solves PA
1:
2:
3:
4:
5:
6:
7:
8:
9:
10:
11:
12:
13:
14:
15:
16:
17:
18:
19:
20:
21:
22:

for Part Pi do
if |Pi | < D then
Broadcast mi from li to all of Pi along Pi ’s spanning tree.
else
if Randomized algorithm then
Delay part Pi by (independent) ∼ U (c);
Blow up subsequent calls to BlockRoute by O(log n).
Route mi from li to r(li ) using BlockRoute.
A ← {r(li )}, I ← {}.
. Initialize sets of “active”/“inactive” representatives.
for b iterations do
S
Run BlockRoute on A to send mi to all nodes in r∈A Bi (r) ∩ Rj .
S
A ← A r∈A Bi (r) ∩ Rj .
for all r ∈ A do
Broadcast mi from r to S(r) along S(r)’s representing tree.
Broadcast mi over edges in E that exit sub-parts in S(A).
for all Vertex v 6∈ S(A) ∪ S(I) do
if v received a message in line 15 then
v routes mi to r(v).
I ← I ∪ A.
A ← representatives that received a message in line 18.
Symmetrically to lines 1-20, compute f (Pi ) at li .
Symmetrically to lines 1-20, broadcast result of f (Pi ) from li to all nodes in Pi .

16

b1

b2

b3

Figure 2: A division of a part, incident to blocks b1 , b2 and b3 , into 4 sub-parts. Solid colored lines
indicate edges in the tree of each sub-part according to the color of the sub-part representative
while dashed lines indicate edges in E between sub-parts. Stars are sub-part representatives.
We now prove a message complexity of Õ(m). We start by proving this message complexity for
broadcasting mi . Message complexity is trivial if the part is of fewer than D nodes. Next consider
parts of more than D nodes. Notice that nodes in a given sub-part only send messages in those
rounds where the sub-part is active. Moreover, once a sub-part becomes inactive, it never again
becomes active. Consequently, routing

 mi to li requires O(n) messages across all sub-parts in all
|Pi |
parts. Moreover, each of the Õ D sub-parts in part Pi use BlockRoute at most once, using
O(D) messages per sub-part by Lemma 4.2; as a result this step uses Õ(|Pi |) messages for part
Pi and so Õ(n) messages total. Broadcasting within all sub-parts requires O(n) messages since
each sub-part only does so once and has a spanning tree with which to do so. Broadcasting across
sub-parts uses each edge at most twice and so uses O(m) messages. Lastly, computing f (Pi ) and
broadcasting f (Pi ) symmetrically require O(m) messages.
Correctness of broadcasting mi is trivial if |Pi | < D. Moreover, if |Pi | > D, a simple argument
by induction over blocks shows that b iterations suffices for parts of more than D nodes. Correctness
of computing f (Pi ) and broadcasting f (Pi ) symmetrically follow.
Lemma 4.5. Given parts (Pi )N
i=1 , a sub-part division, a c-congestion T -restricted shortcut, H, and
desired block parameter b, one can deterministically (resp., w.h.p.) inform every node whether its
part’s block parameter in H exceeds b in Õ(b(D +c)) (resp. Õ(bD +c)) rounds with Õ(m) messages.
Proof. Round and message complexities follow trivially from Lemma 4.4 and Lemma 4.2. We now
argue correctness. If a node does not receive mi when Algorithm 2 is first run then the block
parameter of Pi is certainly larger than b. When this occurs, all nodes will either be told by li that
the block parameter is larger than b or they will not receive mi , implicitly informing them that the
block parameter of Pi is larger than b. If all nodes receive mi , then li clearly distributes to all nodes
in Pi the number of blocks incident to Pi and so the block number of Pi is correctly determined to
be above or below b as desired.

17

Iteration 0

Active:
Inactive:
b2

b3

Iteration 1

b1

Active:
Inactive:
b3

b2

Iteration 2

b1

Active:
Inactive:
b1

b2

b3

Figure 3: Nodes with mj (yellow circles) and (in)active representatives at the end of each broadcast
iteration for a part with 3 blocks b1 , b2 and b3 . The leader li is indicated by a black square, li ,
while sub-part representatives are indicated by stars; solid lines and dotted black lines correspond
to intra- and inter-sub-part edges.

D

Deferred Proofs and Pseduocode of Section 5

In this section we give our randomized sub-part division and shortcut construction algorithms along
with the properties of these algorithms.
Lemma 5.1. Algorithm 3 computes a sub-part division of a part with a known leader w.h.p in
O(D) rounds with O(m) messages.
Proof. Runtime and message complexity are trivial. Correctness is trivial for parts of fewer than
D nodes, so consider parts of more than D nodes. By construction, each claimed sub-part
 has

diameter O(D). It remains to show that every node has a representative and there are Õ |PDi |
sub-parts in Pi . Fix node v and consider the ball of radius D around v. Since Pi has at least D
nodes, this ball is of size at least D and so a Chernoff bound shows that w.h.p Θ(log n) nodes in this
ball will elect themselves a representative, meaning v will have a representative. A union bound
over all v shows this to hold for every node. Moreover, the expected number
of representatives in


|Pi | log n
|Pi |
part Pi is
and so a Chernoff bound shows that w.h.p there are Õ D sub-parts in Pi . A
D
union bound shows this holds for all parts w.h.p.
Lemma 5.2. Given partition partition of V , (Pi )N
i=1 where v ∈ Pi knows leader li , a sub-part
division, spanning tree T and the existence of a T -restricted shortcut with congestion c and block
18

Algorithm 3 Randomized sub-part division.

1:
2:
3:
4:
5:
6:
7:
8:
9:
10:
11:

Input: partition of V given by (Pi )N
i=1 where v ∈ Pi knows leader li
Output: sub-part division
for part Pi do
if |Pi | ≤ D then
Let Pi have one sub-part with representative li .
Compute sub-part spanning tree by an O(D) round BFS restricted to Pi starting at li .
else
for v ∈ Pi do
n
With prob. min{1, log
D }, node v is a representative and sends its ID to Pi neighbors.
for O(D) rounds do
v broadcasts the first representative ID it hears to neighbors in Pi once.
v’s sub-part parent is the neighbor from which it first heard a representative ID.
v ∈ Pi determines for which of its neighbors it is a parent.

Algorithm 4 Randomized shortcut construction.

1:
2:
3:
4:
5:

Input: partition of V , (Pi )N
i=1 where v ∈ Pi knows leader li ;
Input: BFS tree T ;
Input: sub-part division
Output: T -restricted shortcut with congestion Õ(c) and block parameter < 3b
Set all Pi active.
for O(log n) iterations do
Run CoreFast [19] shortcut construction algorithm on representatives in active parts.
Set every Pi with block parameter < 3b on CoreFast result inactive (see Lemma 4.5).
Let every newly inactive Pi use the shortcut edges assigned to it by CoreFast.

19

parameter b, Algorithm 4 computes a T -restricted shortcut with congestion at most Õ(c) and block
parameter at most 3b in Õ(bD + c) rounds with O(n) messages w.h.p.
Proof. We first argue runtime and message complexity. Haeupler, Izumi, and Zuzic [19, Lemma 4]
show that CoreFast takes O(D log n+c) rounds. However, in this algorithm every node potentially
sends a message up
T once leading to super-linear message complexity. By amending CoreSlow

n
so only the Õ D
sub-part representatives send a message up T once as we do, it is easy to see
that the algorithm uses only Õ(n) messages total. Lastly, Lemma 4.5 shows that block parameter
with randomization uses only Õ(bD + c)) and Õ(m) messages.
We now argue correctness. Haeupler, Izumi, and Zuzic [19, Lemma 4] show that each time
CoreSlow is run, it computes a T -restricted shortcut with block parameter at most 3b for at
least half of the nodes and congestion at most 8c. It is easy to see that only having sub-part
representatives participate in CoreSlow does not affect correctness and so we conclude that
after O(log n) iterations every Pi has been rendered inactive. By construction every Pi has block
parameter < 3b and since the congestion of any edge increases by at most 8c in any iteration of
Algorithm 4, the total congestion of our returned shortcut is Õ(c).

E

Deferred Proofs, Pseudocode and Figures of Section 6

Here we provide pseudo-code and the correctness and runtime of our algorithms for deterministic
star-joining constructions, deterministic sub-part division construction and deterministic shortcut
construction.
Algorithm 5 Deterministic star joining.
Input: (Pi )N
i=1 s.t. v ∈ Pi knows edge ei exiting Pi and leader li ;
Input: PA algorithm A
Output: a star joining on (Pi )N
i=1
1: J , R ←
. Initialize joiners and receiver
 ∅

0
N
N
2: G ← ((Pi )i=1 ), {ei }i=1
3:
4:
5:
6:
7:
8:
9:

−
R ← R ∪ {Pi : δG
0 (Pi ) ≥ 2} by running A.
J ← J ∪ {Pi : Pi 6∈ R ∧ ei = (Pi0 , Pi ) s.t. Pi0 ∈ R} by running A.
G0 ← G0 \ (R ∪ J ).
Run the 3-coloring algorithm of Cole and Vishkin [4] on G0 .
for color k = 1, 2, 3 do
R ← R ∪ {Pi : Pi colored k} by running A.
J ← J ∪ {Pi : Pi 6∈ R ∧ ei = (Pi0 , Pi ) s.t. Pi0 ∈ R} by running A.

Lemma 6.3. Let (Pi )N
i=1 partition V and suppose that every v ∈ Pi knows some edge ei ∈ E exiting
Pi . Moreover, suppose algorithm A solves PA over (Pi )N
i=1 . Then, Algorithm 5 computes a star
∗
joining over (Pi )N
with
O(log
n)
repetitions
of
A.
i=1
Proof. We begin by proving correctness. Line 4 yields stars of joiners centered around receivers.
Moreover, the union of all nodes designated in Line 4 from a forest with trees of internal degree
at least 2. Therefore, the number of internal (marked) super-nodes (and therefore the number of
stars) in Line 4 is at most one half of the super-nodes of the tree.
20

Now consider the result of Line 8. As no super-node in G0 has in-degree at least two at this
point in the algorithm, the super-graph considered in Line 8 consists of directed cycles and paths.
Thus, each time we remove a Pi from the super-graph we remove at most three super-nodes from
the graph and Pi gets to merge with its neighbor. It follows that at least 13 of these super-nodes
are merged. Combining the first and second stage, we find that the super-nodes are combined into
stars, where the number of obtained nodes is less than 2/3 of the original nodes. Therefore the
above algorithm computes a star joining.
We now argue that our algorithm requires O(log∗ n) runs of A. This clearly holds for all subroutines of our algorithm except for Line 6. In particular, we must argue how the Cole-Vishkin
algorithm can be efficiently simulated on our super-graph using O(log∗ n) runs of A. We repeat the
following O(log∗ n) times. Let li be the known leader of Pi . Each Pi begins with the color of li ’s
ID. Next, the node in Pi incident to the edge chosen by Pi routes the color it received to li using A.
Then, li performs the Cole-Vishkin computation and then broadcasts Vi ’s new color to all nodes in
Pi using A.
Algorithm 6 Deterministic sub-part division.

1:
2:
3:
4:
5:
6:
7:
8:
9:
10:
11:
12:
13:
14:

Input: partition of V , (Pi )N
i=1
Output: a sub-part division
for part Pi do
Ii ← {{v} : v ∈ Pi }
. Initialize incomplete sub-parts
Ci ← {}
. Initialize complete sub-parts
for O(log n) iterations do
for Fj ∈ Ii do
S
if ∃ edge (u, v) ∈ Fj × ( Fj 0 ∈Ii Fj 0 \ Fj ) then
ej ← e for such edge e = (u, v) using PA.
else
S
ej ← e for some edge e = (u, v) ∈ Fj × ( Fj 0 ∈Ci Fj 0 ) using PA.
Run Algorithm 5 on Ii sub-parts with edges {ej } to compute a star-joining.
for Joiner Fj with edge ej = (u, v) with v ∈ Fj 0 do
Fj merges with Fj 0 using PA.
. if Fj 0 ∈ Ci , update Ci accordingly.
u remembers v as its parent.
Fj orients its tree edges to v using PA.

Ci0 ← {Fj ∈ Ii : |Fj | ≥ D} using PA.
16:
Ci ← Ci ∪ Ci0 .
return Division given by {Ci }N
i=1 .
15:

N
Lemma 6.4. Given partition (Pi )N
i=1 of V , Algorithm 6 computes a sub-part division of (Pi )i=1 in
Õ(D) rounds with Õ(n) messages.

Proof. Round and message complexities are trivial apart from the fact that we must show that
PA can be solved within our bounds on incomplete sub-parts. However, notice that an incomplete
sub-part has fewer than D nodes by definition along with a spanning tree in which every node
knows its parent; as such aggregating within each incomplete sub-part is trivially achievable with
O(D) rounds and O(m) messages.
21

Figure 4: Illustration of a directed path and its potentially shortcut-edge-connected subpaths after
iterations 0, 1 and 2 of Algorithm 7 respectively (indicated by dashed ovals).
We now argue correctness. Correctness for parts of fewer than D nodes is trivial. Consider
parts of more than D nodes. Sub-parts continue
until they are complete and have at
 to merge

least D nodes and so our division clearly has Õ 1 + PDi sub-parts. It remains to show that every
complete sub-part’s spanning tree has diameter Õ(D). When a complete sub-part results from two
incomplete sub-parts joining, its spanning tree has diameter at most 2D. Call these nodes the core
of the complete sub-part. When an incomplete sub-part Fj – which has spanning tree with diameter
at most D since it has fewer than D nodes by definition – joins a complete sub-part, it necessarily
joins by way of nodes in the core. Thus, any node in Fj is within 3D of any node in the core by
way of the resulting sub-part’s spanning tree. Similarly, any other subsequent incomplete sub-part
that joins the complete sub-part will be within 4D of any nodes in Fj by way of the associated
spanning tree. Thus, every complete sub-part has spanning tree with diameter at most 4D.
N

Lemma 6.6. Given directed path P of length D, desired congestion c and S : V → 2(Pi )i=1 which
denotes for each vertex v which parts want to use v’s parent edge in P , Algorithm 7 returns Sf :
N
V → 2(Pi )i=1 s.t. for every v ∈ P it holds that |Sf (v)| = O(c log D) in O(c log D + D) rounds.
Proof. To bound the running time, observe that iteration i of the algorithm can be implemented
in c + 2i rounds. Summing over all iterations i = 0, 1, . . . , log2 D − 1, the bound on the number of
rounds follows. To bound the congestion of the output shortcuts, we prove by induction that before
the i-th iteration the congestion on any edge is at most 2ci. This clearly holds before round i = 0.
Now, before round i, all edges are used by at most 2ci parts. After round i all edges (v, v + 1) for a
node v with v mod 2r+1 ∈ [0, 2i − 1] have their congestion unchanged, while all edges (v, v + 1) for
a node v with v mod 2i+1 ∈ [2i , 2i+1 − 1] have their congestion increase by at most 2c, implying
the claimed bound on the congestion.
Algorithm 7 assumes every node v begins with a set S(v) of part IDs that would like to use
v’s parent edge in the path. For simplicity, we assume vertices of P are numbered by their height,
v = 1, 2, . . . (i.e., the source of the path is number 1, its parent is numbered 2, etc’).
Lemma 6.7. Given: partition (Pi )N
i=1 where v ∈ Pi knows leader li ∈ Pi ; a tree T of depth D
which admits a T -restricted shortcut of congestion c and block parameter b; and a sub-part division,
Algorithm 8 deterministically computes in Õ(b(c + D)) rounds and Õ(m) messages, a shortcut with
congestion O(c log n) and block parameter O(b).
Proof. We first prove the runtime and message complexity. As mentioned above, a heavy path
decomposition of T can be computed in O(D) rounds using O(n) messages. We now bound the
22

Algorithm 7 Deterministic shortcut construction for paths.
Input: Path P ⊆ V ;
N
Input: Mapping S : V → 2(Pj )j=1 ;
Input: Desired congestion c
N
Output: Mapping Sf : V → 2(Pj )j=1
1: for v ∈ V do
2:
Set S0 (v) ← S(v).
3: for i = 0, 1, 2, . . . , log2 D − 1 do
4:
for every node v ≡ 2i mod 2i+1 do
5:
if |Si (v)| ≥ 2c then
6:
Break (v, v + 1) and set Si (v) ← ∅.
7:
else
8:
if no broken edges between v and u then
9:
Transmit Si (v) from v to u = v + 2r along P .
10:
Set Si+1 (u) ← Si (u) ∪ Si (v).
11: return Sf = Slog2 D .

Algorithm 8 Deterministic shortcut construction.

1:
2:
3:
4:
5:
6:
7:
8:
9:
10:
11:
12:
13:
14:
15:

Input: partition of V , (Pi )N
i=1 with leader li known by v ∈ Pi ;
Input: sub-part division
Input: BFS-tree T ;
Output: T -restricted shortcut with congestion Õ(c) and block parameter < 3b
Initially all Pi are active.
Compute heavy path decomposition of T .
for j = 1, 2, . . . , O(log n) do
for all v ∈ V do
if v is representative in active part Pi then
Sj (v) ← {li }.
else
Sj (v) ← ∅.
Set each heavy path with no incoming light edges active.
for blog nc repetitions do
Let Sf be the output of Algorithm 7 run on all active heavy paths.
S
For active path sink node v and light edge (v, u) let Sj (u) = Sj−1 (u) ∪ v Sf (v).
Set all active paths inactive and all heavy paths with source u as in Line 12 active.
Set parts with block parameter < 3b inactive (see Lemma 4.5).
return ∪j Sj (v) as v’s shortcut edges

23

message and round complexity of each iteration. First note that we can inform every path if it has
a light edge in O(D) rounds with O(n) messages. Next, running Algorithm 7 O(log n) times – once
on each heavy path – requires O(c log D log n + D log n) rounds and O(n log n) messages. Lastly,
notice that informing every node in a path that the path is now active requires O(D) rounds using
O(n) messages. Lastly, by Lemma 4.5, running Algorithm 7 is within our stated bounds. Summing
over iterations, we conclude that the overall round and message complexities are Õ(b(c + D)) and
Õ(m) respectively.
We now prove correctness. Notice that by Lemma 6.6 the number of parts assigned to an edge
in any particular iteration is at most O(c log D) and so the overall congestion on any edge is at
most O(c log D log n) = Õ(c).
We now analyze the block parameter. In particular, we argue that the number of active parts
is at least halved in each iteration. Let Aj be the set of active parts in iteration j. Let Uj be the
set of heavy edges used by H but broken in iteration j and therefore not assigned to any parts by
Sj . Each edge in Uj received at least 2c − c = c more requests by parts to use it than in H. Thus
each edge in Uj receives at least 2c − c = c requests from parts in Aj . However, each part in Aj can
contribute at most b such additional requests to a broken edge, as each block can only send one
b
additional request towards the tree’s root. Consequently, we have |Uj | ≤ Aj 2c
. Next, we say an
active part is bad in iteration j if more than 2b of its edges of H are broken in iteration j, and good
in iteration j otherwise. Note that for a good part the number of blocks in the output shortcut is
at most 3b = O(b). On the other hand, every broken heavy edge used in H is used at most c times
c
in H. We conclude that the number of bad active parts is at most |Uj | 2b
.
Combining both upper and lower bounds on |Uj |, the number of bad parts active parts is at
most Aj /2 in iteration j. Thus, after O(log n) iterations all parts will be marked inactive, meaning
the block parameter in the returned shortcut is at most 3b.

F

Our Results In Tabular Form

Throughout the paper we state our results in utmost generality by giving our algorithms’ running
time in terms of the optimal block parameter b and congestion c. As stated in Theorem 1.2 and its
Corollaries 1.3, 1.4 and 1.5 and Appendix A, for PA and the wide range of application problems
we consider, our deterministic algorithms terminate in Õ(b(D + c)) rounds and our randomized
algorithms terminate in Õ(bD + c) rounds. To make these bounds more concrete, we review some
known bounds on the parameters b and c in Table 1, and then state the implied running times of
all our algorithms for the above problems in Table 2.6

b
c

General
[15]

Planar
[15]

1
√
n

O(log D)
Õ(D)

Genus g
[19]
√
O( g)
√
Õ( gD)

Treewidth t
[20]

Pathwidth p
[20]

Minor Free
Minor Free

O(t)

p

Õ(D)

Õ(t)

p

Õ(D)

Table 1: Known bounds on block parameter, b, and congestion, c.
The two exceptions to this rule are our L -approximate SSSP and (1 + )-approximate Min-Cut, for which the
(randomized) bounds hold as stated in the table only for fixed (or polylogarithmic) .
6

24

Deterministic
Randomized

General
√
Õ(D + n)
√
Õ(D + n)

Planar
Õ(D)
Õ(D)

Genus g
Õ(gD)
√
Õ( gD)

Treewidth t
Õ(tD + t2 )

Pathwidth p
Õ(pD + p2 )

Minor Free
Õ(D2 )

Õ(tD)

Õ(pD)

Õ(D2 )

Table 2: Summary of running times of our algorithms.
Reviewing Table 2, we note that for all problems considered, a matching worst case round lower
√
bound of Ω̃(D + n) is given by Das Sarma et al. [5], while a trivial lower bound of Ω(D) holds for
these problems for all graphs. Our algorithms match the worst case bounds and the Ω(D) lower
bound (up to polylog terms) for any constant genus, treewidth and pathwidth, all while requiring
only Õ(m) messages. The exact optimal dependence on the parameters g, t and p remains an open
question.

References
[1] Baruch Awerbuch. Optimal distributed algorithms for minimum weight spanning tree, counting, leader election, and related problems. In Proceedings of the 19th Annual ACM Symposium
on Theory of Computing (STOC), pages 230–240, 1987.
[2] Baruch Awerbuch, Oded Goldreich, Ronen Vainish, and David Peleg. A trade-off between
information and communication in broadcast protocols. Journal of the ACM (JACM), 37(2):
238–256, 1990.
[3] F Chin and HF Ting. An almost linear time and o(n log n + e) messages distributed algorithm
for minimum-weight spanning trees. In Proceedings of the 26th Symposium on Foundations of
Computer Science (FOCS), pages 257–266, 1985.
[4] Richard Cole and Uzi Vishkin. Deterministic coin tossing with applications to optimal parallel
list ranking. Information and Control, 70(1):32–53, 1986.
[5] Atish Das Sarma, Stephan Holzer, Liah Kor, Amos Korman, Danupon Nanongkai, Gopal
Pandurangan, David Peleg, and Roger Wattenhofer. Distributed verification and hardness of
distributed approximation. SIAM Journal on Computing (SICOMP), 41(5):1235–1265, 2012.
[6] Michael Elkin. A faster distributed protocol for constructing a minimum spanning tree. Journal
of Computer and System Sciences, 72(8):1282–1308, 2006.
[7] Michael Elkin. An unconditional lower bound on the time-approximation trade-off for the
distributed minimum spanning tree problem. SIAM Journal on Computing (SICOMP), 36(2):
433–456, 2006.
[8] Michael Elkin. A simple deterministic distributed mst algorithm, with near-optimal time and
message complexities. Proceedings of the 36th ACM Symposium on Principles of Distributed
Computing (PODC), 2017.
[9] Michalis Faloutsos and Mart Molle. A linear-time optimal-message distributed algorithm for
minimum spanning trees. Distributed Computing, 17(2):151–170, 2004.
25

[10] Silvio Frischknecht, Stephan Holzer, and Roger Wattenhofer. Networks cannot compute their
diameter in sublinear time. In Proceedings of the 23rd Annual ACM-SIAM Symposium on
Discrete Algorithms (SODA), pages 1150–1162, 2012.
[11] Eli Gafni. Improvements in the time complexity of two message-optimal election algorithms.
In Proceedings of the 4th ACM Symposium on Principles of Distributed Computing (PODC),
pages 175–185, 1985.
[12] Robert G. Gallager, Pierre A. Humblet, and Philip M. Spira. A distributed algorithm for
minimum-weight spanning trees. ACM Transactions on Programming Languages and systems
(TOPLAS), 5(1):66–77, 1983.
[13] Juan A Garay, Shay Kutten, and David Peleg. A sublinear time distributed algorithm for
minimum-weight spanning trees. SIAM Journal on Computing (SICOMP), 27(1):302–316,
1998.
[14] Mohsen Ghaffari. Near-optimal distributed approximation of minimum-weight connected dominating set. In Proceedings of the 41nd International Colloquium on Automata, Languages and
Programming (ICALP), pages 483–494, 2014.
[15] Mohsen Ghaffari and Bernhard Haeupler. Distributed algorithms for planar networks II: Lowcongestion shortcuts, mst, and min-cut. In Proceedings of the 27th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), pages 202–219, 2016.
[16] Mohsen Ghaffari and Fabian Kuhn. Distributed minimum cut approximation. In Proceedings
of the 27th International Symposium on Distributed Computing (DISC), pages 1–15, 2013.
[17] Mohsen Ghaffari, Andreas Karrenbauer, Fabian Kuhn, Christoph Lenzen, and Boaz PattShamir. Near-optimal distributed maximum flow. In Proceedings of the 34th ACM Symposium
on Principles of Distributed Computing (PODC), pages 81–90, 2015.
√
[18] Bernhard Haeupler and Jason Li. Beating O( n + D) for distributed shortest path approximations via shortcuts. arXiv preprint arXiv:1802.03671, 2018.
[19] Bernhard Haeupler, Taisuke Izumi, and Goran Zuzic. Low-congestion shortcuts without embedding. In Proceedings of the 35th ACM Symposium on Principles of Distributed Computing
(PODC), pages 451–460, 2016.
[20] Bernhard Haeupler, Taisuke Izumi, and Goran Zuzic. Near-optimal low-congestion shortcuts on
bounded parameter graphs. In Proceedings of the 30th International Symposium on Distributed
Computing (DISC), pages 158–172, 2016.
[21] Bernhard Haeupler, Jason Li, and Goran Zuzic. Minor excluded network families admit fast
distributed algorithms. arXiv preprint arXiv:1801.06237, 2018.
[22] Stephan Holzer and Roger Wattenhofer. Optimal distributed all pairs shortest paths and applications. In Proceedings of the 31st ACM Symposium on Principles of Distributed Computing
(PODC), pages 355–364, 2012.
[23] Taisuke Izumi and Roger Wattenhofer. Time lower bounds for distributed distance oracles. In
International Conference on Principles of Distributed Systems (OPODIS), pages 60–75, 2014.
26

[24] Maleq Khan and Gopal Pandurangan. A fast distributed approximation algorithm for minimum spanning trees. In Proceedings of the 20th International Symposium on Distributed
Computing (DISC), pages 355–369, 2006.
[25] Shay Kutten and David Peleg. Fast distributed construction of k-dominating sets and applications. In Proceedings of the 14th ACM Symposium on Principles of Distributed Computing
(PODC), pages 238–251, 1995.
[26] Shay Kutten, Gopal Pandurangan, David Peleg, Peter Robinson, and Amitabh Trehan. On
the complexity of universal leader election. Journal of the ACM (JACM), 62(1):7, 2015.
[27] Christoph Lenzen and Boaz Patt-Shamir. Fast partial distance estimation and applications.
In Proceedings of the 34th ACM Symposium on Principles of Distributed Computing (PODC),
pages 153–162, 2015.
[28] Christoph Lenzen and David Peleg. Efficient distributed source detection with limited bandwidth. In Proceedings of the 32nd ACM Symposium on Principles of Distributed Computing
(PODC), pages 375–382, 2013.
[29] Ali Mashreghi and Valerie King. Time-communication trade-offs for minimum spanning tree
construction. In Proceedings of the 18th International Conference on Distributed Computing
and Networking (ICDCN), 2017.
[30] Gary L Miller, Richard Peng, and Shen Chen Xu. Parallel graph decompositions using random shifts. In Proceedings of the 25th ACM Symposium on Parallelism in Algorithms and
Architectures (SPAA), pages 196–203, 2013.
[31] Danupon Nanongkai. Distributed approximation algorithms for weighted shortest paths. In
Proceedings of the 46th Annual ACM Symposium on Theory of Computing (STOC), pages
565–573, 2014.
[32] Danupon Nanongkai and Hsin-Hao Su. Almost-tight distributed minimum cut algorithms.
In Proceedings of the 28th International Symposium on Distributed Computing (DISC), pages
439–453, 2014.
[33] Jaroslav Nešetřil, Eva Milková, and Helena Nešetřilová. Otakar borůvka on minimum spanning
tree problem translation of both the 1926 papers, comments, history. Discrete Mathematics,
233(1):3–36, 2001.
[34] Gopal Pandurangan, Peter Robinson, and Michele Scquizzato. A time- and message-optimal
distributed algorithm for minimum spanning trees. In Proceedings of the 49th Annual ACM
Symposium on Theory of Computing (STOC), pages 743–756, 2017.
[35] David Peleg. Distributed computing: a locality-sensitive approach. SIAM, 2000.
[36] David Peleg and Vitaly Rubinovich. A near-tight lower bound on the time complexity
of distributed minimum-weight spanning tree construction. SIAM Journal on Computing
(SICOMP), 30(5):1427–1442, 2000.
[37] Lucia D Penso and Valmir C Barbosa. A distributed algorithm to find k-dominating sets.
Discrete Applied Mathematics, 141(1-3):243–253, 2004.
27

[38] Daniel D Sleator and Robert Endre Tarjan. A data structure for dynamic trees. Journal of
Computer and System Sciences, 26(3):362–391, 1983.
[39] Ramakrishna Thurimella. Sub-linear distributed algorithms for sparse certificates and biconnected components. Journal of Algorithms, 23(1):160–179, 1997.

28

