Distributed Computation of Large-scale Graph Problems
Hartmut Klauck∗

arXiv:1311.6209v6 [cs.DC] 16 Sep 2015

Abstract

Danupon Nanongkai†

Gopal Pandurangan‡

Peter Robinson§

lower bound for connectivity, ST verification and other
related problems. Our lower bounds develop and use
new bounds in random-partition communication complexity.
To complement our lower bounds, we also give algorithms for various fundamental graph problems, e.g.,
PageRank, MST, connectivity, ST verification, shortest paths, cuts, spanners, covering problems, densest
subgraph, subgraph isomorphism, finding triangles, etc.
We show that problems such as PageRank, MST, connectivity, and graph covering can be solved in Õ(n/k)
time (the notation Õ hides polylog(n) factors and an additive polylog(n) term); this shows that one can achieve
almost linear (in k) speedup, whereas for shortest
paths,
√
we present algorithms that run in Õ(n/ k) time (for
(1 + ǫ)-factor approximation) and in Õ(n/k) time (for
O(log n)-factor approximation) respectively.
Our results are a step towards understanding the
complexity of distributively solving large-scale graph
problems.

Motivated by the increasing need for fast distributed
processing of large-scale graphs such as the Web graph
and various social networks, we study a number of
fundamental graph problems in the message-passing
model, where we have k machines that jointly perform a
computation on an arbitrary n-node (typically, n ≫ k)
input graph. The graph is assumed to be randomly
partitioned among the k ≥ 2 machines (a common
implementation in many real world systems). The
communication is point-to-point, and the goal is to
minimize the time complexity, i.e., the number of
communication rounds, of solving various fundamental
graph problems.
We present lower bounds that quantify the fundamental time limitations of distributively solving graph
problems. We first show a lower bound of Ω(n/k)
rounds for computing a spanning tree (ST) of the input graph. This result also implies the same bound for
other fundamental problems such as computing a minimum spanning tree (MST), breadth-first tree (BFS),
and shortest paths tree (SPT). We also show an Ω(n/k 2 ) 1 Introduction
The emergence of “Big Data” over the last decade or so
∗ Division of Mathematical Sciences, Nanyang Technological
has led to new computing platforms for distributed proUniversity, Singapore 637371 & Centre for Quantum Technolo- cessing of large-scale data, exemplified by MapReduce
gies, Singapore 117543. E-mail: hklauck@gmail.com. This work [12] and more recently systems such as Pregel [29] and
is funded by the Singapore Ministry of Education (partly through
Giraph[34]. In these platforms, the data — which is simthe Academic Research Fund Tier 3 MOE2012-T3-1-009) and by
ply too large to fit into a single machine — is distributed
the Singapore National Research Foundation.
† KTH Royal Institute of Technology, Sweden, and University
across a group of machines that are connected via a
of Vienna, Austria E-mail: danupon@gmail.com. Work done while communication network and the machines jointly proat ICERM, Brown University, USA, and Nanyang Technological cess the data in a distributed fashion. The focus of this
University, Singapore.
paper is on distributed processing of large-scale graphs
‡ Department of Computer Science, University of Houston,
Houston, TX 77204, USA. E-mail: gopalpandurangan@gmail.com. which is increasingly becoming important with the rise
Work done while at Division of Mathematical Sciences, Nanyang of massive graphs such as the Web graph, social netTechnological University, Singapore 637371 & Department of works, biological networks, and other graph-structured
Computer Science, Brown University, Providence, RI 02912, USA. data and the consequent need for fast graph algorithms
Supported in part by the following research grants: Nanyang
on such large-scale graph data. Indeed, there has been
Technological University grant M58110000, Singapore Ministry
of Education (MOE) Academic Research Fund (AcRF) Tier 2 a recent proliferation of systems designed specifically
grant MOE2010-T2-2-082, Singapore MOE AcRF Tier 1 grant for large-scale graph processing, e.g., Pregel [29], GiMOE2012-T1-001-094, and a grant from the US-Israel Binational raph [34], GraphLab [26], and GPS [1]. MapReduce
Science Foundation (BSF).
(developed at Google [12]) has become a very success§ Department of Computer Science, National University of Sinful distributed computing platform for a wide variety
gapore. E-mail: robinson@comp.nus.edu.sg. Research supported
by the grant MOE2011-T2-2-042 “Fault-tolerant Communica- of large-scale computing applications and also has been
tion Complexity in Wireless Networks” from the Singapore MoE used for processing graphs [25]. However, as pointed out
AcRF-2.

by the developers of Pregel (which was also developed
at Google), MapReduce may sometimes be ill-suited for
implementing graph algorithms; it can lead to “suboptimal performance and usability issues” [29]. On the
other hand, they mention that graph algorithms seem
better suited to a message-passing distributed computing model [33, 28] and this is the main design principle
[29] behind Pregel (and other systems that followed it
such as Giraph [34] and GPS [1]). While there is a rich
theory for the message-passing distributed computing
model [33, 28], such a theory is still in its infancy for
distributed graph processing systems.
In this work, our goal is to investigate a theory for
large-scale graph computation based on a distributed
message-passing model. A fundamental issue that we
would like to investigate is the amount of “speedup”
possible in such a model vis-a-vis the number of machines used: more precisely, if we use k machines, does
the run time scale linearly (or even super-linearly) in k?
And what are the fundamental time bounds for various
graph problems?
1.1 Model We consider a network of k > 1 (distinct)
machines N = {p1 , . . . , pk } that are pairwise interconnected by bidirectional point-to-point communication
links — henceforth called the k-machine model1 . Each
machine executes an instance of a distributed algorithm
A. The computation advances in synchronous rounds
where, in each round, machines can exchange messages
over their communication links. Each link is assumed to
have a bandwidth of W , i.e., W bits can be transmitted
over the link in one round. (In stating our time bounds,
for convenience, we will assume that bandwidth W = 1;
in any case, it is easy to rewrite our upper bounds to
scale in terms of parameter W — cf. Theorem 4.1).
(Note that machines have no other means of communication and do not share any memory.) There is an
alternate — but equivalent — way to view our communication restriction: instead of putting bandwidth
restriction on the links, we can put a restriction on the
amount of information that each machine can communicate (i.e. send/receive) in a round. The results that
we obtain in the bandwidth-restricted model will also
apply to the latter model (cf. Section 4.2). Local computation within a machine is considered free, while communicating messages between the machines is the costly
operation2 .
1 Our results can also be generalized to work if the communication network is a sparse topology as well if one assumes an
underlying routing mechanism; details are omitted here.
2 This assumption is reasonable in the context of large-scale
data, e.g., it has been made in the context of theoretical analysis
of MapReduce, see e.g., [35] for a justification. Indeed, typically

We are interested in solving graph problems where
we are given an input graph G of n vertices (assume
that each vertex has a unique label) and m edges
from some input domain G. To avoid trivialities, we
will assume that n ≥ k (typically n ≫ k). Unless
otherwise stated, we will consider G to be undirected,
although all our results can be made to apply in
a straightforward fashion to directed graphs as well.
Initially, the entire graph G is not known by a single
machine, but rather partitioned among the k machines
in a “balanced” fashion, i.e., the nodes and/or edges
of G must be partitioned approximately evenly among
the machines. We will assume a vertex-partition model,
where vertices (and their incident edges) are partitioned
across machines. One type of partition that we will
assume throughout is the random (vertex) partition, i.e.,
vertices (and its incident edges) of the input graph are
assigned randomly to machines. (This is the typical
way that many real systems (e.g., Pregel) partition
the input graph among the machines; it is simple and
and easy to accomplish, e.g., via hashing 3 .) Our
upper bounds will also hold (with slight modifications)
without this assumption; only a “balanced” partition of
the input graph among the machines is needed. On
the other hand, our lower bounds apply even under
random partitioning, hence they apply to worst-case
partition as well. It can be shown that (cf. Lemma 4.1)
a random partition gives rises to an (approximately)
balanced partition.
Formally, in the random vertex partition (RVP)
model, each vertex of G is assigned independently and
randomly to one of the k machines. If a vertex v is
assigned to machine pi we call pi the home machine of
v. Note that when a vertex is assigned to a machine, all
its incident edges are assigned to that machine as well;
i.e., the home machine will know the labels of neighbors
of that vertex as well as the identity of the home
machines of the neighboring vertices. A convenient way
to implement the above assignment is via hashing: each
vertex (label) is hashed to one of the k machines. Hence,
if a machine knows a vertex label, it also knows where
it is hashed to.
Depending on the problem P, the vertices and/or
edges of G have labels chosen from a set of polynomial
(in n) size. Eventually, each machine pi (1 ≤ i ≤ k)
in practice, even assuming the links have a bandwidth of order of
gigabytes of data per second, the amount of data that have been
to be communicated can be in order of tera or peta bytes which
generally dominates the overall computation cost [35].
3 Partitioning based on the structure of the graph — with the
goal of minimizing the amount of communication between the
machines — is non-trivial; finding such a “good” partition itself
might be prohibitively expensive and can be problem dependent.
Some papers address this issue, see e.g., [40, 3, 39].

must (irrevocably) set a designated local output variable oi (which will depend on the set of vertices assigned to machine pi ) and the output configuration
o = ho1 , . . . , ok i must satisfy certain feasibility conditions w.r.t. problem P. For example, when considering the minimum spanning tree (MST) problem, each
oi corresponds to a set of edges (which will be a subset of edges incident on vertices mapped to machine)
pi and the edges in the union of the sets oi must form
an MST of the input graph G; in other words, each
machine pi will know all the MST edges incident on
vertices mapped to pi . (Note that this is a natural generalization of the analogous assumption in the standard
distributed message passing model, where each vertex
knows which of its incident edges belong to the MST
[33].) We say that algorithm A solves problem P if A
maps each G ∈ G to an output configuration that is feasible for P. The time complexity of A is the maximum
number of rounds until termination, over all graphs in
G. In stating our time bounds, for convenience, we will
assume that bandwidth W = 1; in any case, it is easy to
rewrite our upper bounds to scale in terms of parameter
W (cf. Theorem 4.1).
Notation. For any 0 ≤ ǫ ≤ 1, we say that a protocol
has ǫ-error if, for any input graph G, it outputs the
correct answer with probability at least 1 − ǫ, where
the probability is over the random partition and the
random bit strings used by the algorithm (in case it is
randomized).
For any n > 0 and function T (n), we say that an
algorithm A terminates in O(T (n)) rounds if, for any nnode graph G, A always terminate in O(T (n))) rounds,
regardless of the choice of the (random) input partition.
For any n and problem P on n node graphs, we let
the time complexity of solving P with ǫ error probability
in the k-machine model, denoted by Tǫk (P), be the
minimum T (n) such that there exists an ǫ-error protocol
that solves P and terminates in T (n) rounds. For any
0 ≤ ǫ ≤ 1, graph problem P and function T : Z+ → Z+ ,
we say that Tǫk (P) = O(T (n)) if there exists integer
n0 and c such that for all n ≥ n0 , Tǫk (P) ≤ cT (n).
Similarly, we say that Tǫk (P) = Ω(T (n)) if there exists
integer n0 and real c such that for all n ≥ n0 , Tǫk (P) ≥
cT (n). For our upper bounds, we will usually use
ǫ = 1/n, which will imply high probability algorithms,
i.e., succeeding with probability at least 1 − 1/n. In this
case, we will sometimes just omit ǫ and simply say the
time bound applies “with high probability”. We use ∆
to denote the maximum degree of any node in the input
graph, and D for the diameter of the input graph.

of distributed “rounds”, for solving various fundamental
graph problems. The time complexity not only captures
the (potential) speed up possible for a problem, but it
also implicitly captures the communication cost of the
algorithm as well, since links can transmit only a limited
amount of bits per round; equivalently, we can view our
model where instead of links, machines can send/receive
only a limited amount of bits per round. We develop
techniques to obtain non-trivial lower and upper bounds
on the time complexity of various graph problems.

Lower Bounds. Our lower bounds quantify the fundamental time limitations of distributively solving graph
problems. They apply essentially to distributed data
computations in all point-to-point communication models, since they apply even to a synchronous complete
network model where the graph is partitioned randomly
(unlike some previous results, e.g., [41], which apply
only under some worst-case partition).
We first give a tight lower bound on the complexity of computing a spanning tree (cf. Section 2). The
proof shows that Ω(n/k) rounds of communication are
needed even for unweighted and undirected graphs of
diameter 2, and even for sparse graphs. We give an
information theoretic argument for this result. This result also implies the same bound for other fundamental
problems such as computing a minimum spanning tree,
breadth-first tree, and shortest paths tree. This bound
shows that one cannot hope to obtain a run time that
scales (asymptotically) faster than 1/k. This result, in
conjunction with our upper bound of Õ(n/k) for computing a MST, shows that this lower bound is essentially
tight.
We then show an Ω(n/k 2 ) lower bound for connectivity, spanning tree (ST) verification and other related
verification problems (cf. Section 3). To analyze the
complexity of verification problems we give reductions
from problems in the 2-player communication complexity model using random partitions of the input variables.
As opposed to the standard fixed partition model here
all input bits are randomly assigned to Alice and Bob.
We give a tight lower bound for randomized protocols
for the well-studied disjointness problem in this setting.
In particular, we show a lower bound on the randomized
average partition communication complexity of the disjointness problem which might be of independent interest. Random partition communication complexity has
also been studied by Chakrabarti et al. [8], but their
results apply to the promise disjointness problem in the
multiparty number in hand model for a sufficiently large
number of players only. In our proof we apply the rectangle based arguments of Razborov [36], but we need
1.2 Our Results and Techniques Our main goal
to take care of several issues arising. A core ingrediis to investigate the time complexity, i.e., the number
ent of Razborov’s proof is the conditioning that turns

the input distribution into a product distribution. With
randomly assigned inputs we need to recover the necessary product properties by conditioning over badly
assigned input bits. Even when doing so the size of the
sets in the input are no longer exactly as in Razborov’s
proof. Furthermore, there is a large probability that the
set intersection is visible to a single player right from
the start, but with a small enough error probability the
communication still needs to be large.

pute exact shortest paths, this might take significantly
longer (e.g., using Bellman-Ford — cf. Section 4.3). For
graph covering problems such a Maximal Independent
Set (MIS) and (approximate) Minimum Vertex cover
(MVC), we show a bound of Õ(min(n/k, m/k 2 + ∆/k));
note that this implies a bound of Õ(n/k 2 ) for (constant)
bounded degree graphs, i.e., we can get a speed up that
scales superlinearly in k.
We finally note that our results also directly apply
to an alternate (but equivalent) model, where instead
Algorithms and Upper Bounds. We introduce techof having a restriction on the number of bits individual
niques to obtain fast graph algorithms in the k-machine
links can transmit in a round, we restrict the number
model (cf. Section 1.1). We first present a general reof bits a machine can send/receive (in total) per round
sult, called the Conversion Theorem (cf. Theorem 4.1)
(cf. Section 4.2).
that, given a graph problem P, shows how fast algorithms for solving P in the k-machine model can be
1.3 Related Work The theoretical study of (largedesigned by leveraging distributed algorithms for P in
scale) graph processing in distributed systems is relathe standard CONGEST message-passing distributed
tively recent. Several works have been devoted to decomputing model (see e.g., [33]). We note that fast
veloping MapReduce graph algorithms (e.g., see [25, 35]
distributed algorithms in the standard model do not diand the references therein). There also have been sevrectly imply fast algorithms in the k-machine model. To
eral recent theoretical papers analyzing MapReduce alachieve this, we consider distributed algorithms in an ingorithms in general, including Mapreduce graph algotermediate clique model (cf. Section 4.2) and then show
rithms see e.g., [24, 35, 19] and the references therein.
two ways — parts (a) and (b) respectively of the ConWe note that the flavor of theory developed for MapReversion Theorem — to efficiently convert algorithms in
duce is quite different compared to the distributed comthe clique model to the k-machine model. Part (b) applexity results of this paper. Minimizing communicaplies to converting distributed algorithms (in the clique
tion (which leads in turn to minimizing the number of
model) that only uses broadcast, while part (a) applies
communication rounds) is a key motivation in MapReto any algorithm. Part (a) will sometimes give better
duce algorithms (e.g., see [35]); however this is gentime bounds compared to part (b) and vice versa —
erally achieved by making sure that the data is made
this depends on the problem at hand and the type of
small enough quickly (in a small number of MapReduce
distributed algorithm considered, as well as on the graph
rounds) to fit into the memory of a single machine. An
parameters. (The latter can be especially useful in apexample of this idea is the filtering technique of [24] applications where we might have some information on the
plied to graph problems. The main idea behind filtering
graph parameters/topology as explained below.) Using
is to reduce the size of the input in a distributed fashion
this theorem, we design algorithms for various fundaso that the resulting, much smaller, problem instance
mental graph problems, e.g., PageRank, minimum spancan be solved on a single machine. Filtering allows for
ning tree (MST), connectivity, spanning tree (ST) vera tradeoff between the number of rounds and the availification, shortest paths, cuts, spanners, covering probable memory. Specifically, the work of [24] shows that
lems, densest subgraph, subgraph isomorphism, Trianfor graphs with at most n1+c edges and machines with
gle finding (cf. Table 1). We show that problems such as
memory at least n1+ε will require O(c/ǫ) (MapReduce)
PageRank, MST, and connectivity, graph covering etc.
rounds.
can be solved in Õ(n/k) time; this shows that one can
The work that is closest in spirit to ours is the reachieve almost linear (in k) speedup. For graph conneccent work of [41]. The above work considers a number
tivity, BFS tree construction, and ST verification, we
of basic statistical and graph problems in the messageshow Õ(min(n/k, m/k 2 + D∆/k)) bound — note that
passing model (where the data is distributed across a set
the second part of the above bound may be better in
of machines) and analyzes their communication comsome cases, e.g., if the graph is sparse (i.e., m = O(n))
plexity — which denotes the total number of bits exand D and ∆ are small (e.g., bounded by O(log n))
changed in all messages across the machines during a
2
— then we get a bound of Õ(n/k ). For single-source
computation. Their main result is that exact compushortest paths, another classic
√ and important problem, tation of many statistical and graph problems in the
we show a bound of Õ(n/ k) for a (1 + ǫ)-factor apdistributed setting is very expensive, and often one canproximation and a bound of Õ(n/k) for O(log n)-factor
not do better than simply having all machines send
approximation. We note that if one wants to com-

Problem

Upper Bound

Lower Bound

Minimum Spanning Tree (MST)
Connectivity, Spanning Tree Verification (Conn,ST)
Breadth First Search Tree (BFS)
Single-Source Shortest-Paths Distances (SSSP)
Single-Source Shortest-Paths Tree (SPT)
All-Pairs Shortest-Paths Distances (APSP)
PageRank with reset prob. γ (PageRank)
Graph Covering Problems (MIS, MVC)
Maximal Ind. Set on Hypergraphs (HMIS)
(2δ − 1)-Spanner (Spanner) (δ ∈ O(log n))
Densest Subgraph (DSGraph)
Triangle Verification (Tri)
Subgraph Isomorphism (SubIso) (d-vertex subgraph)

Õ(n/k)
Õ(min(n/k, m/k 2 + D⌈∆/k⌉))
2
Õ(min(n/k
+ D⌈∆/k⌉))
√ † + D, m/k
$
Õ(n/√k) , Õ(n/k)
Õ(n/ k)† , Õ(n/k)$
√
Õ(n n/k)# , Õ(n/k)$
Õ(n/γk)
Õ(min(n/k, m/k 2 + ∆/k))
Õ(n/k + k)
Õ(n/k)
Õ(n/k) (for (2 + ǫ)-approx.)
Õ(min(n∆2 /k 2 + ∆⌈∆/k⌉, n7/3 /k 2 + n4/3 /k))
Õ(n2+(d−2)/d /k 2 + n1+(d−2)/d /k)

Ω̃(n/k)∗
Ω̃(n/k 2 )
Ω̃(n/k)

†

(1 + ǫ)-approximation.

#

(2 + ǫ)-approximation.

$

O(log n)-approximation.

∗

Ω̃(n/k)∗

For any approx. ratio.

Table 1: Complexity bounds in the k-machine model for an n-node input graph with m edges, max degree ∆, and diameter
D. ǫ > 0 is any small constant. The notation Õ hides polylog(n) factors and an additive polylog(n) term. For clarity of
presentation, we assume a bandwidth of Θ(log n) bits.
their data to a centralized server. The graph problems considered are computing the degree of a vertex,
testing cycle-freeness, testing connectivity, computing
the number of connected components, testing bipartiteness, and testing triangle-freeness. The strong lower
bounds shown for these assume a worst-case distribution of the input (unlike ours, which assumes a random
distribution). They posit that in order to obtain protocols that are communication-efficient, one has to allow
approximation, or investigate the distribution or layout
of the data sets and leave these as open problems for
future. Our work, on the other hand, addresses time
(round) complexity (this is different from the notion of
round complexity defined in [41]) and shows that nontrivial speed up is possible for many graph problems.
As posited above, for some problems such as shortest
paths and densest subgraph etc., our model assumes
a random partition of the input graph and also allows
approximation to get good speedup, while for problems
such as MST we get good speedups for exact algorithms
as well. For spanning tree problems we show tight lower
bounds as well.
The k-machine model is closely related to the wellstudied (standard) message-passing CONGEST model
[33], in particular to the CONGEST clique model (cf.
Section 4). The main difference is that while many vertices of the input graph are mapped to the same machine in the k-machine model, in the standard model
each vertex corresponds to a dedicated machine. More
“local knowledge” is available per vertex (since it can
access for free information about other vertices in the

same machine) in the k-machine model compared to the
standard model. On the other hand, all nodes assigned
to a machine have to communicate through the links
incident on this machine, which can limit the bandwidth (unlike the standard model where each vertex has
a dedicated processor). These differences manifest in
the time complexity — certain problems have a faster
time complexity in one model compared to the other
(cf. Section 4). In particular, the fastest known distributed algorithm in the standard model for a given
problem, may not give rise to the fastest algorithm in
the k-machine model. Furthermore, the techniques for
showing the complexity bounds (both upper and lower)
in the k-machine model are different compared to the
standard model. The recently developed communication complexity techniques (see e.g, [37, 32, 15]) used to
prove lower bounds in the standard CONGEST model
are not applicable here.
2

Tight Lower Bounds for Spanning Tree
Computation

In this section, we show that any ε-error algorithm takes
Ω(n/k) rounds to compute a spanning tree (STC). Recall
that in the STC problem, for every edge uv, the home
machines of u and v must know whether uv is in the ST
or not.
Theorem 2.1. (Lower bound for STC) Every
public-coin ǫ-error randomized protocol on a k-machine
network that computes a spanning tree of an n-node
input graph has an expected round complexity of


More specifically, there exists a constant
Ω nk .
ǫ > 0 such that, for any k ≥ 3 and large enough
n,

Tǫk (STC), Tǫk (MST), Tǫk (BFS), Tǫk (SPT) ∈ Ω nk .

Observation 1. For any X, Y chosen as described
above, and all 1 ≤ i ≤ b such that Xi = Yi = 1 exactly
one of the edges uvi or vi w must be part of any spanning
tree, except for exactly one such i, for which both edges
Proof. We first show the theorem for Tǫk (STC) using are in the spanning tree. For all other i the one edge uvi
an information theoretic argument. Assume for a or vi w that is in the graph must also be in the spanning
contradiction that there exists a distributed algorithm tree.
in the k-machine model, denoted by R, that violates
Theorem 2.1. In other words, R solves STC correctly
Since all edges are adjacent to either u or w, and
with probability at least 1 − ǫ and always terminates in any spanning tree must have b + 1 edges, one of p1 or p2
δn
k rounds, for some δ ∈ o(1). We will show that the must output at most b/2 edges. Before the first round
information flow to at least one machine must be large. of communication the entropy H(Y |X) is 2b/3 by the
following calculation:
Graph Gb (X, Y ). Let b = n − 2. For any X, Y ⊆ [b],
X
we construct the following graph, denoted by Gb (X, Y ).
H(Y
|X)
=
Pr(X = x) · H(Y |X = x)
The vertices (and adjacent edges of Gb (X, Y )) will be
x
assigned to a random machine.
b  
X
Gb (X, Y ) consists of b + 2 nodes, denoted by
b ℓ
= 3−b
2 · log 2ℓ
v1 , . . . , vb and u, w. For each 1 ≤ i ≤ b, we add edge uvi
ℓ
ℓ=0
to Gb (X, Y ) if i ∈ X, and we add edge vi w to Gb (X, Y )

b−1 
X
b − 1 ℓ+1
if i ∈ Y .
= 3−b b
2
The random strings X, Y will be drawn from a disℓ
ℓ=0
tribution that will ensure that Gb (X, Y ) is connected.
= 2b/3.
Furthermore the graph will contain roughly 4b/3 edges
with high probability (2b/3 adjacent to u, w respectively), hence roughly b/3 edges must be removed to
Besides X the machine p1 also knows some vertices
obtain a spanning tree.
vi and their edges, giving it access to some bits of Y .
To produce the correct output in R the machine
It is easy to see via the Chernoff bound that with very
that receives u must know which edges uvi are included
high probability p1 knows at most (1 + ζ)b/k bits of
in the spanning tree, and similarly the machine that
Y for ζ = 0.01, lowering the conditional entropy of Y
receives w must know which edges vi w are included
given those bits to no less than 2b/3 − (1 + ζ)b/k. The
in the spanning tree. Since X, Y are encoded in the
event where p1 knows more cannot influence the entropy
graph, the machine p1 who receives u knows X via
2
by more than 2−ζ b/(3k) · b = o(1) (for b large enough).
the edges uvi at the start, but has initially limited
Hence the entropy of Y given the initial information
information about Y , unless it also receives w, which
of p1 , which we denote by a random variable A, is
happens with probability 1/k. With probability 1 − 1/k
H(Y |A) ≥ 2b/3 − (1 + ζ)b/k − o(1).
the information about Y initially held by p1 comes from
Assume that p1 outputs at most b/2 edges. This
the set of vertices vi held by p1 which is of size ≈ b/k
event or the corresponding event for p2 must happen
with high probability, giving p1 at most ≈ b/k bits of
with probability 1 − ǫ assuming failure probability ǫ.
information about Y . Hence all information needed to
Conditioned on the event that p1 outputs b/2 or fewer
decide which edges to not include must come into p1 via
edges we can estimate the entropy H(Y |A, T0 ) for the
communication with the other k − 1 machines. We show
random variable T0 containing the transcript of all
that this communication is Ω(b), if p1 outputs at most
messages to p1 . H(Y |A, T0 ) ≤ H(Y |X, E) where E is
b/2 edges as part of the spanning tree (and a symmetric
the random variables of edges in the output of p1 (we
argument holds for the machine p2 that holds w). Hence
use that X and E can be computed from A, T0 ). Given
the number of rounds is Ω(b/k) = Ω(n/k).
that X = x there are |x| possible edges for E. With
In order to give a clean condition on which edges
probability 1 − o(1) we have |y| < 2b/3 + ζb.
are necessary for a spanning tree we use the following
For at most b/2 edges in E there are at most
distribution on X, Y . X, Y (viewed as characteristic
b
b


vectors) are chosen uniformly from {0, 1} × {0, 1}
X b/2
b/2
under the condition that for every i ∈ [b] we have
≤b·
ℓ
b/6 + ζb
Xi + Yi ≥ 1. Hence there are exactly 3b possible values
ℓ<b/6+ζb
for X, Y . The following simple observation is crucial to
our proof.
possibilities for Y = y such that |y| ≤ 2b/3 + ζb. Hence

we can estimate the remaining entropy of Y as follows:


b/2
H(Y |X, E) ≤ Pr(|Y | < 2b/3 + ζb)(log
b/6 + ζb
+ log b) + o(1)

n
o( k2 log
n ) expected rounds, and no (ǫ, ǫ)-error protocol
n
that solves Conn correctly in o( k2 log
n ) rounds.

To prove Theorem 3.1, we introduce a new
model called random-partition (two-party) communication complexity and prove some lower bounds in this
≤ H(1/3 + 2ζ)b/2 + o(b)
model. This is done in Section 3.1. We then use these
for the binary entropy function H. For k ≥ 7 we lower bounds to show lower bounds for the k-machine
can simply use the upper bound b/2 for the above model in Sections 3.1.1 and 3.1.2.
quantity and conclude that I(T0 : Y |A) = H(Y |A) −
H(Y |A, T0 ) ≥ 2b/3 − (1 + ζ)b/k − o(1) − b/2 ≥ Ω(b), and 3.1 Random-Partition Communication Comhence p1 must have received messages of length Ω(b). plexity We first recall the standard communication
This happens with some probability γ for p1 and with complexity model, which we will call worst-partition
probability (1 − ǫ) − γ for p2 . Hence |T0 | + |T1 | ≥ Ω(b). model, to distinguish it from our random-partition
The above analysis is under the assumption that model. (For a comprehensive review of the subject, we
different machines hold u, w, which happens with proba- refer the reader to [22].)
In the worst-partition communication complexity
bility 1 − 1/k. Without this assumption the information
model,
there are two players called Alice and Bob.
flow must be at least (1 − 1/k) · Ω(b).
Each
player
receives a b-bit binary string, for some
For k < 7 we need to make a more careful analysis.
integer
b
≥
1. We denote the string received by
For instance, p1 actually gets only around 2b/(3k) bits
Alice
and
Bob
by x and y respectively. Together, they
of information from knowing b/k bits of Y , and the
both
want
to
compute
f (x, y) for a Boolean function
estimate on H(Y |A, E) needs to be made more precise.
b
b
f
:
{0,
1}
×
{0,
1}
→
{0, 1}. At the end of the
We skip the details.
This completes the proof of

n
k
process,
we
want
both
Alice
and Bob to know the value
Tǫ (STC) = Ω k .
of
f
(x,
y).
We
are
interested
in the number of bits
To
see
that
this
also
implies

n
k
k
k
exchanged
between
Alice
and
Bob
in order to compute
Tǫ (MST), Tǫ (BFS), Tǫ (SPT) ∈ Ω k , it is suffif
.
We
say
that
a
protocol
R
has
complexity t if it
cient to observe that any BFS tree (resp. MST, and
4
always
uses
at
most
t
bits
in
total
.
For any function
SPT, for any approximation ratio) is also a spanning
f
,
the
worst-partition
communication
complexity for
tree.
(f ),
computing f with (ǫ0 , ǫ1 )-error, denoted by Rǫcc−pub
0 ,ǫ1
is
the
minimum
t
such
that
there
is
an
(ǫ
,
ǫ
)-error
0
1
3 Lower Bounds for Verification Problems
protocol with complexity t. (Note that a protocol is
In this section, we show lower bounds for the spanning
(ǫ0 , ǫ1 )-error if it outputs 0 with probability at least
tree (ST) and connectivity (Conn) verification problems.
1 − ǫ0 when f (x, y) = 0 and outputs 1 with probability
An algorithm solves the Conn verification problem in
at least 1 − ǫ1 when f (x, y) = 1.)
our model if the machines output 1 if and only if the
The random-partition model is slightly different
input graph G is connected; the ST problem is defined
from the worst-partition model in that, instead of giving
similarly. We note that our lower bounds hold even
every bit of x to Alice and every bit of y to Bob, each
when we allow shared randomness, i.e. even when all
of these bits are sent to one of the players randomly.
machines can read the same random string. For a
To be precise, let xi be the ith bit of x and yi be the
problem P where a two-sided error is possible, we define th
i bit of y. For any pair of input strings (x, y), we
the time complexity of solving P with (ǫ0 , ǫ1 ) error
partition it by telling the value of each xi and yi (by
k
probabilities, denoted by Tǫ0 ,ǫ1 (P), be the minimum
sending a message of the form “xi = 0” or “xi = 1”)
T (n) such that there exists a protocol that solves
to a random player. As before, we say that a protocol
P, terminates in T (n) rounds, and errs on 0-input
R has complexity t if it always uses at most t bits in
with probability at most ǫ0 and errs on 1-input with
total, regardless of the input and its partition. We note
probability at most ǫ1 .
that the error probability of a protocol R is calculated
over all possible random choices made by the algorithm
Theorem 3.1. (ST verification and Conn) There
exists a constant ǫ > 0 such that,
 for any kk ≥ 2 and
k
and Tǫ,ǫ (Conn) =
large enough n, Tǫ,0
(ST) = Ω̃ kn2

Ω̃ kn2 . In other words, there is no public-coin (ǫ, 0)error randomized protocol on a k-machine model that,
on any n-node input graph, solves ST correctly in

4 We

emphasize that we allow R to incur at most t bits of
communication regardless of the input and random choices made
by the protocol. We note a standard fact that one can also define
the complexity t to be the expected number of bits. The two
notions are equivalent up to a constant factor.

and all possible random partitions; e.g., it is possible
that an (ǫ0 , ǫ1 )-error protocol never answers a correct
answer for some input partition. Also note that, while
we pick the input partition randomly, the input pair
itself is picked adversarially. In other words, an (ǫ0 , ǫ1 )error protocol must, for any input (x, y), output 0 with
probability at least 1 − ǫ0 when f (x, y) = 0 and output
1 with probability at least 1 − ǫ1 when f (x, y) = 1,
where the probability is over all possible random strings
given to the protocol and the random partition. For
any function f , the random-partition communication
complexity for computing f with (ǫ0 , ǫ1 )-error, denoted
(f ), is the minimum t such that there is an
by Rǫrcc−pub
0 ,ǫ1
(ǫ0 , ǫ1 )-error protocol with complexity t.
The problems of our interest are equality and disjointness. In the rest of Section 3.1, we show that the
communication complexity of these problems are essentially the same in both worst-partition and randompartition models. The techniques used to prove these results are different between the two problems, and might
be of an independent interest.
3.1.1 ST Verification and Random-Partition
Communication Complexity of Eq. The equality
function, denoted by eq, is defined as eq(x, y) = 1
if x = y and eq(x, y) = 0 otherwise. Note that
this problem can be solved by the fingerprinting technique which makes a small error only when x 6= y, i.e.
cc−pub
Rǫ,0
(eq) = O(log b) (see, e.g. [22]). Interestingly, if
we “switch” the error side, the problem becomes hard:
cc−pub
R0,ǫ
(eq) = Ω(b). We show that this phenomenon remains true in the random-partition setting. Lemma 3.1
is proved in Appendix B.
Lemma 3.1. (Random-Partition Equality) For
rcc−pub
some ǫ > 0, R0,ǫ
(eq) = Ω(b). This lower bound
holds even when Alice knows x and Bob knows y.
Lower bound for ST verification. We now show a
lower bound of Ω̃(n/k 2 ) on (0, ǫ)-error algorithms for
ST verification. For the b-bit string inputs x and y of
the equality problem, we construct the following graph
G(x, y): The nodes are u0 , . . . , ub and v0 , . . . , vb . For
any i, there is an edge between u0 and ui if and only if
xi = 1, and there is an edge between v0 and vi if and
only if yi = 0. Additionally, there is always an edge
between uj and vj , for 0 ≤ j ≤ b. Observe that G(x, y)
is a spanning tree if and only if x = y. Also note that
G(x, y) has n = Θ(b) nodes.
Now assume that there is a (0, ǫ)-error algorithm R
in the k-machine model that finishes in õ(n/k 2 ) rounds.
Alice and Bob simulate R as follows. Let p1 , . . . , pk
be machines in the k-machine model, and assume that

k is even. First, Alice and Bob generate a random
partition of nodes in G(x, y) using the random partition
of input (x, y) and shared randomness. Using shared
randomness, they decide which machine the nodes u0
and v0 should belong to. Without loss of generality,
we can assume that u0 belongs to p1 . Moreover, with
probability 1 − 1/k, v0 is not in p1 , and we can assume
that v0 is in p2 without loss of generality. (If u0 and
v0 are in the same machine then Alice and Bob stop
the simulation and output 0 (i.e. x 6= y).) Alice will
simulate machines in PA = {p1 , p3 , p5 . . . , pk−1 } and
Bob will simulate machines in PB = {p2 , p4 , . . . , pk }.
This means that Alice (Bob respectively) can put and
get any information from PA (PB respectively) with no
cost. At this point, Alice assigns node u0 on p1 ; i.e., she
tells p1 whether ui has an edge to u0 or not, for all i (this
can be done since she knows x). Similarly, Bob assigns
node v0 on p2 . (Note that to do this we need Alice to
know x and Bob to know y in addition to the random
partition of x and y. We have the lower bound of this as
claimed in Lemma 3.1.) Next, they randomly put every
node in a random machine. For any i, if Alice gets xi ,
then she assigns ui in a random machine in PA , i.e., she
tells such a random machine whether ui has an edge to
u0 or not. Otherwise, Bob puts ui in a random machine
in PB in the same way. Since each xi and yi belongs to
Alice with probability 1/2, it can be seen that each ui
and vi will be assigned to a random machine. Similarly,
node vi is assigned to a random machine depending on
who gets yi . Note that both Alice and Bob know which
machine each node is assigned to since they use shared
randomness.
Now Alice and Bob simulate R where Alice simulates R on machines in PA and Bob simulates R on
machines in PB . To keep this simulation going, they
have to send messages to each other every time there is
a communication between machines in PA and PB . This
means that they have to communicate Õ(k 2 ) bits in each
round of R. Since R finishes in õ(n/k 2 ) rounds, Alice
and Bob have to communicate õ(n) = õ(b) bits. Once
they know whether G(x, y) is an ST or not, they can answer whether x = y or not. Since R is (0, ǫ)-error, Alice
and Bob’s error will be (0, ǫ + 1/k), where the extra 1/k
term is because they answer 0 when u0 and v0 are in the
same machine. For large enough k, this error is smaller
than the error in Lemma 3.1, contradicting Lemma 3.1.
This implies that such an algorithm R does not exist.
3.1.2 Conn and Random-Partition Communication Complexity of Disjointness The disjointness
function, denoted by disj, is defined as disj(x, y) = 1
if there is i such that xi = yi and disj(x, y) = 0 otherwise. This problem in the worst-partition model is

a fundamental problem in communication complexity,
having tons of application (e.g. [9]). Through a series of results (e.g. [2, 4, 7, 18, 36]), it is known that
cc−pub
Rǫ,ǫ
(disj) = Ω(b). By adapting the previous proof
of Razborov [36], we show that this lower bound remains true in the random-partition setting. Lemma 3.2
is proved in Appendix A.

machine each node is assigned to since they use shared
randomness.
Now Alice and Bob simulate R where Alice simulates R on machines in PA and Bob simulates R on
machines in PB . To keep this simulation going, they
have to send messages between each other every time
there is a communication between machines in PA and
PB . This means that they have to communicate Õ(k 2 )
Lemma 3.2. (Random-Partition Disjointness)
bits in each round of R. Since R finishes in õ(n/k 2 )
rcc−pub
For some ǫ > 0, Rǫ,ǫ
(disj) = Ω(b). This lower
rounds, Alice and Bob have to communicate õ(n) = õ(b)
bound holds even when Alice knows x and Bob knows y.
bits. Once they know whether G(x, y) is connected or
not, they can answer whether x and y are disjoint or
Lower bound for Conn verification. We now show
not. Since R is (ǫ, ǫ)-error, Alice and Bob’s error will
a lower bound of Ω̃(n/k 2 ) on (ǫ, ǫ)-error algorithms for
be (ǫ, ǫ+ 1/k), where the extra 1/k term is because they
Conn verification, for a small enough constant ǫ > 0.
answer 0 when u0 and v0 are in the same machine. For
For the b-bit string inputs x and y of the disjointness
large enough k, this error is smaller than the error in
problem, we construct the following graph G(x, y): The
Lemma 3.2, contradicting Lemma 3.2. This implies that
nodes are u0 , . . . , ub and v0 , . . . , vb . For any i, there
such an algorithm R does not exist.
is an edge between u0 and ui if and only if xi = 0,
and there is an edge between v0 and vi if and only if
4 Algorithms and Techniques
yi = 0. Additionally, there is always an edge between
uj and vj , for 0 ≤ j ≤ b. Observe that G(x, y) is 4.1 A Mapping Lemma We first prove a “mapconnected if and only if x and y are disjoint. Also ping” lemma for the random vertex partition model,
note that G(x, y) has n = Θ(b) nodes. Assume that which we will use in our Conversion theorem (cf. Thethere is an (ǫ, ǫ)-error algorithm R in the k-machine orem 4.1). Consider an input graph G = (V, E) that is
model that finishes in õ(n/k 2 ) rounds. Alice and Bob partitioned (according to the random vertex partition
simulate R as follows. Let p1 , . . . , pk be machines in model) among the k machines in N = {p1 , . . . , pk } of
the k-machine model, and assume that k is even. First, the network. Let |V | = n and |E| = m. We will assume
Alice and Bob generate a random partition of nodes (without loss of generality) throughout that n ≥ k. We
in G(x, y) using the random partition of input (x, y) say that a vertex v of G is mapped to a machine h of
and shared randomness. Using shared randomness, they N if v is assigned to N , i.e., h is the home machine of
decide which machine the nodes u0 and v0 should belong v (cf. Section 1.1). We say that an edge e = (u, v) of G
to. Without loss of generality, we can assume that u0 is mapped to a link (pi , pj ) of the k-machine network, if
belongs to p1 . Moreover, with probability 1 − 1/k, v0 is u is mapped to pi and v is mapped to vj or vice versa.
not in p1 , and we can assume that v0 is in p2 without loss The following Mapping Lemma gives a concentration
of generality. (If u0 and v0 are in the same machine then bound on the number of edges mapped to any link of
Alice and Bob stop the simulation and output 0.) Alice the network.
will simulate machines in PA = {p1 , p3 , p5 . . . , pk−1 } and
Bob will simulate machines in PB = {p2 , p4 , . . . , pk }.
This means that Alice (Bob respectively) can put and
get any information from PA (PB respectively) with no
cost. At this point, Alice assigns node u0 on p1 ; i.e.,
she tells p1 whether ui has an edge to u0 or not, for all
i (this can be done since she knows x). Similarly, Bob
assigns node v0 on p2 . Next, they randomly put every
node in a random machine. For any i, if Alice gets xi ,
then she assigns ui in a random machine in PA , i.e., she
tells such a random machine whether ui has an edge to
u0 or not. Otherwise, Bob puts ui in a random machine
in PB in the same way. Since each xi and yi belongs to
Alice with probability 1/2, it can be seen that each ui
and vi will be assigned to a random machine. Similarly,
node vi is assigned to a random machine depending on
who gets yi . Note that both Alice and Bob knows which

Lemma 4.1. (Mapping Lemma) Let an n-node, medge graph G be partitioned among the k machines
in N = {p1 , . . . , pk }, according to the random vertex
partition model (assume n ≥ k). Then with probability
at least 1 − 1/nα , where α > 1 is an arbitrary fixed
constant, the following bounds hold:
(1) The number of vertices of G mapped to any machine
is Õ(n/k).
(2) The number of edges of G mapped to any link of
the network is Õ(m/k 2 + ∆/k), where ∆ is the
maximum node degree of G.
Proof. (1) This follows easily from a direct Chernoff
bound application. Since each vertex of G is mapped
independently and uniformly to the set of k machines,
the expected number of vertices mapped to a machine

is n/k. The concentration follows from a standard mapped to link ℓ; the total number of edges mapped pto
X
⌉
Chernoff bound [14].
ℓ is bounded by Zℓp + Zℓq . We have, E[Zℓp |X p ] ≤ ⌈ k−1
q
q
p
X
q
(2) We first note that we cannot directly apply a and similarly E[Zℓ |X ] ≤ ⌈ k−1 ⌉. We next show that Zℓ
q
2
Chernoff bound to show concentration on the number and Zℓ are both bounded by Õ(m/k +∆/k) whp which
p
of edges mapped, as these are not independently dis- will complete the proof. We focus on Zℓ ; (the case of
q
p
Zℓ is similar). By proof of (a), X < Φ with probability
tributed. We show the bound in two steps:
at
least 1 − 1/n2α , where Φ = c log n(m/k + ∆) for some
1. (a) We first show a concentration bound on the
total degree of the vertices assigned to any machine; sufficiently large constant c > 0, depending on constant
2. (b) then we bound the number of edges assigned to α. Observe that an edge that has one endpoint mapped
to p is mapped to link ℓ independently. Hence we can
any link.
p
′
To show (a) we use Bernstein’s inequality [14]. Fix apply a standard Chernoff bound [14]: Pr(Zℓ < c Φ/k+
p
p
′
p
p
a machine p. Let random variable Xi be defined as 1) ≤ Pr(X > Φ) + Pr(Zℓ < c Φ/k + 1)|X < Φ) ≤
′
follows: Xip = d(vi ) (d(vi ) is the degree of vi ) if 1/n2α + 2−c Φ/k+1 ≤ 1/n2α + 2−3 log n+Ω(1) = O(1/n2α ),
p
′
vertex vi is assigned
Pn to pmachine p, otherwise Xi = for a sufficiently large constant c > 0.
p
Thus, with probability 1 − 1/n2α , the number of
0. Let X =
i=1 Xi denote the total degree of
the vertices assigned to machine p; in other words, it edges mapped to link ℓ is c′ Φ/k = Õ(m/k 2 + ∆/k).
is the total number of edges that have at least one Applying a union bound over all k(k − 1)/2 links, yields
endvertex assigned to P
machine p. WeP
have E[Xip ] = the result.
n
n
p
d(vi )/k and E[X p ] =
i=1 d(vi )/k =
i=1 E[Xi ] =
p
p 2
2m/k. Furthermore, V ar(Xi ) = E[(Xi ) ] − E[Xip ]2 = 4.2 The Conversion Theorem We now present a
2
1
2
general conversion theorem that enables us to leverage
( d(vk i ) )2 = (d(vki )) (1 − 1/k)
k (d(vi )) − P
Pn and hence
n
p
1
1
2
p
V ar(X ) P
= i=1 V ar(Xi ) = k (1 − k ) i=1 (d(vi )) ≤ results from the standard message-passing model [33].
n
1
1
1
1
Our conversion theorem allows us to use distributed
i=1 ∆d(vi ) = k (1 − k )∆m.
k (1 − k )
Using Bernstein’s inequality, we have (for some algorithms that leverage direct communication between
nodes, even when such an edge is not part of the
t > 0):
input graph. More specifically, we can translate any
t2
distributed algorithm that works in the following clique
Pr(X p > E[X p ] + t) ≤ e− 2V ar(X p )+(2/3)bt)
model to the k-machine model.
where b = max1≤i≤n |Xip − E[Xip ]|. Now, |Xip −
E[Xip ]| ≤ d(vi )(1 − 1/k) ≤ ∆(1 − 1/k) = b.
Let γ > 0 and let A be the event that X p >
2m/k + γ(2m/k + ∆). Hence, for any γ > 0 and letting
t = γ(2m/k + ∆), we have:
t2

t2

Pr(A) ≤ e− 2(1/k)(1−1/k)∆m+(2/3)∆(1−1/k)t ≤ e− Θ(m∆/k+∆t)
γ 2 (2m/k+∆)2

≤e

− Θ(m∆/k+∆2 )

≤ e−γ

2

m
Θ( ∆k
+ ∆k
m +1)

= O(1/n3α ),

√
if γ = Θ(α log n).
The above tail bound applies to a single machine
p; applying a union bound over all the k machines, we
have X p = Õ(m/k + ∆) whp for every machine p ∈ N .
We now show (b) which will complete the proof
of Part 2. Fix a link ℓ = (p, q) of the k-machine
network. Let X p (resp. X q ) be defined as before, i.e.,
the total number of edges of G with at least one endvertex assigned to p (resp. q). Note that each such
edge mapped to p has probability of 1/(k − 1) of being
mapped to link ℓ (independently of other edges mapped
to p). A similar statement holds for edges mapped to
q as well. Let r.v. Zℓp (resp. Zℓq ) denote the number
of edges, among those mapped to p (resp. q), that are

The Clique Model. Consider a complete n-node
network C and a spanning subgraph G of C determined
by a set of (possibly weighted) edges E(G). The nodes
of C execute a distributed algorithm and each node
u is aware of the edges that are incident to u in G.
Each node can send a message of at most W ≥ 1
bits over each incident link per round. For a graph
problem P , we are interested in distributed algorithms
that run on the network C and, given input graph G,
compute a feasible solution of P . In addition to time
complexity (the number of rounds in the worst case), we
are interested in the message complexity of an algorithm
in this model which is the number of messages (in the
worst case) sent over all links. Additionally, we are also
interested in communication degree complexity which is
the maximum number of messages sent or received by
any node in any round; i.e., it is the minimum integer
M ′ such that every node sends a message to at most
M ′ other nodes in each round. Note that we can
simulate any “classic” distributed algorithm running
on a network G of an arbitrary topology that uses
messages of O(log n) size in the clique model by simply
restricting the communication to edges in E(G) ⊂ E(C)
and by splitting messages into packets of size W . In

Let Gi be the graph whose node set is the same as the
input graph (as well as the clique model), and there is
an edge between nodes u and v if and only if a message
is sent between u and v in round i of the algorithm;
in other words, Gi captures the communications happening in round i. From Lemma 4.1(2), we know that
(w.h.p.) each communication link of N is mapped to
at most Õ(|E(Gi )|/k 2 + ∆i /k) edges of Gi , where ∆i
is the maximum degree of Gi . This means that each
machine needs to send at most Õ(|E(Gi )|/k 2 + ∆i /k)
Theorem 4.1. (Conversion Theorem) Suppose
messages over a specific communication link with high
that there is an ε-error algorithm AC that solves probability. In other words, the ith round of AC can be
problem P in time TC (n) ∈ Õ(n) in the clique model, simulated in Õ(|E(Gi )|/k 2 W +∆i /kW ) rounds, and, by
for any n-node input graph. Then there exists an taking a union bound, the same is true for all rounds in
ε-error algorithm A that solves P in the k-machine [1, TC (n)]. By summing up over all rounds of AC , we
model with bandwidth W satisfying the following time can conclude that the number rounds needed to simucomplexity bounds with high probability:
late AC is


(a) If AC uses point-to-point communication with mes

 ′ 
TC (n) 
X
|E(Gi )|
∆i 
M
∆
sage complexity M and communication
degree com


Õ
=
Õ
+
+
T
(n)
C
∆′
2W
2W
k
kW
k
kW
+
T
(n)⌈
⌉
plexity ∆′ , then A runs in Õ kM
C
2W
kW
i=1
time.
the equality is because of the following facts: (1)
(b) If AC is a broadcast algorithm with broadcast com- where
PTC (n)
B
|E(Gi )| = O(M ) since |E(Gi )| is at most two
plexity B, then A takes Õ( kW + TC (n)) time.
i=1
times the number of messages sent by all nodes in the
Proof. Consider any n-node input graph G with m ith round, and (2) ∆i ≤ ∆′ . This proves (a).
edges and suppose that nodes in G are assigned to the Proof of (b): We first slightly modify the previous
k machines of the network N according to the vertex simulation to simulate broadcast algorithms: Note that
partitioning process (cf. Section 1.1).
if AC is a broadcast algorithm, then for the ith round
We now describe how to obtain algorithm A for the (i ≥ 1) of algorithm AC , if a node u belonging to
k-machine model from the clique model algorithm AC : machine p1 sends messages to nodes v1 , . . . , vj (j ≥ 1)
Each machine locally simulates the execution of AC at belonging to machine p2 , we know that u sends the
each hosted vertex. First of all, we only need to consider same message to v1 , . . . , vj . Thus, when we simulate
inter-machine communication, since local computation this round AC , we will let machine p1 send only one
at each machine happens instantaneously at zero cost. message to p2 , instead of j messages. Then, machine
If algorithm AC requires a message to be sent from a p2 will pretend that this message is sent from u1 to
node u1 ∈ C hosted at machine p1 to some node u2 ∈ C all nodes belonging to p2 that have an edge to node u.
hosted at p2 , then p1 sends this message directly to p2 (We cannot specify the destination nodes v1 , . . . , vj in
via the links of the network N . (Recall that a machine this message as this might increase the length of the
p1 knows the hosting machines of all endpoints of all message significantly.)
edges (in G) that are incident to a node hosted at p1 .)
We now analyze this new simulation. We show that
Moreover, p1 adds a header containing the IDs of u1 and this simulation finishes in Õ( B + TC (n)) rounds. Let
k
u2 to ensure that p2 can correctly deliver the message Bi be the number of nodes that perform a broadcast
to the simulation of AC at u2 . Each message is split in round i of the run of AC in the clique model, and
into packets of size W , which means that sending all note that B = PTC (n) Bi . According to Lemma 4.1(a),
i=1
packages that correspond to such a message requires the number of nodes contributing to Bi broadcasts
⌈O(log n)/W ⌉ rounds. In the worst case (i.e. W = 1), that are assigned to a single machine is Õ(⌈Bi /k⌉)
this requires additional O(log n) rounds, which does not w.h.p.; in other words, w.h.p., each machine contains
change our complexity bounds. Thus, for the remainder ℓi = Õ(⌈Bi /k⌉) of the Bi nodes. Thus, for every i, we
of the proof, we assume that W is large enough such that instruct algorithm A to simulate these Bi broadcasts in
any message generated by AC can be sent in 1 round in the k-machine model in ⌈ℓi /W ⌉ rounds. Since AC takes
the k-machine model.
at most TC (n) rounds, we can take a union bound, and
B
Proof of (a): We will bound the number of messages sent it follows that algorithm A takes Õ( kW
+TC (n)) rounds
in each round through each link using Lemma 4.1(2). in the k-machine model.
this case, the time and message complexities remain
the same (up to log-factors) while the communication
degree complexity can be bounded by the maximum
degree of G. We say that an algorithm is a broadcast
algorithm if, in every round and for every node u, it
holds that u broadcasts the same message to other nodes
(or remains silent). We define the broadcast complexity
of an algorithm as the number of times nodes broadcast
messages.

It is easy to see that a simulation similar to the one
employed in the proof of Theorem 4.1 provides the same
complexity bounds, if we limit the total communication
of each machine (i.e. bits sent/received) to at most kW
bits per round, instead of restricting the bandwidth
of individual inter-machine links to W bits. To see
why this is true, observe that throughout the above
simulation, each machine is required to send/receive at
most kW bits in total per simulated round with high
probability.
4.3 Algorithms We now consider various important
graph problems in the k-machine model. For the sake
of readability, we assume a bandwidth of Θ(log n) bits,
i.e., parameter W = Θ(log n). Observe that the simple
solution of aggregating the entire information about the
input graph G at a single machine takes O(m/k) rounds;
thus we are only interested in algorithms that beat this
trivial upper bound. Our results are summarized in
Table 1.
Breadth-First Search Tree (BFS). To get an intuition for the different bounds obtained by applying either Theorem 4.1(a) or Theorem 4.1(b) to an algorithm
in the clique model, consider the problem of computing a breadth-first search (BFS) tree rooted at a fixed
source node. If we use Theorem 4.1(a) we get a bound of
Õ(m/k 2 + D⌈∆/k⌉) rounds. In contrast, recalling that
each node performs O(1) broadcasts, Theorem 4.1(b)
k
(BFS) ∈ Õ(n/k + D). We will leverage these
yields T1/n
bounds when considering graph connectivity and spanning tree verification below.
Minimum Spanning Tree (MST), Spanning Tree
Verification (ST) and Graph Connectivity (Conn).
An efficient algorithm for computing the MST of an
input graph was given by [16], which proceeds by
merging “MST-fragments” in parallel; initially each
vertex forms a fragment by itself. In each of the O(log n)
phases, each fragment computes the minimum outgoing
edge (pointing to another fragment) and tries to merge
with the respective fragment. Since any MST has
n − 1 edges, at most n − 1 edges need to be added in
total. This yields a total broadcast complexity of Õ(n)
and thus Theorem 4.1(b) readily implies the bound of
Õ(n/k). We can use an MST algorithm for verifying
graph connectivity which in turn can be used for ST. We
assign weight 1 to all edges of the input graph G and
then add an edge with infinite weight between any pair
of nodes u, v where (u, v) ∈
/ E(G), yielding a modified
graph G′ . Clearly, G is disconnected iff an MST of
G′ contains an edge with infinite weight. This yields
the first part of the upper bound for graph connectivity
stated in Table 1. We now describe how to verify

whether an edge set S is an ST, by employing a given
algorithm A for Conn. Note that, for ST verification,
each machine p initially knows the assumed status of
the edges incident to its nodes wrt. being part of the
ST, and eventually p has to output either yes or no.
First, we run A on the graph induced by S and then
we compute the size of S as follows: Each machine
locally adds 1 to its count for each edge (u, v) ∈ S,
if p is the home machine for vertices u, v. Otherwise,
if one of u or v reside on a different machine, then p
adds 1/2. Then, all machines exchange their counts
via broadcast, which takes 1 round (since each count is
at most n and W ∈ Θ(log n)) and determine the final
count by summing up over all received counts including
their own. Each machine outputs yes iff (1) the output
of the Conn algorithm A returned yes and (2) the final
count is n − 1. Thus we get the same bounds for ST
verification as for graph connectivity.
Recalling that we can compute a BFS in Õ(m/k 2 +
D⌈∆/k⌉) rounds, it is straightforward to see that the
same bound holds for Conn (and thus also ST verification): First, we run a leader election algorithm among
the√k machines. This can be done in O(1) rounds (and
Õ( k) messages) by using the algorithm of [23] (whp).
The designated leader machine then chooses an arbitrary node s as the source node and executes a BFS
algorithm. Once this algorithm has terminated, each
machine locally computes the number of its vertices that
are part of the BFS and then computes the total number
of vertices in the BFS by exchanging its count (similarly
to the ST verification above). The input graph is connected iff the BFS contains all vertices.
PageRank. The PageRank problem is to compute the
PageRank distribution of a given graph (may be directed or undirected). A distributed page rank algorithm was presented in [10], based on the distributed
random walk algorithm: Initially, each node generates
Θ(log n) random walk tokens. A node forwards each token with probability 1−δ and terminates the token with
probability δ (called the reset probability). Clearly, every token will take at most O(log n/δ) steps with high
probability before being terminated. From Lemma 2.2
of [11] we know that these steps can be implemented
in O(log2 n) rounds in the clique model, and since this
requires O(n log2 n/δ) messages to be sent in total, Theorem 4.1(a) yields that, for any δ > 0, there is a randomized algorithm for computing PageRank in the kn
k
).
machine model such that T1/n
(PageRank) ∈ Õ( δk
Computing a (2δ − 1)-Spanner. The algorithm of [5]
computes a (2δ − 1)-spanner, for some (δ ∈ O(log n)),
of the input graph G in δ 2 rounds (using messages of
O(log n) size) that has an expected number of δm1+1/δ

edges (cf. Theorem 5.1 in [5]). That is, each node needs
to broadcast δ 2 times, for a total broadcast complexity
of nδ 2 . Applying Theorem 4.1(b) yields a bound of
Õ(n/k) rounds in the k machine model.
Single-Source Shortest Paths (SSSP, SPT), and
All-Pairs Shortest Paths(APSP). We show that,
in the k-machine model, SSSP
√ and APSP can be
(1 + ǫ)-approximated√in Õ(n/ k) time, and (2 + ǫ)approximated in Õ(n n/k) time, respectively.
Recall that, for SSSP, we need to compute the distance between each node and a√designated source node.
1/4
Nanongkai [31] presented a Õ(
√ nD )-time algorithm
for SSSP, which implies a Õ( n)-time algorithm in the
clique model. We show that the ideas
√ in [31], along
with Theorem 4.1(b), leads to a Õ(n/ k)-time (1 + ǫ)approximation algorithm in the k-machine model. We
sketch the algorithm in [31] here5 . First, every node
broadcasts ρ edges incident to it of minimum weight
(breaking tie arbitrarily), for some parameter ρ which
will be fixed later. Using this information, every node
internally compute Õ(1) integral weight functions (without communication). For each of these weight functions, we compute a BFS tree of depth n/ρ from the
source node, treating an edge of weight w as a path
of length w. Using two techniques called light-weight
SSSP and shortest-path diameter reduction, the algorithm of [31] gives a (1 + ǫ)-approximation solution.
Observe that this algorithm uses broadcast communication. Its time complexity
√ is clearly TC (n) = Õ(ρ + n/ρ).
n, we have the running time of
(Thus,
by
setting
ρ
=
√
Õ( n) in the clique model.) Its broadcast complexity is B = Õ(nρ) since every node has to broadcast ρ
edges in the first step and the BFS tree algorithm has
O(n) broadcast complexity. Its message complexity is
M = Õ(n2 ρ) (the BFS tree algorithm has O(n2 ) message complexity since a message will be sent through
each edge once). By Theorem 4.1(b), we have that in
the k-machine model, the time√we need to solve SSSP
is Õ( nρ
+ n/ρ). Using ρ = k, we have the running
k + ρ√
√
√
time of Õ( k + n/ k) = Õ(n/ k) where the equality
is because k ≤ n.
In [31], a similar √
idea was also used to obtain a
(2 + ǫ)-approximation n-time algorithm for APSP on
the clique model. This algorithm is almost identical to
the above algorithm except that it creates BFS trees of
depth n/ρ from n/ρ centers instead of just the source.
By this modification, it can be shown that the running
time remains the same,
√ i.e. TC (n) = Õ(ρ + n/ρ).
n, we have the running time of
(Thus,
by
setting
ρ
=
√
Õ( n) in the clique model.) The broadcast complexity
5 The algorithm is in fact a simplification of the algorithm in
[31] since we only have to deal with the clique model

becomes B = Õ(nρ + n2 /ρ) since each BFS tree
algorithm has O(n) broadcast complexity. Its message
complexity becomes M = Õ(n2 ρ + n3 /ρ) since each
BFS tree algorithm has O(n2 ) message complexity. By
Theorem 4.1(b), we have that in the k-machine model,
2
/ρ
the time we need to solve APSP is Õ( nρ+n
+ρ+n/ρ).
k
√
√
Using ρ = n, we have the running time of Õ( n k n ).
Since the algorithm of [31] also constructs a shortest
path tree while computing the shortest path distances,
we get analogous bounds for the SPT problem, which
requires each machine to know which of its edges are
part of the shortest path tree to the designated source.
We can leverage the technique of computing a
(2δ − 1)-spanner in Õ(n/k) rounds that has an expected
number of Õ(m1+1/δ ) edges. We can simply collect
all edges at one designated machine p, which takes
time Õ(m1+1/δ /k) and then locally compute a (2δ −
1)-approximation for the shortest path problems at
machine p. In particular, for δ = Θ(log n), we have
a spanner of (expected) O(n) edges and thus we get a
O(log n)-approximation for the shortest path problems
in expected Õ(n/k) rounds.
For computing the exact APSP (resp. SSSP) problems, we can use a distributed algorithm by BellmanFord ([33, 28]). This algorithm takes S rounds, where
S is the shortest path diameter, and thus the broadcast
complexity is nS. By virtue of Theorem 4.1(b), we get
a round complexity of Õ(nS/k + S) in the k-machine
model.
Densest Subgraph. We show that Theorem 4.1
implies that the densest subgraph problem can be
approximated in Õ(min( km2 , nk )) time in the k-machine
model. In [38], Das Sarma et al. presented a (2 +
ǫ)-approximation algorithm for the densest subgraph
problem. The idea is very simple: In every round, they
compute the average degree of the network and delete
nodes of degree less than (1 + ǫ) times of the average
degree. This process generates several subgraphs of
the original network, and the algorithm output the
densest subgraph among the generated subgraphs. It
was shown in [38] that this algorithm produces a (2+ǫ)approximate solution. They also proved that this
algorithm stops after log1+ǫ n rounds, implying a time
complexity of TC (n) = O(log n) in the clique model.
The message complexity is M = Õ(m) since every node
has to announce to its neighbors in the input graph
that it is deleted at some point. For the same reason,
the broadcast complexity is B = Õ(n). Note that this
algorithm is broadcast. So, By Theorem 4.1, we have
that in the k-machine model, the time we need to solve
this problem is Õ( nk ) as desired.
Cut Sparsifier, Min Cut, Sparsest Cut, etc.. An

ǫ-cut-sparsification of a graph G is a graph G′ on the
same set of nodes such that every cut in G′ is within
(1 ± ǫ) of the corresponding cut in G. We show that
we can use the technique called refinement sampling
of Goel et al. [17], to compute an ǫ-sparsification of
Õ(n) edges in Õ(n/k) time in the k-machine model.
By aggregating this sparsification to a single machine,
we can approximately solve cut-related problems such
as a (1 ± ǫ)-approximate solution to the minimum cut
and sparsest cut problems. The main component of the
algorithm of Goel et al. is repetitively sparsify the graph
by keeping each edge with probability 2−ℓ for some ℓ,
and compute the connected components after every time
we sparsify the graph. By doing this process for Õ(1)
times, we can compute a probability z(e) on each edge e.
Goel et al. showed that we can use this probability z(e)
to (locally) sample edges and assign weights to them to
obtain an ǫ-sparsification. It is thus enough to be able
to compute the connected components quickly in the
k-machine model. This can be done by simply invoke
the MST algorithm, which takes Õ(n/k) rounds. We
have to runs this algorithm for Õ(1) times, so the total
running time is Õ(n/k).
Covering Problems on Graphs. We now describe
how to solve covering problems like maximal independent set (MIS) in our model. We first consider MIS
and related covering problems on simple graphs, and
then describe how to obtain an MIS on an input hypergraph. A well known distributed algorithm for computing a maximal independent set (MIS) is due to [27]: The
algorithm proceeds in phases and in each phase, every
active node v—initially every node—marks itself with
probability 1/2dv where dv is the degree of v. If v turns
out to be the only marked node in its neighborhood,
v enters the MIS, notifies all of its neighbors who no
longer participate (i.e. become inactive) in future phases
and terminates. When 2 neighboring nodes both mark
themselves in the same phase, the lower degree node
unmarks itself. Nodes that were not deactivated proceed to the next phase and so forth. It was shown in
[27] that this algorithm terminates in O(log n) rounds
with high probability. Since each node sends the same
messages to all neighbors, we can analyze the communication in terms of broadcasts, yielding a broadcast complexity of O(n log n) (whp). Applying Theorem 4.1(b)
yields a round complexity of Õ(n/k). Alternatively, for
bounded degree graphs, applying Theorem 4.1(a) gives
us a running time of Õ(m/k 2 + ∆/k), which is faster
when ∆ ≪ k. Considering the locality preserving reductions (cf. [21]) between MIS, maximal matching (MM),
minimal dominating set (MDS), and computing a 2approximation of the minimum vertex cover (MVC), we
k
k
k
k
get that T1/n
(MIS), T1/n
(MM), T1/n
(MVC), T1/n
(MDS)

are Õ(min(n/k, m/k 2 + ∆/k)).
We now describe how to obtain an Õ(n/k + k) time
algorithm for all graph covering problems directly in
the k-machine model, without resorting to Theorem√4.1;
note that this translates to Õ(n/k) when k ≤ Õ( n).
In particular, this yields an Õ(n/k + k) algorithm for
the problem of finding a maximal independent set in a
hypergraph (HMIS), which has been studied extensively
in the PRAM model of computation (cf. [20, 6]). Note
that, for the hypergraph setting, the input graph G is
a hypergraph and if some node u has home machine p1 ,
then p1 knows all hyperedges (and the corresponding
machines) that contain u. To the best of our knowledge,
there is no efficient distributed algorithm known for
HMIS. First assume that there is an ordering of the
machines with ids 1, . . . , k. Such an ordering can
be obtained by running the O(1)-time leader election
algorithm of [23]. The elected leader (machine) then
arbitrarily assigns unique ids to all the other machines.
Then, we sequentially process the nodes at each machine
and proceed in k phases. In the first phase, machine 1
locally determine the membership status of being in the
HMIS, for all of its nodes. Next, machine 1 computes an
arbitrary enumeration of its nodes and sends the status
(either 0 or 1) and node id of the first k nodes over its
k links (i.e. a single status is sent over exactly 1 link).
When a machine receives this message from machine 1,
it simply broadcasts this message to all machines in the
next round. Thus, after 2 rounds, all machines know
the status of the first k nodes of machine 1. Then,
machine 1 sends the status of the next k nodes and so
forth. By Lemma 4.1, there will be Õ(n/k) nodes with
high probability, and therefore every machine will know
the status of all the nodes of machine 1 after Õ(n/k 2 )
rounds. After machine 1 has completed sending out all
statuses, all other machines locally use this information
to compute the statuses of their nodes (if possible). For
example, if some node u at machine 1 is in the HMIS (i.e.
has status 1) and adjacent to some node v at machine
2, then machine 2 sets the status of v to 0. Then,
machine 2 locally computes the status of its remaining
undetermined nodes such that they are consistent with
the previously received statuses, and starts sending this
information to all other machines in the same fashion.
Repeating the same process for each of the k machines
yields a total running time of Õ(n/k + k).
Finding Triangles and Subgraphs. For the subgraph isomorphism problem SubIsod , we are given 2
input graphs: the usual n-node graph G and a dvertex graph H, for d ∈ O(1). We want to answer
the question whether H ⊆ G. A distributed algorithm
for the clique model that runs in O(n(d−2)/d ) rounds
was given by [13]. Since the total number of mes-

sages sent per round is O(n2 ), Theorem 4.1(a) gives
rise to an algorithm for the k-machine model that runs
in Õ(n2+(d−2)/d /k 2 + n1+(d−2)/d /k) rounds.
We use Tri to denote the restriction of SubIso3
to the case where H is a triangle. The following is
a simple algorithm for the clique model: Each node
locally collects its 2-neighborhood information, checks
for triangles and then either outputs yes or no. This
requires each node to send a message for each of its
at most ∆ neighbors. The total number of messages
sent is n∆2 , and the algorithm takes ∆ rounds to
send all messages. Applying Theorem 4.1(a), we get
a distributed algorithm in the k-machine model with
round complexity of Õ(n∆2 /k 2 + ∆⌈∆/k⌉), which is
better than the above bound when ∆ is sufficiently
k
small. Thus, we have T1/n
(Tri) ∈ Õ(min(n∆2 /k 2 +
∆⌈∆/k⌉, n7/3 /k 2 + n4/3 /k)).
5

Conclusion

We presented algorithms and lower bounds for distributed computation of several graph problems. Our
bounds are (almost) tight for problems such as computing a ST or a MST, while for other problems such as connectivity and shortest paths, there is a non-trivial gap
between upper and lower bounds. Understanding these
bounds and investigating the best possible can provide
insight into understanding the complexity of distributed
graph processing.
References
[1] Gps:
A
graph
processing
system,
http://infolab.stanford.edu/gps/. 1, 2
[2] L. Babai, P. Frankl, and J. Simon. Complexity classes
in communication complexity theory (preliminary version). In FOCS, pages 337–347, 1986. 9
[3] Nikhil Bansal, Kang-Won Lee, Viswanath Nagarajan,
and Murtaza Zafer. Minimum congestion mapping in
a cloud. In PODC, pages 267–276, 2011. 2
[4] Ziv Bar-Yossef, T. S. Jayram, Ravi Kumar, and
D. Sivakumar. An information statistics approach to
data stream and communication complexity. J. Comput. Syst. Sci., 68(4):702–732, 2004. Also in FOCS’02.
9
[5] Surender Baswana and Sandeep Sen. A simple and linear time randomized algorithm for computing sparse
spanners in weighted graphs. Random Struct. Algorithms, 30(4):532–563, 2007. 12, 13
[6] Paul Beame and Michael Luby. Parallel search for
maximal independence given minimal dependence. In
SODA, pages 212–218, 1990. 14
[7] Mark Braverman, Ankit Garg, Denis Pankratov, and
Omri Weinstein. From information to exact communication. In STOC, pages 151–160, 2013. 9

[8] Amit Chakrabarti, Graham Cormode, and Andrew
McGregor. Robust lower bounds for communication
and stream computation. Electronic Colloquium on
Computational Complexity (ECCC), 18:62, 2011. 3
[9] Arkadev Chattopadhyay and Toniann Pitassi. The
Story of Set Disjointness. SIGACT News, 41(3):59–85,
2010. 9
[10] Atish Das Sarma, Anisur Rahaman Molla, Gopal Pandurangan, and Eli Upfal. Fast distributed pagerank
computation. In ICDCN, pages 11–26, 2013. 12
[11] Atish Das Sarma, Danupon Nanongkai, and Gopal
Pandurangan. Fast distributed random walks. In
PODC, pages 161–170, 2009. 12
[12] Jeffrey Dean and Sanjay Ghemawat. Mapreduce:
Simplified data processing on large clusters. In OSDI,
pages 137–150, 2004. 1
[13] Danny Dolev, Christoph Lenzen, and Shir Peled. ”tri,
tri again”: Finding triangles and small subgraphs in
a distributed setting - (extended abstract). In DISC,
pages 195–209, 2012. 14
[14] Dubhashi and Panconesi. Concentration of Measure
for Analysis of Randomized Algorithms. Cambridge
University Press, 2012. 10
[15] Michael Elkin, Hartmut Klauck, Danupon Nanongkai,
and Gopal Pandurangan. Can quantum communication speed up distributed computation? In PODC,
2014. 5
[16] Robert G. Gallager, Pierre A. Humblet, and Philip M.
Spira. A distributed algorithm for minimum-weight
spanning trees. ACM Trans. Program. Lang. Syst.,
5(1):66–77, 1983. 12
[17] Ashish Goel, Michael Kapralov, and Sanjeev Khanna.
Graph sparsification via refinement sampling. CoRR,
abs/1004.4915, 2010. 14
[18] Bala Kalyanasundaram and Georg Schnitger. The
Probabilistic Communication Complexity of Set Intersection. SIAM J. Discrete Math., 5(4):545–557, 1992.
Also in CCC’87. 9
[19] Howard J. Karloff, Siddharth Suri, and Sergei Vassilvitskii. A model of computation for mapreduce. In
SODA, pages 938–948, 2010. 4
[20] Pierre Kelsen. On the parallel complexity of computing
a maximal independent set in a hypergraph. In STOC,
pages 339–350, 1992. 14
[21] Fabian Kuhn, Thomas Moscibroda, and Roger Wattenhofer. Local computation: Lower and upper bounds.
CoRR, abs/1011.5470, 2010. 14
[22] E. Kushilevitz and N. Nisan. Communication complexity. Cambridge University Press, New York, NY, USA,
1997. 7, 8, 20
[23] Shay Kutten, Gopal Pandurangan, David Peleg, Peter
Robinson, and Amitabh Trehan. Sublinear bounds for
randomized leader election. In ICDCN, pages 348–362,
2013. 12, 14
[24] Silvio Lattanzi, Benjamin Moseley, Siddharth Suri, and
Sergei Vassilvitskii. Filtering: a method for solving
graph problems in mapreduce. In SPAA, pages 85–94,
2011. 4

[25] J. Lin and C. Dyer. Data-Intensive Text Processing
with MapReduce. Morgan Claypool Publishers, 2010.
1, 4
[26] Yucheng Low, Joseph Gonzalez, Aapo Kyrola, Danny
Bickson, Carlos Guestrin, and Joseph M. Hellerstein.
Graphlab: A new framework for parallel machine
learning. In UAI, pages 340–349, 2010. 1
[27] Michael Luby. A simple parallel algorithm for the
maximal independent set problem. SIAM J. Comput.,
15(4):1036–1053, 1986. 14
[28] Nancy Lynch. Distributed Algorithms. Morgan Kaufmann, 1996. 2, 13
[29] Grzegorz Malewicz, Matthew H. Austern, Aart J. C.
Bik, James C. Dehnert, Ilan Horn, Naty Leiser, and
Grzegorz Czajkowski. Pregel: a system for large-scale
graph processing. In SIGMOD Conference, pages 135–
146, 2010. 1, 2
[30] M. Mitzenmacher and E. Upfal. Probability and Computing: Randomized Algorithms and Probabilistic Analysis. Cambridge University Press, 2005. 20
[31] Danupon Nanongkai. Distributed approximation algorithms for weighted shortest paths. In STOC, pages
565–573, 2014. 13
[32] Danupon Nanongkai, Atish Das Sarma, and Gopal
Pandurangan. A tight unconditional lower bound on
distributed randomwalk computation. In PODC, pages
257–266, 2011. 5
[33] David Peleg.
Distributed computing: a localitysensitive approach. Society for Industrial and Applied
Mathematics, Philadelphia, PA, USA, 2000. 2, 3, 4, 5,
10, 13
[34] The
Apache
Project.
Apache
Giraph,
http://giraph.apache.org/. 1, 2
[35] Anand Rajaraman and Jeff Ullman. Mining of Massive
Datasets. Cambridge University Press, October 2011.
2, 4
[36] Alexander A. Razborov.
On the Distributional
Complexity of Disjointness. Theor. Comput. Sci.,
106(2):385–390, 1992. Also in ICALP’90. 3, 9, 16
[37] 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. 5
[38] Atish Das Sarma, Ashwin Lall, Danupon Nanongkai,
and Amitabh Trehan. Dense subgraphs on dynamic
networks. In Distributed Computing - 26th International Symposium, DISC 2012, Salvador, Brazil, October 16-18, 2012. Proceedings, pages 151–165, 2012.
13
[39] Isabelle Stanton. Streaming balanced graph partitioning for random graphs. CoRR, abs/1212.1121, 2012.
2
[40] Isabelle Stanton and Gabriel Kliot. Streaming graph
partitioning for large distributed graphs. In KDD,
pages 1222–1230, 2012. 2
[41] David P. Woodruff and Qin Zhang. When distributed
computation is communication expensive. In DISC,

pages 16–30, 2013. 3, 4, 5

A Proof of Lemma 3.2
Our proof adapts the proof of Razborov [36] from the
situation of a fixed partition to a random partition of
the inputs. In the following we try to keep our notation
close to that of Razborov’s. In particular, we use N
to replace b as elsewhere in this paper. We first recall
the standard definition of deterministic and randomized
protocols here.
Definition 1. The communication cost of a deterministic protocol P computing a function f : X ×Y → {0, 1}
on an input x, y is the number of bits exchanged between
Alice and Bob during P on x, y. The communication
cost of P is the maximum communication cost over all
inputs. The deterministic communication complexity of
f is the minimum communication cost (over all protocols) computing f .
A randomized protocol has to be correct with probability 2/3 (over the random choices used in the protocol) on every input. The randomized communication
complexity is then defined as above.
In the above definition, the inputs x, y are partitioned
in a fixed way. We are interested in the communication
cost over an average partition of the inputs to Alice and
Bob. In this situation the communication cost (for a
fixed input z) is the average over all partitions of the
bits of z to Alice and Bob. More precisely, for every
partition ρ of z there is a protocol Pρ computing f ,
and the communication cost on z is the average over
the communication costs of all the Pρ on z. Here the
distribution over partitions is the one in which every bit
zj is assigned uniformly random to Alice or Bob (but
not both).
Definition 2. A deterministic average partition protocol P consists of a protocol Pρ for every partition of
the inputs z = z1 , . . . , zℓ . Every protocol Pρ has to be
correct on all inputs partitioned according to ρ.
The average partition communication cost of a deterministic protocol P on an input z is the average number of bits exchanged by Pρ , where the distribution on ρ
is defined such that each zj is assigned as input to Alice or Bob uniformly at random. The average partition
communication cost of P is then the maximum over all
inputs.
The deterministic average partition communication
complexity of a function f is the minimum average
partition communication cost over all protocols for f .
For randomized protocols the following correctness
criteria must hold: for an input z the probability of P
giving the correct output must be at least 2/3, over both

the random choices inside the Pρ and the choice of Pρ
itself.
We note that in the definition above, the notion of
average partition is slightly different from the notion of
random-partition we define in Section 3.1 in that we are
interested in expected communication complexity for the
case of average partition, and worst-case communication
complexity for the case of random partition. Since a
protocol with worst-case communication complexity c
also gives an average communication complexity c, a
lower bound for the average partition model is also a
lower bound for the random partition model. In this
section, we will prove a lower bound for the average
partition model.
We will show a lower bound on the randomized average partition communication complexity of the Disjointness problem disj. This complexity measure is defined as a maximum over all inputs (of the average cost
of randomized protocols under a random partition). As
usual we can instead (as in the easy direction of the Yao
principle) bound the expected complexity of deterministic protocols over a hard distribution on inputs (and
over the random partitions).
Recall that the partitions ρ of {z1 , . . . , zℓ } are
chosen uniformly. Furthermore, inputs z will be chosen
from a distribution µ defined by Razborov. It is
important that inputs and their partition are chosen
independent of each other. Due to independence, when
analyzing the error of a protocol, we may also choose the
partition first, and then consider the error for random
inputs given a fixed partition.

This error is the expectation over inputs z (from µ) and
over partitions ρ of the input positions {1, . . . , 2N }. We
denote the expected error under a fixed partition ρ, i.e.,
the expected error of Pρ , by ǫρ . The probability (over
ρ) that ǫρ is larger than ǫ/δ is at most δ.
Besides the error also the communication cost on
input z is an expectation, this time over the choice of the
partition. Recall that we are dealing with deterministic
protocols Pρ . Denote by c the expected communication
over the choice of ρ and the choice of z, and by cρ the
expectation over z with ρ fixed.
In our main lemma we will show that for most
partitions ρ this is impossible unless c = Ω(N ).
We first define the input distribution used by
Razborov for disj on inputs of size N .
Definition 3. Set N = 4m−1, the size of the universe
of elements. To choose inputs according to Razborov’s
distribution one first chooses a frame. The frame
consists of a partition of {1, . . . , N } into 3 disjoint
subsets zx , zy , {i} such that |zx | = |zy | = 2m − 1.
For the distribution µ1 on 1-inputs to disj one then
chooses a subset x of size m of zx as an input to Alice,
and a subset of size m of zy as an input to Bob.
For the distribution µ0 on 0-inputs one chooses a
subset x of size m − 1 from zx and lets Alice’s input be
x ∪ {i}, and correspondingly for Bob.
The distribution µ is the mixture 3/4 · µ0 + 1/4 · µ1.

Note that µ is the uniform distribution on all inputs
for which both sets are of size m and the intersection
size is at most 1.
In our setting the partition ρ of input positions (not
Theorem A.1. The randomized average partition com- to be confused with the partitions from the definition of
munication complexity of the Disjointness problem disj µ) is chosen independent of the inputs (which are chosen
is Ω(N ).
from µ). We next observe that usually enough inputs
The theorem also holds, if Alice also gets to know xi , yi are distributed among Alice and Bob.
all of x and Bob gets to know all of y.
Lemma A.1. Let ρ be a uniformly random partition of

Proof of Theorem A.1 The inputs to Disjointness
are z = x1 , . . . , xN , y1 , . . . , yN . We first take a look
at a simple property that most partitions have, namely
that on most partitions many pairs xj , yj are distributed
among Alice and Bob. For simplicity we only care about
pairs where xj is with Alice and yj is with Bob.
After that we follow Razborov’s proof for the hardness of Disjointness under a fixed distribution µ, but we
have to be more flexible with parameters, and restrict
attention to a part of the distribution µ that is still hard
(for a given partition of the inputs). Furthermore we
have to analyze certain parts of rectangles separately to
keep the product properties in Razborov’s proof intact.
In the following δ will be a small all-purpose constant. Denote the expected error of the protocol by ǫ.

the input variables x1 , . . . , xN , y1 , . . . , yN . pThen with
probability 1 − δ we have that at least N/4 − N/δ pairs
xj , yj are distributed such that Alice holds xi and Bob
holds yi .
Proof: For each pair xi is on Alice’s side and yi on
Bob’s side with probability 1/4. Let C denote number
of i’s for which this is the case. The expectation of C is
N/4 and the variance is 3N/16. Hence, by Chebyshev’s
inequality
probability that |C − N/4| is larger than
√ √ the √

(1/ δ)( 3/4) N is at most δ.
We call partitions ρ under which more than n =
N/5 positions j are such that xj is with Alice and yj
with Bob good partitions. In the following we analyze
protocols under an arbitrary fixed good partition, showing that protocols with low communication cost will

have large error. Since the expected communication is
at least 1 − δ times the cost under the best good partition, a linear lower bound will follow for a random
partition. On the other hand, at most a δ fraction of all
partitions is allowed to have larger error than ǫ/δ.
So fix any good partition ρ. For notational simplicity assume that x1 , . . . , xn belong to Alice, and
y1 , . . . , yn to Bob. The remaining inputs are distributed
in any other way. We consider inputs drawn from the
distribution µ.
Note first, that the probability (under µ) that for
the ”intersection position” i is larger than n, i.e., that
both xi and yi might belong to Alice (or Bob) is 4/5, and
in this case we assume the protocol already knows the
answer without communication. So we have to assume
that ǫ < 1/20 to get a lower bound, since i is contained
in both x and y with probability 1/4, and hence with
error 1/20 the problem to be solved is trivial. If the error
is smaller than, say 1/50, then the protocol must give
the correct output for most inputs with the intersecting
position i smaller than n + 1.
Define µρ as the distribution µ restricted to i (as
part of the frame) being chosen from 1 to n. Note that
µ = 1/5 · µρ + 4/5 · σ for some distribution σ. Since
the protocols Pρ we consider have error ǫρ on µ (using
partition ρ), they can have error at most 5ǫρ on µρ . So
we restrict our attention to µρ .
µρ,1 is the distribution µ1 restricted to i being from
1 to n, and µρ,0 is the distribution µ0 under the same restriction. We will denote the random variables of inputs
chosen from µρ,1 by x0 , y0 (indicating intersection size
0), and the random variables of inputs chosen from µρ,0
by x1 , y1 . x, y is the pair of random variables drawn
from µ. Note that x is the random variable corresponding to the marginal of µ on the x-variables.
Furthermore we will denote by a, b etc. the random
variables x, y grouped into Alice’s and Bob’s inputs.
Note that the first n variables in x belong to Alice
and the first n variables in y belong to Bob, the other
variables are assigned in any way. Subscripts again
indicate drawing inputs from µρ,0 or µρ,1 .
We can now state the Main Lemma.

In other words, all rectangles R that are trying
to cover mostly 1-inputs to disj are either small or
corrupted by a constant fraction of 0-inputs. A low
error cover made up of rectangles hence needs to contain
many rectangles.
Now we show that the main lemma implies the
lower bound for disj. The randomized average partition communication complexity is lower bounded by
Eρ Eµ cρ,z (f ), where cρ,z is the communication cost on
input z under partition ρ. Since all good partitions
together have probability 1 − δ, we just need to show
that for any good partition ρ the average communication Eµ cρ,z ≥ Ω(N ).
We have Prρ,µ (cρ,z > δc) < δ. Hence, if we stop all
protocols Pρ once their communication on an input z
exceeds c/δ, we increase the error by at most δ. Hence
in the following we can assume that for each ρ and z we
have cρ,z ≤ c/δ, and in particular, that cρ ≤ c/δ.
The protocol Pρ has communication at most c/δ,
and corresponds to a partition of the communication
matrix according to ρ into 2c/δ rectangles with total
error ǫρ +δ under µ. Since µρ makes up one fifth of µ, the
error under µρ can be at most 5(ǫρ + δ). Furthermore,
the inputs in the support of µρ (i.e., the inputs with
intersection size at most 1 and intersections happening
at position n or less) are partitioned into 2c/δ rectangles
with error 10(ǫρ +δ). Since µρ puts weight 3/4 on inputs
x, y that are disjoint, there must be a single rectangle
R that covers (3/12) · 2−c/δ of 1-inputs and at the same
time has error at most 30(ǫ/δ + δ) (both under µρ ). The
Main Lemma now leads to a contradiction for ζN < c/δ
and 30(ǫ/δ + δ) being a suitably small constant.
We now proceed to show the main lemma. In
Razborov’s proof the rectangles R to be analyzed are
product sets with respect to the divide between x and y.
For us this is not the case, because Alice and Bob hold
both x- and y-inputs. However, Alice holds x1 . . . , xn
and Bob y1 , . . . , yn . Call all the remaining variables
(that are distributed arbitrarily) O.
In the statement of the Main Lemma α/(1 + α) is
(a lower bound on) the error of R under µρ . Since α is a
constant we will determine later it is enough to show a
constant lower bound on the error of any large rectangle
Lemma A.2. Let ρ be a good partition. x, y are chosen R. Denote the error of R under µρ by α′ .
from µρ (i.e., µ with i < n + 1), and partitioned into
The rectangle R can be partitioned into smaller
random variables as described above. Let R = Ā × B̄ rectangles by fixing the variables O to some value o.
denote a rectangle of size 2−ζN (under µρ ) in the We denote a resulting rectangle by Ro (note that Ro
communication matrix induced by disj and ρ, for some is indeed a rectangle). Let γo denote the average error
small constant ζ > 0.
of Ro under µρ , normalized to Ro (where o is chosen
Then
according to the size of Ro ). Clearly the expected γo is
α′ .
Pr ((a1 , a1 ) ∈ R) ≥ α · Pr ((a0 , a0 ) ∈ R) ,
Ro = Āo ×B̄ o corresponds to a rectangle in {0, 1}n ×
{0, 1}n by ignoring fixed input variables. R itself is a
for some constant α > 0.

rectangle in {0, 1}N × {0, 1}N . o fixes x, y on the last
N −n input positions, and if we define a as x∩{1, . . . , n}
and b = y ∩ {1, . . . , n}, then ma = |a| and mb = |b| are
fixed on Ro .
For every a, b with fixed ma , mb there are

 

N −n
N − n − m + ma
fa,b =
·
m − ma
mb

in the same situation as Razborov, except that the sets
a, b are not exactly of size n/4.
Denote by ma and mb the sizes of a, b respectively.
We consider the distribution ν which is defined as
follows.

Definition 4. n = 4m′ − 1. To choose inputs one
first chooses a frame. There are n input positions. The
frame consists of a partition of {1, . . . , n} into 3 disjoint
extensions o. And hence as many (disjoint) rectangles subsets za , zb , {i} such that |za | = |zb | = 2m′ − 1.
For the distribution ν1 on 1-inputs to disj one then
Ro in R. Later we will restrict our attention to o for
which ma , mb are very close to n/4. Recall that R has chooses a subset a of size ma of za as an input to Alice,
size µρ (R) ≥ 2−ζN by the assumptions in the Main and a subset of size mb of zb as an input to Bob.
For the distribution µ0 on 0-inputs one chooses a
Lemma.
To apply a modification of Razborov’s original subset a of size ma − 1 from za and lets Alice’s input be
argument for disj on {0, 1}n × {0, 1}n we want to find a ∪ {i}, and correspondingly for Bob.
The distribution ν is the mixture 3/4 · ν0 + 1/4 · ν1 .
an o such that Ro
1. is large (as a rectangle in {0, 1}n × {0, 1}n)
2. has small error
3. the size of x∩{1, . . . n} and y ∩{1, . . . , n} is roughly
n/4 for all inputs in Ro .

Note that ν can be obtained from µρ by dropping
the last N − n elements of the universe. Since µ is
invariant under permuting the last N − n or the first n
elements of the universe, for all x, y and a, b obtained
from them ν(a, b) = µρ (x, y) · fa,b . In our case all fa,b
are within 2O(κn) of each other. This means that our
Ro has size ν(Ro ) ≥ 2−2ζN −O(κN ) .
What is left to do is to prove Razborov’s Main
Lemma under the modification that the sets x, y have
fixed sizes that are slightly different from n/4. The argument is almost entirely the same, with some estimates
looser than in the original.
We now restate that Lemma. In this restatement
we re-use the notation a1 etc., which now refer to the
domain {0, 1}n × {0, 1}n and ν etc.

−1
The rectangles Ro with µρ (R0 ) < fa,b
· 2−2ζN contribute at most 2−2ζN to R and can thus be disregarded without changing the error much (even if the
small Ro contain only 1-inputs). We choose o now
by picking x, y from µρ restricted to R, and removing
x1 , . . . , xn , y1 , . . . , yn . This clearly chooses a Ro by size,
and hence the expected error is at most 2α′ , and the
probability that the error is larger than 2α′ /δ is at most
δ.
We now have to consider the size of sets a = Lemma A.3. a, b are chosen from ν (as above). Let
x ∩ {1, . . . , n} and b = y ∩ {1, . . . , n}. Note that o fixes R = Ā × B̄ denote a rectangle of size 2−ζ ′ , for some
some kx of the x-variables to 1 and some ky of the y- small constant ζ ′ > 0.
variables, and the size of a is m − kx , the size of b is
Then
m − ky .
Pr ((a1 , a1 ) ∈ R) ≥ α · Pr ((a0 , a0 ) ∈ R) ,
The following claim follows from a simple application of the Chernoff inequality.
for some constant α > 0.
Claim 1. Choose o by choosing x, y from µρ and disWe omit the details of this. As discussed above this
carding the variables outside O.
implies our Main Lemma, and hence the lower bound
2
Pr(| |a| − n/4 | > κn or | |b| − n/4 | > κn) ≤ 2−κ n/3 . for disj.
To see that the above proof also applies if Alice
2
knows
all of x and Bob knows all of y note that we
For a small enough κ (namely κ /3 · n ≪ ζN ) this
actually
analyze the rectangles R0 , in which the extra
means that when we choose o as above (i.e., x, y from R
inputs
are
fixed anyway.
according to µ and dropping the unneeded variables),
then with probability > 2/3 the size of a and b are
B Proof of Lemma 3.1
within ±κn of n/4.
Hence we can find o such that the above 3 criteria We will use the following lower bound which can be
are satisfied, and all that is left to do is to show that Ro derived using basic facts in communication complexity.
must have large error after all. By now we are almost We sketch its proof for completeness.

cc−pub
Theorem B.1. For some ǫ > 0, R0,ǫ
(eq) ≥ b.

gives the additional error of 4/b.) Moreover, the number
of communication bits that their√simulation requires
is
√
Proof. [Proof sketch] We need the following additional less than |Sb |+(b−|Sb|)/2+(1/2) 6b ln b+b/4− 6b ln b
√
notations. Let N 1 (f ) denote the nondeterminic com- which is less than b since |Sb | ≤ b/2+(1/2) 6b ln b. This
munication complexity of computing f (see, e.g., [22, implies that Rcc−pub (eq) < b as desired.
0,ǫ
Definition 2.3]). It is well-known that N 1 (eq) ≥ b
Note that in the reduction above Alice knows x and
(see, e.g. [22, Example 2.5]). Note further that Bob knows y. Thus, the claimed lower bound holds even
cc−pub
R0,ǫ
(f ) ≥ N 1 (f ) (see, e.g., [22, Proposition 3.7]6 ). when Alice and Bob have this information in addition
cc−pub
Thus, R0,ǫ
(eq) ≥ N 1 (eq) ≥ b as claimed.
to the random partition.
Proof. [Proof Lemma 3.1]
prove that if
√ We will now cc−pub
rcc−pub
R0,ǫ
(eq) < b/4 − 6b ln b, then R0,ǫ
(eq) <
b, thus contradicting Theorem B.1. This immedircc−pub
ately implies that R0,ǫ
(eq) = Ω(b), as claimed in
Lemma 3.1. Let A be a protocol in the random-partition
model which requires strictly less than b/4 bits of communication. Alice and Bob simulates A as follows.
First, they use shared randomness to pick a random
partition of x and y, denoted by P. Let SB be the set
of positions in x that
√ Bob receives in partition P. If
|SB | > b/2 + (1/2) 6b ln b, then they stop the simulation and answer 0 (representing “x 6= y”). Note that
this could cause an error when x = y; however, by
Chernoff’s bound (e.g. [30, Section 4.2.2]), this happens with probability at most 2/b. If Alice and Bob
do not stop the simulation, Alice sends to Bob bits in
x at positions
√ in SB . This causes a communication of
b/2 + (1/2) 6b ln b (note that Alice simply sends |SB |
bits in order and Bob can figure out which bit belongs
to which position since he also knows the partition P).
Next, Bob checks whether bits in x sent from Alice is
the same as his bits (in the same position). If not, he
immediately answers 0 (“x 6= y”); otherwise, we let
SA be the set of positions not in SB such that Alice
receives bits in y at positions
√ in SA . Bob checks if
|SA | > (b − |SB |)/2 + (1/2) 6b ln b. If this is the case,
then Alice and Bob stops the simulation and answer 0.
This again could cause an error but it happens with
probability at most 2/b by Chernoff’s bound. If this
does not happen, Bob sends bits in y at positions
√ in SA
to Alice. This causes at most (b−|SB |)/2+(1/2) 6b ln b
bits of communication. Then, Alice and √
Bob simulates
A, which will finish after less than b/4 − 6b ln b bits of
communication and produces an answer that is (ǫ, 0)error. Alice and Bob use this answer as their answer.
Combining with the previous errors, we have that Alice
and Bob’s answer is (ǫ+ 4/b, 0)-error. (This error comes
from the worst-case scenario where A could be always
correct for the partitions that Alice and Bob stops. This
6 We note that our notations are slightly different from [22].
It can be checked from [22, Definitions 3.1 and 3.3] that the
rcc−pub
definition of R0,ǫ
is the same as R1 , i.e. they correspond
to the case where we allow an error only when f (x, y) = 1.

