Round Compression for Parallel Matching Algorithms

arXiv:1707.03478v2 [] 1 Feb 2018

Artur Czumaj
University of Warwick
a.czumaj@warwick.ac.uk
Slobodan Mitrović
EPFL
slobodan.mitrovic@epfl.ch

Jakub Łacki
˛
Google Research, New York
jlacki@google.com
Krzysztof Onak
IBM Research
konak@us.ibm.com

Aleksander Madry
˛
MIT
madry@mit.edu
Piotr Sankowski
University of Warsaw
sank@mimuw.edu.pl

Abstract
For over a decade now we have been witnessing the success of massive parallel computation (MPC)
frameworks, such as MapReduce, Hadoop, Dryad, or Spark. One of the reasons for their success is
the fact that these frameworks are able to accurately capture the nature of large-scale computation. In
particular, compared to the classic distributed algorithms or PRAM models, these frameworks allow for
much more local computation. The fundamental question that arises in this context is though: can we
leverage this additional power to obtain even faster parallel algorithms?
A prominent example here is the maximum matching problem—one of the most classic graph problems. It is well known that in the PRAM model one can compute a 2-approximate maximum matching in
O(log n) rounds. However, the exact complexity of this problem in the MPC framework is still far from
understood. Lattanzi et al. (SPAA 2011) showed that if each machine has n1+Ω(1) memory, this problem
can also be solved 2-approximately in a constant number of rounds. These techniques, as well as the
approaches developed in the follow up work, seem though to get stuck in a fundamental way at roughly
O(log n) rounds once we enter the (at most) near-linear memory regime. It is thus entirely possible that
in this regime, which captures in particular the case of sparse graph computations, the best MPC round
complexity matches what one can already get in the PRAM model, without the need to take advantage
of the extra local computation power.
In this paper, we finally refute that perplexing possibility. That is, we break the above O(log n) round
complexity bound even in the case of slightly sublinear memory per machine. In fact, our improvement
here is almost exponential: we are able to deliver
a (2 + ǫ)-approximation to maximum matching, for

any fixed constant ǫ > 0, in O (log log n)2 rounds.
To establish our result we need to deviate from the previous work in two important ways that are crucial for exploiting the power of the MPC model, as compared to the PRAM model. Firstly, we use vertex–
based graph partitioning, instead of the edge–based approaches that were utilized so far. Secondly, we
develop a technique of round compression. This technique enables one to take a (distributed) algorithm
that computes an O(1)-approximation of maximum matching in O(log n) independent PRAM phases
and implement a super-constant number of these phases in only a constant number of MPC rounds.

1 Introduction
Over the last decade, massive parallelism became a major paradigm in computing, and we have witnessed
the deployment of a number of very successful massively parallel computation frameworks, such as MapReduce [DG04, DG08], Hadoop [Whi12], Dryad [IBY+ 07], or Spark [ZCF+ 10]. This paradigm and the
corresponding models of computation are rather different from classical parallel algorithms models considered widely in literature, such as the PRAM model. In particular, in this paper, we study the Massive Parallel Computation (MPC) model (also known as Massively Parallel Communication model) that
was abstracted out of capabilities of existing systems, starting with the work of Karloff, Suri, and Vassilvitskii [KSV10, GSZ11, BKS13, ANOY14, BKS14]. The main difference between this model and the
PRAM model is that the MPC model allows for much more (in principle, unbounded) local computation.
This enables it to capture a more “coarse–grained,” and thus, potentially, more meaningful aspect of parallelism. It is often possible to simulate one clock step of PRAM in a constant number of rounds on
MPC [KSV10, GSZ11]. This implies that algorithms for the PRAM model usually give rise to MPC algorithms without incurring any asymptotic blow up in the number of parallel rounds. As a result, a vast
body of work on PRAM algorithms naturally translates to the new model.
It is thus natural to wonder: Are the MPC parallel round bounds “inherited” from the PRAM model
tight? In particular, which problems can be solved in significantly smaller number of MPC rounds than
what the lower bounds established for the PRAM model suggest?
It is not hard to come up with an example of a problem for which indeed the MPC parallel round
number is much smaller than its PRAM round complexity. For instance, computing the parity of n Boolean
values takes only O(1) parallel rounds in the MPC model when space per machine is nΩ(1) , while on
PRAM it provably requires Ω(log n/ log log n) time [BH87] (as long as the total number of processors is
polynomial). However, the answer is typically less obvious for other problems. This is particularly the
case for graph problems, whose study in a variant of the MPC model was initiated already by Karloff et
al. [KSV10].
In this paper, we focus on one such problem, which is also one of the most central graph problems
both in sequential and parallel computations: maximum matching. Maximum matchings have been the
cornerstone of algorithmic research since 1950s and their study inspired many important ideas, including
the complexity class P [Edm65]. In the PRAM model we can compute (1 + ǫ)-approximate matching in
O(log n) rounds
 [LPP15] using randomization. Deterministically, a (2 + ǫ)-approximation can be computed
2
in O log n rounds [FG17]. We note that these results hold in a distributed message passing setting, where
processorsare located at graph
 nodes and can communicate only with neighbors. In such a distributed
p
log n/ log log n time lower bound is known for computing any constant approximation to
setting, Ω
maximum matching [KMW06].
So far, in the MPC setting, the prior results are due to Lattanzi, Moseley, Suri, and Vassilvitskii [LMSV11],
Ahn and Guha [AG15] and Assadi and Khanna [AK17]. Lattanzi et al. [LMSV11] put forth algorithms for
several graph problems, such as connected components, minimum spanning tree, and maximum matching problem, that were based on a so-called filtering technique. In particular, using this technique, they
have obtained an algorithm that can compute a 2-approximation to maximum matching in O(1/δ) MPC
rounds, provided S, the space per machine, is significantly larger than the total number of vertices n, that
is S = Ω n1+δ , for any constant δ ∈ (0, 1). Later on, Ahn and Guha [AG15] provided an improved algorithm that computes a (1+ ǫ)-approximation in O(1/(δǫ)) rounds, provided S = Ω n1+δ , for any constant
δ > 0. Both these results, however, crucially require that space per machine is significantly superlinear in
n, the number of vertices. In fact, if the space S is linear in n, which is a very natural setting for massively

1

parallel graph algorithms, the performance of both these algorithms degrades to O(log n) parallel rounds,
which matches what was known for the PRAM model. Recently, Assadi and Khanna [AK17] showed how
to construct randomized composable coresets of size Õ(n) that give an O(1)-approximation for maximum
√
matching. Their techniques apply to the MPC model only if the space per machine is Õ(n n).
We also note that the known PRAM maximal independent set and maximal matching algorithms [Lub86,
ABI86, II86] can be used to find a maximal matching (i.e., 2-approximation to maximum matching) in
O(log n) MPC rounds as long as space per machine is at least nΩ(1) (i.e., S ≥ nc for some constant c > 0).
We omit further details here, except mentioning that a more or less direct simulation of those algorithms is
possible via an O(1)-round sorting subroutine [GSZ11].
The above results give rise to the following fundamental question: Can the maximum matching be
(approximately) solved in o(log n) parallel rounds in O(n) space per machine? The main result of this
paper is an affirmative answer to that question. We show that, for any S = Ω(n), one can obtain an O(1)approximation to maximum matching using O (log log n)2 parallel MPC rounds. So, not only do we
break the existing Ω(log n) barrier, but also provide an exponential improvement over the previous work.
Our algorithm can also provide a (2 + ǫ), instead of O(1)-approximation, at the expense of the number of
parallel rounds increasing by a factor of O(log(1/ǫ)). Finally, our approach can also provide algorithms
that have o(log n) parallelround complexity also in the regime of S being (mildly) sublinear. For instance,
we obtain O (log log n)2 MPC rounds even if space per machine is S = n/(log n)O(log log n) . The exact
comparison of our bounds with previous results is given in Table 1.

1.1 The model
In this work, we adopt a version of the model introduced by Karloff, Suri, and Vassilvitskii [KSV10] and
refined in later works [GSZ11, BKS13, ANOY14]. We call it massive parallel computation (MPC), which
is a mutation of the name proposed by Beame et al. [BKS13].
In the MPC model, we have m machines at our disposal and each of them has S words of space. Initially,
each machine receives its share of the input. In our case, the input is a collection E of edges and each
machine receives approximately |E|/m of them.
The computation proceeds in rounds. During the round, each of the machines processes its local data
without communicating with other machines. At the end of each round, machines exchange messages. Each
message is sent only to a single machine specified by the machine that is sending the message. All messages
sent and received by each machine in each round have to fit into the machine’s local memory. Hence, their
total length is bounded by S.1 This in particular implies that the total communication of the MPC model is
bounded by m · S in each round. The messages are processed by recipients in the next round.
At the end of the computation, machines collectively output the solution. The data output by each
machine has to fit in its local memory. Hence again, each machine can output at most S words.
The range of values for S and m. If the input is of size N , one usually wants S sublinear in the N , and
the total space across all the machines to be at least N —so the
 input fits onto the machines—and ideally not
much larger. Formally, one usually considers S ∈ Θ N 1−ǫ , for some ǫ > 0.
In this paper, the focus
 is on graph algorithms. If n is the number of vertices in the graph, the input size
can be as large as Θ n2 . Our parallel algorithm requires Θ(n) space per machine (or even slightly less),
which is polynomially less than the size of the input for dense graphs.
1

This for instance allows a machine to send a single word to S/100 machines or S/100 words to one machine, but not S/100
words to S/100 machines if S = ω(1), even if the messages are identical.

2

Sparse graphs. Many practical large graphs are believed to have only O(n) edges. One natural example
is social networks, in which most participants are likely to have a bounded number of friends. The additional
advantage of our approach is that it allows for a small number of processing rounds even if a sparse input
graph does not fit onto a single machine. If a small number—say, f (n)—of
 machines is needed even to
2
store the graph, our algorithm still requires only O (log log n) + log f (n) rounds for O(n/f (n)) space
per machine.
Communication vs. computation complexity. The main focus of this work is the number of (communication) rounds required to finish computation. Also, even though we do not make an effort to explicitly bound
it, it is apparent from the design of our algorithms that every machines performs O(S polylog S) computation steps locally. This in particular implies that the overall work across all the machines is O(rN polylog S),
where r is the number of rounds and N is the input size (i.e., the number of edges).

The total communication during the computation is O(rN ) words. This is at most O rn2 words
and it is known that computing a (1 + ǫ)-approximate
matching in the message passing model with Θ(n)

edges per player may require Ω n2 /(1 + ǫ)2 bits of communication [HRVZ15]. Since our value of r is

O (log log n)2 when Θ(n) edges are assigned to each player, we lose a factor of Θ̃(log n) compared to
this lower bound if words (and vertex identifiers) have Θ(log n) bits.

1.2 Our results
In our work, we focus on computing an O(1)-approximate maximum matching in the MPC model. We
collect our results and compare to the previous work in Table 1. The table presents two interesting regimes
Source

Approx.

Space
1+Ω(1)

[LMSV11]

2

n
O(n)

[AG15]

1+ǫ

O n1+1/p

2

nΩ(1)

O(1)



O(n)

2+ǫ
here

O(1)
2+ǫ

O(n)/f (n)

Rounds

Remarks

O(1)
O(log n)

Maximal matching

O(p/ǫ)
O(log n)
O (log log n)2




O (log log n)2 · log(1/ǫ)

O (log log n)2 + log f (n)

O (log log n)2 + log f (n) · log(1/ǫ)

p>1
Maximal matching
Simulate [Lub86, ABI86, II86]
ǫ ∈ (0, 1/2)

2 ≤ f (n) = O n1/2



Table 1: Comparison of our results for computing approximate maximum size matchings to the previous
results for the MPC model.
for our algorithms. On the one hand, when the space per machine is S = O(n), we obtain an algorithm
that requires O((log log n)2 ) rounds. This is the first known algorithm that, with linear space per machine,
breaks the O(log n) round barrier. On the other hand, in the mildly sublinear regime of space per machine,
i.e., when S = O(n/f (n)), for some function f (n) that is no(1) , we obtain an algorithm that still requires
o(log n) rounds. This, again is the first such result in this regime. In particular, we prove the following
result.

3

Theorem 1.1. There exists an MPC algorithm that constructs 
an O(1)-approximation to maximum matching
n
2
with constant probability in O (log log n) + max log S , 0 rounds, where S = nΩ(1) is the amount of
space on each machine.
As a corollary, we obtain the following result that provides nearly 2-approximate maximum matching.
Corollary 1.2. For any ǫ ∈ (0, 21 ), there exists an MPC algorithm that constructsa (2+ǫ)-approximation to
maximum matching with 99/100 probability in O (log log n)2 + max log Sn , 0 · log(1/ǫ) rounds, where
S = nΩ(1) is the amount of space on each machine.
Assadi et al. [ABB+ 17] observe that one can use a technique of McGregor [McG05] to extend the
algorithm to compute a (1 + ǫ)-approximation in O((log log n)2 ) · (1/ǫ)O(1/ǫ) rounds.
It should also be noted that (as pointed out to us by Seth Pettie) any O(1)-approximation algorithm for
unweighted matchings can be used to obtain a (2 + ǫ)-approximation algorithm for weighted matchings (see
Section 4 of his paper with Lotker and Patt-Shamir [LPP15] for details). In our setting this implies that
Theorem 1.1 yields an algorithm that computes a (2 + ǫ)-approximation to maximum weight matching in
O((log log n)2 · (1/ǫ)) rounds and O(n log n) space per machine.

1.3 Related work
We note that there were efforts at modeling MapReduce computation [FMS+ 10] before the work of Karloff
et al. Also a recent work [RVW16] investigates the complexity of the MPC model.
In the filtering technique, introduced by Lattanzi et al. [LMSV11], the input graph is iteratively sparsified
until it can be stored on a single machine. For the matching problem, the sparsification is achieved by first
obtaining a small sample of edges, then finding a maximal matching in the sample, and finally removing
all the matched vertices. Once a sufficiently small graph is obtained, a maximal matching is computed on
a single machine. In the S = Θ(n) regime, the authors show that their approach reduces the number of
edges by a constant factor in each iteration. Despite this guarantee, until the very last step, each iteration
may make little progress towards obtaining even an approximate maximal matching, resulting in a O(log n)
round complexity of the algorithm. Similarly, the results of Ahn and Guha [AG15] require n1+Ω(1) space
per machine to compute a O(1)-approximate maximum weight matching in a constant number of rounds
and do not imply a similar bound for the case of linear space.
We note that the algorithm of Lattanzi et al. [LMSV11] cannot be turned easily into a fast approximation
algorithm when space per machine is sublinear. Even with Θ(n) space, their method is able to remove only
a constant fraction of edges from the graph in each iteration, so Ω(log n) rounds are needed until only a
matching is left. When S = Θ(n), their algorithm works as follows: sample uniformly at random Θ(n)
edges of the graph, find maximal matching on the sampled set, remove the matched vertices, and repeat.
We do not provide a formal proof here, but on the following graph this algorithm requires Ω̃(log n) rounds,
even to discover a constant factor approximation. Consider a graph consisting of t separate regular graphs
of degree 2i , for 0 ≤ i ≤ t − 1, each on 2t vertices. This graph has t2t nodes and the algorithm requires Ω̃(t)
rounds even to find a constant approximate matching. The algorithm chooses edges uniformly at random,
and few edges are selected each round from all but the densest remaining subgraphs. Thus, it takes multiple
rounds until a matching of significant size is constructed for sparser subgraphs. This example emphasizes
the weakness of direct edge sampling and motivates our vertex sampling scheme that we introduce in this
paper.
Similarly, Ahn and Gupta [AG15] build on the filtering approach of Lattanzi et al. and design a primaldual method for computing a (1 + ǫ)-approximate weighted maximum matching. They show that each
4

iteration of their distributed algorithm either makes large progress in the dual, or they can construct a large
approximate matching. Regardless of their new insights, their approach is inherently edge-sampling based
and does not break the O(log n) round complexity barrier when S = O(n).
Despite the fact that MPC model is rather new, computing matching is an important problem in this
model, as the above mentioned two papers demonstrate. This is further witnessed by the fact that the
distributed and parallel complexity of maximal matching has been studied for many years already. The best
deterministic PRAM maximal matching algorithm, due to Israeli and Shiloach [IS86], runs in O log3 n
rounds. Israeli and Itai [II86] gave a randomized algorithm for this problem that runs in O(log n) rounds.
Their algorithm works as well in CONGEST, a distributed message-passing model with a processor assigned
to each vertex and a limit on the amount of information sent along each edge per round. A more recent paper
by Lotker, Patt-Shamir, and Pettie [LPP15] gives a (1+ǫ)-approximation to maximum matching in O(log n)
rounds also in the CONGEST model, for any constant ǫ > 0. On the deterministic front, in the LOCAL
model, which is a relaxation of CONGEST that allows for an arbitrary amount of data sent along each edge,

a line of research initiated by Hańćkowiak, Karoński, and Panconesi [HKP01, HKP99] led to an O log3 n round algorithm by Fischer and Ghaffari [FG17].
On the negative side, Kuhn, Moscibroda, and Wattenhofer [KMW06] showed that any distributed
algo
p
log n/ log log n
rithm, randomized or deterministic, when communication is only between neighbors requires Ω
rounds to compute a constant approximation to maximum matching. This lower bound applies to all distributed algorithms that have been mentioned above. Our algorithm circumvents this lower bound by loosening the only possible assumption there is to be loosened: single-hop communication. In a sense, we assign
subgraphs to multiple machines and allow multi-hop communication between nodes in each subgraph.
Finally, the ideas behind the peeling algorithm that is a starting point for this paper can be traced back
to the papers of Israeli, Itai, and Shiloach [II86, IS86], which can be interpreted as matching high-degree
vertices first in order to reduce the maximum degree. A sample distributed algorithm given in a work
of Parnas and Ron [PR07] uses this idea to compute an O(log n) approximation for vertex cover. Their
algorithm was extended by Onak and Rubinfeld [OR10] in order to provide an O(1)-approximation for
vertex cover and maximum matching in a dynamic version of the problems. This was achieved by randomly
matching high-degree vertices to their neighbors in consecutive phases while reducing the maximum degree
in the remaining graph. This approach was further developed in the dynamic graph setting by a number of
papers [BHI15, BHN16, BHN17, BCH17]. Ideas similar to those in the paper of Parnas and Ron [PR07]
were also used to compute polylogarithmic approximation in the streaming model by Kapralov, Khanna,
and Sudan [KKS14]. Our version of the peeling algorithm was directly inspired by the work of Onak and
Rubinfeld [OR10] and features important modifications in order to make our analysis go through.

1.4 Future challenges
We show a parallel matching algorithm in the MPC model by taking an algorithm that can be seen as a
distributed algorithm in the so-called LOCAL model. This algorithm requires Θ(log n) rounds and can
be simulated in Θ(log n) MPC rounds relatively easily with nΩ(1) space per machine. We develop an approximate version of the algorithm that uses much fewer rounds by repeatedly compressing a superconstant
number of rounds of the original algorithm to O(1) rounds. It is a great question if this kind of speedup can
be obtained for other—either distributed or PRAM—algorithms.
As for the specific problem considered in this paper, an obvious question is whether our round complexity is optimal. We conjecture that there is a better algorithm that requires O(log log n) rounds, the square
root of our complexity. Unfortunately, a factor of log n in one of our functions (see the logarithmic factor in

5

α, a parameter defined later in the paper) propagates to the round complexity, where it imposes a penalty of
log log n.
Note also that as opposed to the paper of Onak and Rubinfeld [OR10], we do not obtain an O(1)approximation to vertex cover. This stems from the fact that we discard so-called reference sets, which can
be much bigger than the minimum vertex cover. This is unfortunately necessary in our analysis. Is there a
way to fix this shortcoming of our approach?
Finally, we suspect that there is a simpler algorithm for the problem that avoids the intricacies of our
approach and proceeds by simply greedily matching high-degree vertices on induced subgraphs without
sophisticated sampling in every phase. Unfortunately, we do not know how to analyze this kind of approach.

1.5 Recent developments
Since an earlier version of this work was shared on arXiv, it has inspired two followup works. First, Assadi [Ass17] applied the round compression idea to the distributed O(log n)-approximation algorithm for
vertex cover of Parnas and Ron [PR07]. Using techniques from his recent work with Khanna [AK17], he
gave a simple MPC algorithm that in O(log log n) rounds and n/ polylog(n) space per machine computes
an O(log n)-approximation to minimum vertex cover.
Second, a new paper by Assadi et al. [ABB+ 17] addresses, among other things, several open questions
from this paper. They give an MPC algorithm that computes O(1)-approximation to both vertex cover
and maximum matching in O(log log n) rounds and Õ(n) space per machine (though the space is strictly
superlinear). Their result builds on techniques developed originally for dynamic matching algorithms [BS15,
BS16] and composable coresets [AK17]. It is worth to note that their construction critically relies on the
vertex sampling approach (i.e., random assignment of vertices to machines) introduced in our work.

1.6 Notation
For a graph G = (V, E) and V ′ ⊆ V , we write G[V ′ ] to denote the subgraph of G induced by V ′ . Formally,
def
G[V ′ ] = (V ′ , E ∩ (V ′ × V ′ )). We also write N (v) to denote the set of neighbors of a vertex v in G.

2 Overview
In this section we present the main ideas and techniques behind our result. Our paper contains two main
technical contributions.
First, our algorithm randomly partitions vertices across the machines, and on each machine considers
only the corresponding induced graph. We prove that it suffices to consider these induced subgraphs to
obtain an approximate maximum matching. Note that this approach greatly deviates from previous works,
that used edge based partitioning.
Second, we introduce a round compression technique. Namely, we start with an algorithm that executes
O(log n) phases and can be naturally implemented in O(log n) MPC rounds and then demonstrate how to
emulate this algorithm using only o(log n) MPC rounds. The underlying idea is quite simple: each machine
independently runs multiple phases of the initial algorithm. This approach, however, has obvious challenges
since the machines cannot communicate in a single round of the MPC algorithm. The rest of the section is
devoted to describing our approach and illustrating how to overcome these challenges.

6

2.1 Vertex based sampling
The algorithms for computing maximal matching in PRAM and their simulations in the MPC model [Lub86,
ABI86, IS86, II86] are designed to, roughly speaking, either halve the number of the edges or halve the
maximum degree in each round. Therefore, in the worst case those algorithms inherently require Ω(log n)
rounds to compute a maximal matching.
On the other hand, all the algorithm for the maximal matching problem in the MPC model prior to
ours ([LMSV11, AG15, AK17]) process the input graph by discarding edges, and eventually aggregate the
remaining edges on a single machine to decide which of them are part of the final matching. It is not known
how to design approaches similar to [LMSV11, AG15, AK17] while avoiding a step in which the maximal
matching computation is performed on a single machine. This seems to be a barrier for improving upon
O(log n) rounds, if the space available on each machine is O(n).
The starting point of our new approach is alleviating this issue by resorting to a more careful vertex based
sampling. Specifically, at each round, we randomly partition the vertex set into vertex sets V1 , . . . , Vm and
consider induced graphs on those subsets independently. Such sampling scheme has the following handy
property: the union of matchings obtained across the machines is still a matching. Furthermore, we show
that for the appropriate setting of parameters this sampling scheme allows us to handle vertices of a wide
range of degrees in a single round, unlike handling only high-degree vertices (that is, vertices with degree
within a constant factor of the maximum degree) as guaranteed by [II86, IS86].

2.2 Global algorithm
To design an algorithm executed on machines locally, we start from a sequential peeling algorithm GlobalAlg
(see Algorithm 1), which is a modified version of an algorithm used by Onak and Rubinfeld [OR10]. The
algorithm had to be significantly adjusted in order to make our later analysis of a parallel version possible.
The execution of GlobalAlg is divided into Θ(log n) phases. In each phase, the algorithm first computes a set H of high-degree vertices. Then it selects a set F of vertices, which we call friends. Next the
f between H and F , using a simple randomized strategy. F is carefully conalgorithm selects a matching M
f are likely to be of order Θ(|H|). Finally, the algorithm removes all vertices in
structed so that both F and M
H ∪F , hence reducing the maximum vertex degree in the graph by a constant factor, and proceeds to the next
phase. The central property of GlobalAlg is that it returns an O(1) approximation to maximum matching
with constant probability (Corollary 3.4). A detailed discussion of GlobalAlg is given in Section 3.
e
Algorithm 1: GlobalAlg(G, ∆)
Global matching algorithm
1
2

3
4
5
6
7

e
Input: Graph G = (V, E) of maximum degree at most ∆
Output: A matching in G
e M ← ∅, V ′ ← V
∆ ← ∆,
while ∆ ≥ 1 do
/* Invariant: the maximum degree in G[V ′ ] is at most ∆ */
Let H ⊂ V ′ be a set of vertices of degree at least ∆/2 in G[V ′ ]. We call vertices in H heavy.
Create a set F of friends by selecting each vertex v ∈ V ′ independently with probability |N (v) ∩ H|/4∆.
f in G[H ∪ F ] using MatchHeavy(H, F ) and add it to M .
Compute a matching M
V ′ ← V ′ \ (H ∪ F ), ∆ ← ∆/2
return M

7

Algorithm 2: MatchHeavy(H, F )
Computing a matching in G[H ∪ F ]
Input: set H of heavy vertices and set F of friends
Output: a matching in G[H ∪ F ]

1
2
3
4
5

For every vertex v ∈ F pick uniformly at random a heavy neighbor v⋆ in N (v) ∩ H.
Independently at random color each vertex in H ∪ F either red or blue.
Select the following subset of edges: E⋆ ← {(v, v⋆ ) : v ∈ F ∧ v is red ∧ v⋆ ∈ H ∧ v⋆ is blue}.
f.
For every blue vertex w incident to an edge in E⋆ , select one such edge and add it to M
f
return M

2.3 Parallel emulation of the global algorithm (Section 4)
The following two ways could be used to execute GlobalAlg in the MPC model: (1) place the whole
graph on one machine, and trivially execute all the phases of GlobalAlg in a single round; or (2) simulate
one phase of GlobalAlg in one MPC round while using O(n) space per machine, by distributing vertices
randomly onto machines (see Section 6.1 for details). However, each of these approaches has severe drawbacks. The first approach requires Θ(|E|) space per machine, which is likely to be prohibitive for large
graphs. On the other hand, while the second approach uses O(n) space, it requires Θ(log n) rounds of MPC
computation. We achieve the best of both worlds by showing how to emulate the behavior of multiple phases
of GlobalAlg in a single MPC round with each machine using O(n) space, thus obtaining an MPC algorithm requiring o(log n) rounds. More specifically, we show that it is possible to emulate the behavior of
GlobalAlg in O (log log n)2 rounds with each machine using O(n) (or even only n/(log n)O(log log n) )
space.
Before we provide more details about our parallel multi-phase emulation of GlobalAlg, let us mention
the main obstacle such an emulation encounters. At the beginning of every phase, GlobalAlg has access
to the full graph. Therefore, it can easily compute the set of heavy vertices H. On the other hand, machines
in our MPC algorithm use O(n) space and thus have access only to a small subgraph of the input graph
(when |E| ≫ n). In the first phase this is not a big issue, as, thanks to randomness, each machine can
estimate the degrees of high-degree vertices. However, the degrees of vertices can significantly change from
phase to phase. Therefore, after each phase it is not clear how to select high-degree vertices in the next
phase without inspecting the entire graph again. Hence, one of the main challenges in designing a multiphase emulation of GlobalAlg is to ensure that machines at the beginning of every phase can estimate
global degrees of vertices well enough to identify the set of heavy vertices, while each machine still having
access only to its local subgraph. This property is achieved using a few modifications to the algorithm.
2.3.1

Preserving randomness

Our algorithm partitions the vertex set into m disjoint subsets Vi by assigning each vertex independently
and uniformly at random. Then the graph induced by each subset Vi is processed on a separate machine.
Each machine finds a set of heavy vertices, Hi , by estimating the global degree of each vertex of Vi . It is not
hard to argue (using a standard concentration bound) that there is enough randomness in the initial partition
so that local degrees in each induced
S subgraph roughly correspond to the global degrees. Hence, after the
described partitioning, sets H and i∈[m] Hi have very similar properties. This observation crucially relies
on the fact that initially the vertices are distributed independently and uniformly at random.
However, if one attempts to execute the second phase of GlobalAlg without randomly reassigning
8

vertices to sets after the first phase, the remaining vertices are no longer distributed independently and
uniformly at random. In other words, after inspecting the neighborhood of every vertex locally and making
a decision based on it, the randomness of the initial random partition may significantly decrease.
Let us now make the following thought experiment. Imagine for a moment that there is an algorithm
that emulates multiples phases of GlobalAlg in parallel and in every phase inspects only the vertices that
end-up being matched. Then, from the point of view of the algorithm, the vertices that are not matched so
far are still distributed independently and uniformly at random across the machines. Or, saying in a different
way, if randomness of some vertices is not inspected while emulating a phase, then at the beginning of the
next phase those vertices still have the same distribution as in the beginning of that MPC round. But, how
does an algorithm learn about vertices that should be matched by inspecting no other vertex? How does the
algorithm learn even only about high-degree vertices without looking at their neighborhood?
In the sequel we show how to design an algorithm that looks only "slightly" at the vertices that do not end-up
being matched. As we prove, that is sufficient to design a multi-phase emulation of GlobalAlg.
We now discuss in more detail how to preserve two crucial properties of our vertex assignments throughout the execution of multiple phases: independent and nearly-uniform distribution.
2.3.2

Independence (Lemma 4.3)

As noted above, it is not clear how to compute vertex degrees without inspecting their local neighborhood.
A key, and at first sight counter-intuitive, step in our approach is to estimate even local degrees of vertices
(in contrast to computing them exactly). To obtain the estimates, it suffices to examine only small neighborhoods of vertices and in turn preserve the independent distribution of the intact ones. More precisely, we
sample a small set of vertices on each machine, called reference sets, and use the set to estimate the local
degrees of all vertices assigned to this machine. Furthermore, we show that with a proper adjustments of
GlobalAlg these estimates are sufficient for capturing high-degree vertices.
Very crucially, all the vertices that are used in computing a matching in one emulated phase (including
the reference sets) are discarded at the end of the phase, even if they do not participate in the obtained
matching. In this way we disregard the vertices which position is fixed and, intuitively, secure an independent distribution of the vertices across the machines in the next phase.
We also note, without going into details, that obtaining full independence required modifying how the
set of friends is selected, compared to the original approach of Onak and Rubinfeld [OR10]. In their approach, each heavy vertex selected one friend at random. However, as before, in order to select exactly one
friend would require examining neighborhood of heavy vertices. This, however, introduces dependencies
between vertices that have not been selected. So instead, in our GlobalAlg, every vertex selects itself as
a friend independently and proportionally to the number of high-degree vertices (found using the reference
set), which again secures an independent distribution of the remaining vertices. The final properties of the
obtained sets in either approach are very similar.
2.3.3

Uniformity (Lemma 4.4)

A very convenient property in the task of emulating multiple phases of GlobalAlg is a uniform distribution
of vertices across all the machines at every phase – for such a distribution, we know the expected number of
neighbors of each desired type assigned to the same machine. Obtaining perfect uniformity seems difficult—
if not impossible in our setting—and we therefore settle for near uniformity of vertex assignments. The
probability of the assignment of each vertex to each machine is allowed to differ slightly from that in the
uniform distribution. Initially, the distribution of each vertex is uniform and with every phase it can deviate
9

more and more from the uniform distribution. We bound the rate of the decay with high probability and
execute multiple rounds as long as the deviation from the uniform distribution is negligible. More precisely,
in the execution
 of the entire parallel algorithm, the sufficiently uniform distribution is on average kept over
log n
Ω (log log n)2 phases of the emulation of GlobalAlg.

µH (r)

1

1
2

1
2

1

r

Figure 1: An idealized version of µH : R → [0, 1], in which n was fixed to a small constant and the
multiplicative constant inside the exponentiation operator was lowered.
In order to achieve the near uniformity, we modify the procedure for selecting H, the set of high-degree
vertices. Instead of a hard threshold on the degrees of vertices that are included in H as in the sequential
algorithm, we randomize the selection by using a carefully crafted threshold function µH . This function
specifies the probability with which a vertex is included in H. It takes as input the ratio of the vertex’s degree
to the current maximum degree (or, more precisely, the current upper bound on the maximum degree) and
it smoothly transitions from 0 to 1 in the neighborhood of the original hard threshold (see Figure 1). The
main intuition behind the introduction of this function is that we want to ensure that a vertex is not selected
for H with almost the same probability, independently of the machine on which it resides. Using a hard
threshold instead of µH could result in the following deficiency. Consider a vertex v that has slightly too
few neighbors to qualify as a heavy vertex. Still, it could happen, with a non-negligible probability, that the
reference set of some machine contains so many neighbors of v that v would be considered heavy on this
machine. However, if v is not included in the set of heavy vertices on that machine, it becomes clear after
even a single phase that the vertex is not on the given machine, i.e. the vertex is on the given machine with
probability zero. At this point the distribution is clearly no longer uniform.
Function µH has further useful properties that we extensively exploit in our analysis. We just note that
in order to ensure near uniformity with high probability, we also have to ensure that each vertex is selected
for F , the set of friends, with roughly the same probability on each machine.

2.4 Organization of the appendix
The appendix presents the details of our techniques. We start by analyzing GlobalAlg in Section 3. Then,
Section 4 describes how to emulate of a single phase of GlobalAlg in the MPC model. Section 5 gives
and analyzes our parallel algorithm by putting together components developed in the previous sections. The
resulting parallel algorithm can be implemented in the MPC model in a fairly straightforward way by using
the result of [GSZ11]. The details of the implementation are given in Section 6.
10

3 Global Algorithm
3.1 Overview
The starting point of our result is a peeling algorithm GlobalAlg that takes as input a graph G, and
removes from it vertices of lower and lower degree until no edge is left. See page 7 for its pseudocode. We
use the term phase to refer to an iteration of the main loop in Lines 2–6.
e the upper bound on the maximum
Each phase is associated with a threshold ∆. Initially, ∆ equals ∆,
vertex degree. In every phase, ∆ is divided by two until it becomes less than one and the algorithm stops.
Since during the execution of the algorithm we maintain the invariant that the maximum degree in the graph
is at most ∆, the graph has no edge left when the algorithm terminates.
In each phase the algorithm matches, in expectation, a constant fraction of the vertices it removes. We
use this fact to prove that, across all the phases, the algorithm computes a constant-factor approximate
matching.
We now describe in more detail the execution of each phase. First, the algorithm creates H, the set
of vertices that have degree at least ∆/2 (Line 3). We call these vertices heavy. Then, the algorithm uses
randomness to create F , a set of friends (Line 4). Each vertex v is independently included in F with
probability equal to the number of its heavy neighbors divided by 4∆. We show that E [|F |] = O(|H|)
and G[H ∪ F ] contains a matching of expected size Ω(|H|). This kind of matching is likely found by
MatchHeavy in Line 5.
Note that GlobalAlg could as well compute a maximal matching in G[H ∪ F ] instead of calling
MatchHeavy. However, for the purpose of the analysis, using MatchHeavy is simpler, as we can directly
relate the size of the obtained matching to the size of H. In addition, we later give a parallel version of
GlobalAlg, and MatchHeavy is easy to parallelize.
At the end of the phase, vertices in both H and F are removed from the graph, while the matching found
in G[H ∪ F ] is added to the global matching being constructed. It is easy to see, that by removing H, the
algorithm ensures that no vertex of degree larger than ∆/2 remains in the graph, and therefore the bound on
the maximum degree decreases by a factor of two.

3.2 Analysis
We start our analysis of the algorithm by showing that the execution of MatchHeavy in each phase of
GlobalAlg finds a relatively large matching in expectation.
Lemma 3.1. Consider onehphasei of GlobalAlg. Let H be the set of heavy vertices. MatchHeavy finds
f such that E M
f ≥ 1 |H|.
a matching M
40

Proof. Observe that the set E⋆ is a collection of vertex-disjoint stars: each edge connects a red vertex with
a blue vertex and the red vertices have degree 1. Thus, a subset of E⋆ forms a valid matching as long as no
f in
blue vertex is incident to two matched edges. Note that this is guaranteed by how edges are added to M
Line 4.
The size of the computed matching is the number of blue vertices in H that have at least one incident
edge in E⋆ . Let us now lower bound the number of such vertices. Consider an arbitrary u ∈ H. It has the
desired properties exactly when the following three independent events happen: some v ∈ F selects u in
Line 1, u is colored blue, and v is colored red. The joint probability of the two latter events is exactly 14 . The

11

probability that u is not selected by some v ∈ F is

′





 

1 ∆/2
1 ∆
1
9
1 |N (u)∩V |
·
≤ 1−
≤ exp −
≤ exp −
≤ .
1−
4∆
4∆
4∆ 2
8
10

1
. Therefore, with probability
This implies that u is selected by a neighbor v ∈ F with probability athleast i10
f ≥ 1 |H|.
at least 1 · 1 = 1 , u is blue and incident to an edge in E⋆ . Hence, E M
10

4

40

40

Next we show an upper bound on the expected size of F , the set of friends.

Lemma 3.2. Let H be the set of heavy vertices selected in a phase of GlobalAlg. The following bound
holds on the expected size of F , the set of friends, created in the same phase: E [|F |] ≤ 14 |H|.
Proof. At the beginning of a phase, every vertex u ∈ V ′ —including those in H—has its degree, |N (u)∩V ′ |,
bounded by ∆. Reversing the order of the summation and applying this fact, we get:
E [|F |] =

X |N (u) ∩ V ′ |
X |N (v) ∩ H|
|H| · ∆
|H|
=
≤
=
.
4∆
4∆
4∆
4
′
u∈H

v∈V

We combine the last two bounds to lower bound the expected size of the matching computed by GlobalAlg.
e on the maximum vertex degree. GlobalAlg(G, ∆)
e
Lemma 3.3. Consider an input graph G with an upper bound ∆
def
e + 1 phases. Let Hi , Fi , and M
fi be the sets H, F , and M
f constructed in phase i for
executes T = ⌊log ∆⌋
i ∈ [T ]. The following relationship holds on the expected sizes of these sets:
T
T
i
h
X
1 X
f
E [|Hi | + |Fi |]
E Mi ≥
50
i=1

i=1

Proof. For each phase i ∈ [T ], by applying the expectation over all possible settings of the set Hi , we learn
from Lemmas 3.1 and 3.2 that
i
h
1
fi ≥ 1 E [|Hi |]
E M
and
E [|Fi |] ≤ E [|Hi |] .
40
4

It follows that

h
i
1
1
1
1
fi ,
E [|Hi | + |Fi |] ≤
E [|Hi |] +
E [|Hi |] =
E [|Hi |] ≤ E M
50
50
200
40

and the statement of the lemma follows by summing over all phases.

We do not use this fact directly in our paper, but note that the last lemma can be used to show that
GlobalAlg can be used to find a large matching.
Corollary 3.4. GlobalAlg computes a constant factor approximation to the maximum matching with
Ω(1) probability.
Proof. First, note that GlobalAlg finds a correct matching, i.e., no two different edges in M share an
endpoint. This is implied by the fact that M is extended in every phase by a matching on a disjoint set of
vertices.
12

fi for i ∈ [T ] be defined as in the statement of Lemma 3.3. Let MOPT be a
Let T and sets Hi , Fi , and M
maximum matching in the graph. Observe that at the end of the algorithm execution, the remaining graph is
empty. This implies that the size of the maximum matching can be bounded by the total number of removed
vertices, because each removed vertex decreases the maximum matching size by at most one:
T
X
i=1

|Hi | + |Fi | ≥ |MOPT | .

Hence, using Lemma 3.3,
E [|M |] =

T
T
i
h
X
X
1
fi ≥ 1
E M
|MOPT | .
E [|Hi | + |Fi |] ≥
50
50
i=1

i=1

1
1
Since |M | ≤ |MOPT |, |M | ≥ 100
|MOPT | with probability at least 100
. Otherwise, E [|M |] would be
1
1
1
strictly less than 100 · |MOPT | + 1 · 100 |MOPT | = 50 |MOPT |, which is not possible.

4 Emulation of a Phase in a Randomly Partitioned Graph
In this section, we introduce a modified version of a single phase (one iteration of the main loop) of
GlobalAlg. Our modifications later allow for implementing the algorithm in the MPC model. The pseudocode of the new procedure, EmulatePhase, is presented as Algorithm 3. We partition the vertices of
the current graph into m sets Vi , 1 ≤ i ≤ m. Each vertex is assigned independently and almost uniformly at
random to one of the sets. For each set Vi , we run a subroutine LocalPhase (presented as Algorithm 4).
This subroutine runs a carefully crafted approximate version of one phase of GlobalAlg with an appropriately rescaled threshold ∆. More precisely, the threshold passed to the subroutine is scaled down by a factor
of m, which corresponds to how approximately vertex degrees decrease in subgraphs induced by each of
the sets. The main intuition behind this modification is that we hope to break the problem up into smaller
subproblems on disjoint induced subgraph, and obtain similar global properties by solving the problem approximately on each smaller part. Later, in Section 5, we design an algorithm that assigns the subproblems
to different machines and solves them in parallel.
Algorithm 3: EmulatePhase(∆, G⋆ , m, D)
Emulation of a single phase in a randomly partitioned graph
Input:
• threshold ∆
• induced subgraph G⋆ = (V⋆ , E⋆ ) of maximum degree 23 ∆
• number m of subgraphs
• ǫ-near uniform and independent distribution D on assignments of V⋆ to [m]
Output: Remaining vertices and a matching
1
2
3
4
5

Pick a random assignment Φ : V⋆ → [m] from D
for i ∈ [m] do
Vi ← {v ∈ V⋆ : Φ(v) = i}
(Vi′ , Mi ) ← LocalPhase(i, G⋆ [Vi ], ∆/m)
Sm
Sm
return ( i=1 Vi′ , i=1 Mi )

/* LocalPhase = Algorithm 4 */

13

A multiplicative constant used in the exponent of µH :
def

α = 96 ln n.
The probability of the selection for a reference set:
def

µR = 106 · log n

−1

.

The probability of the selection for a heavy set (used with r equal to the ratio of the
estimated degree to the current threshold):
(

1
exp α2 (r − 1/2)
if r ≤ 1/2,
def
2

µH (r) =
1 − 12 exp − α2 (r − 1/2) if r > 1/2.
The probability of the selection for the set of friends (used with r equal to the ratio of
the number of heavy neighbors to the current threshold):
(
max{r/4, 0} if r ≤ 4,
def
µF (r) =
1
if r > 4.

Table 2: Global parameters α ∈ (1, ∞) and µR ∈ (0, 1) and functions µH : R → [0, 1] and µF : R → [0, 1]
used in the parallel algorithm. α, µR , and µH depend on n, the total number of vertices in the graph.
We now discuss LocalPhase (i.e., Algorithm 4) in more detail. Table 2 introduces two parameters, α
and µR , and two functions, µH and µF , which are used in LocalPhase. Note first that α is a parameter
used in the definition of µH but it is not used in the pseudocode of LocalPhase (or EmulatePhase)
for anything else. It is, however, a convenient abbreviation in the analysis and the later parallel algorithm.
The other three mathematical objects specify probabilities with which vertices are included in sets that are
created in an execution of LocalPhase.
Apart from creating its own versions of H, the set of heavy vertices, and F , the set of friends, LocalPhase
constructs also a set Ri , which we refer to as a reference set. In Line 1, the algorithm puts each vertex in
Ri independently and with the same probability µR . The reference set is used to estimate the degrees of
other vertices in the same induced subgraph in Line 2. For each vertex vi , its estimate dbv is defined as
the number of v’s neighbors in Ri multiplied by µ−1
R to compensate for sampling. Next, in Line 3, the
algorithm uses the estimates to create Hi , the set of heavy vertices. Recall that GlobalAlg uses a sharp
threshold for selecting heavy vertices: all vertices of degree at least ∆/2 are placed in Hi . LocalPhase
works differently. It divides the degree estimate by the current threshold ∆⋆ and uses function µH to decide
with what probability the corresponding vertex is included in Hi . A sketch of the function can be seen in
Figure 1. The function transitions from almost 0 to almost 1 in the neighborhood of 12 at a limited pace.
As a result vertices of degrees smaller than, say, 41 ∆ are very unlikely to be included in Hi and vertices of
degree greater than 34 ∆ are very likely to be included in Hi . GlobalAlg can be seen as an algorithm that
instead of µH , uses a step function that equals 0 for arguments less than 21 and abruptly jumps to 1 for larger
arguments. Observe that without µH , the vertices whose degrees barely qualify them as heavy could behave
very differently depending on which set they were assigned to. We use µH to guarantee a smooth behavior
in such cases. That is one of the key ingredients that we need for making sure that a set of vertices that

14

Algorithm 4: LocalPhase(i, Gi , ∆⋆ )
Emulation of a single phase on an induced subgraph
Input:
• induced subgraph number i (useful only for the analysis)
• induced subgraph Gi = (Vi , Ei )
• threshold ∆⋆ ∈ R+
Output: Remaining vertices and a matching on Vi
1
2
3
4

5
6

Create a reference set Ri by independently selecting each vertex in Vi with probability µR .
For each v ∈ Vi , dbv ← |N (v) ∩ Ri |/µR .



Create a set Hi of heavy vertices by independently selecting each v ∈ Vi with probability µH dbv /∆⋆ .
Create a set Fi of friends by independently selecting each vertex in v ∈ Vi with probability
µF (|N (v) ∩ Hi |/∆⋆ ).
Compute a maximal matching Mi in G[Hi ∪ Fi ].
return (Vi \ (Ri ∪ Hi ∪ Fi ), Mi )

remains on one machine after a phase has almost the same statistical properties as a set of vertices obtained
by new random partitioning.
Finally, in Line 4, LocalPhase creates a set of friends. This step is almost identical to what happens
in the global algorithm. The only difference is that this time we have no upper bound on the number of
heavy neighbors of a vertex. As a result that number divided by 4∆⋆ can be greater than 1, in which case
we have to replace it with 1 in order to obtain a proper probability. This is taken care of by function µF .
Once Hi and Fi have been created, the algorithm finds a maximal matching Mi in the subgraph induced
by the union of these two sets. The algorithm discards from the further consideration not only Hi and Fi ,
but also Ri . This eliminates dependencies in the possible distribution of assignments of vertices that have
not been removed yet if we condition this distribution on the configuration of sets that have been removed.
Intuitively, the probability of a vertex’s inclusion in any of these sets depends only on Ri and Hi but not on
any other vertices. Hence, once we fix the sets of removed vertices, the assignment of the remaining vertices
to subgraphs is fully independent.2 The output of LocalPhase is a subset of Vi to be considered in later
phases and a matching Mi , which is used to expand the matching that we construct for the entire input
graph. We now introduce additional concepts and notation. They are useful for describing and analyzing
properties of the algorithm. A configuration describes sets Ri , Hi , and Fi , for 1 ≤ i ≤ m, constructed
in an execution of EmulatePhase. We use it for conditioning a distribution of vertex assignments as
described in the previous paragraph. We also formally define two important properties of distributions of
vertex assignments: independence and near uniformity.
Configurations. Let m and V⋆ be the parameters to EmulatePhase: the number of subgraphs and the
set of vertices in the graph to be partitioned, respectively. We say that

C = {Ri }i∈[m] , {Hi }i∈[m] , {Fi }i∈[m]

is an m-configuration if it represents a configuration of sets Ri , Hi , and Fi created by EmulatePhase in
the simulation of a phase. Recall that for any i ∈ [m], Ri , Hi , and Fi are the sets created (and removed) by
2
By way of comparison, consider observing an experiment in which we toss the same coin twice. The bias of the coin is not
fixed but comes from a random distribution. If we do not know the bias, the outcomes of the coin tosses are not independent.
However, if we do know the bias, the outcomes are independent, even though they have the same bias.

15

the execution of LocalPhase for Vi , the i-th subset of vertices.
We say that a vertex v is fixed by C if it belongs to one of the sets in the configuration, i.e.,
[
v∈
(Ri ∪ Hi ∪ Fi ) .
i∈[m]

Conditional distribution. Let D be a distribution on assignments ϕ : V⋆ → [m]. Suppose that we execute
EmulatePhase for D and let C be a non-zero probability m-configuration—composed of sets Ri , Hi , and
Fi for i ∈ [m]—that can be created in this setting. Let V⋆′ be the set of vertices in V⋆ that are not fixed by C.
We write D[C] to denote the conditional distribution of possible assignments of vertices in V⋆′ to [m], given
that for all i ∈ [m], Ri , Hi , and Fi in C were the sets constructed by LocalPhase for the i-th induced
subgraph.
Near uniformity and independence. Let D be a distribution on assignments ϕ : Ve → [m] for some set
Ve and m. For each vertex v ∈ Ve , let pv : [m] → [0, 1] be the probability mass function of the marginal
distribution of v’s assignment. For any ǫ ≥ 0, we say that D is ǫ-near uniform if for every vertex v and
every i ∈ [m], pv (i) ∈ J(1 ± ǫ)/mK.
Q We say that D is an independent distribution if the probability of every
assignment ϕ in D equals exactly v∈V ′ pv (ϕ(v)).

Concentration inequality. We use the following version of the Chernoff bound that depends on an upper
bound on the expectation of the underlying independent random variables. It can be shown by combining
two applications of the more standard version.

Lemma 4.1 (Chernoff bound). Let X1 , . . . , Xk be independently distributed random variables taking values
def
in [0, 1]. Let X = X1 + · · · + Xk and let U ≥ 0 be an upper bound on the expectation of X, i.e., E[X] ≤ U .
For any δ ∈ [0, 1], Pr(|X − E[X]| > δU ) ≤ 2 exp(−δ2 U/3).
Concise range notation. Multiple times throughout a paper, we want to denote a range around some
value. Instead of writing, say, [x − δ, x + δ], we introduce a more concise notation. In this specific case,
we would simply write Jx ± δK. More formally, let E be a numerical expression that apart from standard
operations also contains a single application of the binary or unary operator ±. We create two standard
numerical expressions from E: E− and E+ that replace ± with − and +, respectively. Now we define
def
JEK = [min{E− , E+ }, max{E− , E+ }].
√
√
√
As another
q√ example,yconsider E = 101 ± 20. We have E− = 101 − 20 = 9 and E+ = 101 + 20 =
101 ± 20 = [min{9, 11}, max{9, 11}] = [9, 11].
11. Hence
We now show the properties of EmulatePhase that we use to obtain our final parallel algorithm.

4.1 Outline of the section
We start by showing that EmulatePhase computes a large matching as follows. Each vertex belonging to Hi or Fi that EmulatePhase removes in the calls to LocalPhase can decrease the maximum
matching size in the graph induced by the remaining vertices by one. We show that the matching that
EmulatePhase constructs in the process captures on average at least a constant fraction of that loss. We
also show that the effect of removing Ri is negligible. More precisely, in Section 4.2 we prove the following
lemma.

16

Lemma 4.2. Let ∆, G⋆ = (V⋆ , E⋆ ), m, and D be parameters for EmulatePhase such that
• D is an independent and ǫ-near uniform distribution on assignments of vertices V⋆ to [m] for ǫ ∈
[0, 1/200],
•

∆
m

2
≥ 4000µ−2
R ln n,

• the maximum degree of a vertex in G⋆ is at most 32 ∆.
For each i ∈ [m], let Hi , Fi , and Mi be the sets constructed by LocalPhase for the i-th induced subgraph.
Then, the following relationship holds for their expected sizes:
X
X
E [|Hi ∪ Fi |] ≤ n−9 + 1200
E [|Mi |] .
i∈[m]

i∈[m]

Note that Lemma 4.2 requires that the vertices are distributed independently and near uniformly in the
m sets. This is trivially the case right after the vertices are partitioned independently at random. However,
in the final algorithm, after we partition the vertices, we run multiple phases on each machine. In the rest
of this section we show that running a single phase preserves independence of vertex distribution and only
slightly disturbs the uniformity (Lemma 4.3 and Lemma 4.4). As we have mentioned before, independence
stems from the fact that we use reference sets to estimate vertex degrees. We discard them at the end and
condition on them, which leads to the independence of the distribution of vertices that are not removed.
Lemma 4.3. Let D be an independent distribution of assignments of vertices in V⋆ to [m]. Let C be a nonzero probability m-configuration that can be constructed by EmulatePhase for D. Let V⋆′ be the set of
vertices of V⋆ that are not fixed by C. Then D[C] is an independent distribution of vertices in V⋆′ on [m].
Independence of the vertex assignment is a very handy feature that allows us to use Chernoff-like concentration inequalities in the analysis of multiple phase emulation. However, although the vertex assignment
of non-removed vertices remains independent across machines from phase to phase, as stated by Lemma 4.3,
their distribution is not necessarily uniform. Fortunately, we can show it is near uniform.
The proof of near uniformity is the most involved proof in this paper. In a nutshell, the proof is structured as
follows. We pick an arbitrary vertex v that has not been removed and show that with high probability it has
the same number of neighbors in all sets Ri . The same property holds for v’s neighbors in all sets Hi . We
use this to show that the probability of a fixed configuration of sets removed in a single phase is roughly the
same for all assignments of v to subgraphs. In other words, if v was distributed nearly uniformly before the
execution of EmulatePhase, it is distributed only slightly less uniformly after the execution.
Lemma 4.4. Let ∆, G⋆ = (V⋆ , E⋆ ), m, and D be parameters for EmulatePhase such that
• D is an independent and ǫ-near uniform distribution on assignments of vertices V⋆ to [m] for ǫ ∈
[0, (200 ln n)−1 ],
•

∆
m

2
≥ 4000µ−2
R ln n.

Let C be an m-configuration constructed by EmulatePhase. With probability at least 1 − n−4 both the
following properties hold:
• The maximum degree in the graph induced by the vertices not fixed in C is bounded by 34 ∆.
 

∆ −1/4
• D[C] is 60α m
+ ǫ -near uniform.
17

4.2 Expected matching size
Now we prove Lemma 4.2, i.e. we show that EmulatePhase computes a large matching. In the proof
we argue that the expected total size of sets Hi and Fi is not significantly impacted by relatively low-degree
vertices classified as heavy or by an unlucky assignment of vertices to subgraphs resulting in local vertex
degrees not corresponding to global degrees. Namely, we show that the expected number of friends a heavy
vertex adds is O(1) and at the same time the probability that the vertex gets matched is Ω(1).
Lemma 4.2. Let ∆, G⋆ = (V⋆ , E⋆ ), m, and D be parameters for EmulatePhase such that
• D is an independent and ǫ-near uniform distribution on assignments of vertices V⋆ to [m] for ǫ ∈
[0, 1/200],
•

∆
m

2
≥ 4000µ−2
R ln n,

• the maximum degree of a vertex in G⋆ is at most 32 ∆.
For each i ∈ [m], let Hi , Fi , and Mi be the sets constructed by LocalPhase for the i-th induced subgraph.
Then, the following relationship holds for their expected sizes:
X
X
E [|Hi ∪ Fi |] ≤ n−9 + 1200
E [|Mi |] .
i∈[m]

i∈[m]

Proof. We borrow more notation from EmulatePhase and the m executions of LocalPhase initiated
∆
is the rescaled threshold passed
by it. For i ∈ [m], Vi is the set inducing the i-th subgraph. Value ∆⋆ = m
to the executions of LocalPhase. Ri is the reference set created by LocalPhase for the i-th induced
subgraph.
For each induced subgraph, LocalPhase computes a maximal matching Mi in Line 5. While such a
matching is always large—its size is at least half the maximum matching size—it is hard to relate its size
directly to the sizes of Hi and Fi . Therefore, we first analyze the size of a matching that would be created
fi and we later use the inequality
by MatchHeavy(G⋆ [Hi ∪ Fi ], Hi , Fi ). We refer to this matching as M
fi ≤ 2 |Mi |.
M

We partition each Hi , i ∈ [m], into two sets: Hi′ and Hi′′ . Hi′ is the subset of vertices in Hi of degree
def
′′
is its complement, i.e., Hi′′ = Hi \ Hi′ . We start by bounding the expected
less than 18 ∆ in G⋆ . Hi,t+1
total size of sets Hi′ . What is the probability that a given vertex v of degree less than 81 ∆ is included in
S
i∈[m] Hi ? Suppose that v ∈ Vk , where k ∈ [m]. The expected number of v’s neighbors in Rk is at
3
most (1 + ǫ) · µR · 18 ∆/m ≤ 16
µR ∆⋆ due to the independence and ǫ-near uniformity of D[C]. Using the
independence, Lemma 4.1, and the lower bound on ∆⋆ , we obtain the following bound:
!
 2


1
3
1
1
· µR ∆⋆ ≤ 2 exp (−27 ln n) = 2n−27 .
Pr µR dbv > µR ∆⋆ ≤ 2 exp − ·
4
3
3
16

If dbv ≤ 14 ∆⋆ , the probability that v is selected to Hk is at most µH (dbv /∆⋆ ) ≤ µH (1/4) ≤ 12 n−12 . Hence
v is selected
to Hk —and therefore to Hk′ —with probability at most 2n−27 + 12 n−12 ≤ n−12 . This implies
P
that i∈[m] E [|Hi′ |] ≤ n · n−12 = n−11 .
We also partition the sets of friends, Fi for i ∈ [m], into two sets each: Fi′ and Fi′′ . This partition is
based on the execution of MatchHeavy for the i-th subgraph. In Line 1, this algorithm selects for every
18

vertex v ∈ Fi a random heavy neighbor v⋆ ∈ Hi . If v⋆ ∈ Hi′ , we assign v to Fi′ . Analogously, if v⋆ ∈ Hi′′ ,
′
′
we assign v to Fi′′ . Obviously, a heavy
By Markov’s
P vertex in′ Hi can be selected only if Hi is non-empty.
inequality and the upper bound on i∈[m] E [|Hi |], the probability that at least one set Hi′ is non-empty is at
′
most n−11 . Even if for all i ∈ [m], all vertices in Fi select a heavy neighbor
h
iin Hi whenever it is available,
P
′
the total expected number of vertices in sets Fi′ is at most i∈[m] E Fi,t+1
≤ n · n−11 = n−10 .
Before we proceed to bounding sizes of the remaining sets, we prove that with high probability, all
vertices have a number of neighbors close to the expectation. Let ϕ : V⋆ → [m] be the assignment of
vertices to subgraphs. We define E as the event that for all v ∈ V⋆ ,
1
1
|N (v) ∩ V⋆ | − N (v) ∩ Vϕ(v) ≤ ∆⋆ .
m
16
Consider first one fixed v ∈ V⋆ . The degree of v in G⋆ is |N (v) ∩ V⋆ | ≤ 23 ∆. Due to the near-uniformity
and independence,


1
3
3∆
|N (v) ∩ V⋆ | − E N (v) ∩ Vϕ(v) ≤ ǫ ·
≤
∆⋆ .
m
2m
400



3
∆⋆ ≤ 2∆⋆ . Using the independence of D,
This in particular implies that E N (v) ∩ Vϕ(v) ≤ 23 + 400
−2 2
∆
Lemma 4.1, and the lower bound on ∆⋆ (i.e., ∆⋆ = m ≥ 4000µR ln n = 4 · 1015 · ln4 n),
!






1
1 1 2
1
Pr E N (v) ∩ Vϕ(v) − N (v) ∩ Vϕ(v) >
∆⋆ ≤ 2 exp − ·
·
· 2∆⋆
20
3
20 2

≤ 2 exp −(1012 + 3) ln n
12 +2)

≤ n−(10

≤ n−12 .

As a result, with this probability, we have
1
|N (v) ∩ V⋆ | − N (v) ∩ Vϕ(v)
m

≤

3
1
1
∆⋆ +
∆⋆ ≤ ∆⋆ .
20
400
16

By the union bound, this bound holds for all vertices in V⋆ simultaneously—and hence E occurs—with
probability at least 1 − n · n−12 = 1 − n−11 .P
P
If E does not occur, we can bound both i∈[m] |Hi′′ | and i∈[m] |Fi′′ | by n. This contributes at most
n−11 ·n = n−10 to the expected size of each of these quantities. Suppose nowthat E occurs. Consider an arbi
′′ for some i. The number of neighbors of v in V lies in the range 1 ∆ − 1 ∆ , 3 ∆ + 1 ∆
⊆
trary
v
∈
H
⋆
⋆
⋆
⋆
i
i
8
16
2
16

1
′′
16 ∆⋆ , 2∆⋆ . Moreover, the expected number of vertices w ∈ Fi that select v in w⋆ in Line 1 of
1
MatchHeavy is bounded by 2∆⋆ · 4∆
= 12 . It follows that E [|Fi′′ |] ≤ 21 E [|Hi′′ |], given E. We now
⋆
fi given E. What is the probability that some vertex w ∈ Fi selects v as
lower bound the expected size of M
fi ?
w⋆ in MatchHeavy and (v, w) is added to M
This occurs if one of v’s neighbors w is added to Fi and selects v as w⋆ , and additionally, v and w are
1
∆⋆ . Since each vertex w in
colored blue and red, respectively. The number of v’s neighbors is at least 16
Vi has at most 2∆⋆ neighbors, the number of heavy neighbors of w is bounded by the same number. This
implies that in the process of selecting Fi , only the first branch in the definition of µF is used and each
vertex w is included with probability exactly equal to the number of its neighbors in Hi divided by 4∆t+1 .
Then each heavy neighbor of w is selected as w⋆ with probability one over the number of heavy neighbors
19

of w. What this implies is that each neighbor w of v is selected for Fi and selects v as w⋆ with probability
1
∆⋆ neighbors w
exactly (4∆⋆ )−1 . Hence the probability that v is not selected as w⋆ by any of its at least 16
can be bounded by


 1 ∆⋆

16
1
1
1
≤ exp −
1−
· ∆⋆ = e−1/64 .
4∆⋆
4∆⋆ 16
Therefore the probability that v is selected by some vertex w ∈ Fi as w⋆ is at least 1 − e−1/64 ≥ 1/100.
Then with probability 1/4, these two vertices have appropriate colors and this or another edge incident to
fi . In summary, the probability that an edge (v, w) for some w as
v with the same properties is added to M
fi is at least 1/400. Since we do not count any edge in the matching twice for two
described is added to M
h
i
1
f
E [|Hi′′ |] given E. Overall, given E, we have
heavy vertices, by the linearity of expectation E Mi ≥ 400
X

i∈[m]

i
X h

 3 X  ′′ 
fi .
E Hi ≤ 600
E M
E Hi′′ + Fi′′ ≤
2
i∈[m]

i∈[m]

In general, without conditioning on E,
X

i∈[m]

i
X h


fi .
E Hi′′ + Fi′′ ≤ 2 · n−10 + 600
E M
i∈[m]

We now combine bounds on all terms to finish the proof of the lemma.
X
X 

E [|Hi ∪ Fi |] ≤
E Hi′ + Fi′ + Hi′′ + Fi′′
i∈[m]

i∈[m]

≤ n−11 + n−10 + 2n−10 + 600

≤n

−9

+ 1200

X

i∈[m]

E [|Mi |] .

X

i∈[m]

h
i
fi
E M

4.3 Independence
Next we prove Lemma 4.3. We start with an auxiliary lemma that gives a simple criterion under which
an independent distribution remains independent after conditioning on a random event. Consider a random
vector with independently distributed coordinates. Suppose that for any value of the vector, a random event
E occurs when all coordinates “cooperate”, where each coordinate cooperates independently with probability that depends only on the value of that coordinate. We then show that the distribution of the vector’s
coordinates given E remains independent.
Lemma 4.5. Let k be a positive integer and A an arbitrary finite set. Let X = (X1 , . . . , Xk ) be a random
vector in Ak with independently distributed coordinates. Let E be a random event of non-zero probability.
If there exist functions pi : A → [0, 1], for i ∈ [k], such that for any x = (x1 , . . . , xk ) ∈ Ak appearing with
non-zero probability,
k
Y
pi (xi ),
Pr[E|X = x] =
i=1

then the conditional distribution of coordinates in X given E is independent as well.
20

Proof. Since the distribution of coordinates in X is independent, there are k probability
Qkmass′ functions
′
k
pi : A → [0, 1], i ∈ [k], such that for every x = (x1 , . . . , xk ) ∈ A , Pr[X = x] = i=1 pi (xi ). The
probability of E can be expressed as
X
X
Pr[E] =
Pr[E ∧ X = x] =
Pr[E|X = x] · Pr[X = x]
x=(x1 ,...,xk )∈Ak

=

X

x=(x1 ,...,xk )∈Ak
Pr[X=x]>0

k
Y

pi (xi )p′i (xi ) =

k X
Y

pi (y)p′i (y).

i=1 y∈A

x=(x1 ,...,xk )∈Ak i=1

P
Note that since the probability of E is positive, each multiplicative term y∈A pi (y)p′i (y), i ∈ [k], in the
above expression is positive. We can express the probability of any vector x = (x1 , . . . , xk ) ∈ Ak given E
as follows:
Pr[E ∧ X = x]
Pr[E|X = x] · Pr[X = x]
Pr[X = x|E] =
=
Pr[E]
Pr[E]
Qk
k
Y pi (xi )p′ (xi )
pi (xi )p′i (xi )
i
P
=
= Qk i=1
P
′ (y) .
′
p
(y)p
y∈A i
i
i=1
y∈A pi (y)pi (y)
i=1
P
def
We define p′′i : A → [0, 1] as p′′i (x) = pi (xi )p′i (xi )/ y∈A pi (y)p′i (y) for each i ∈ [k]. Each p′′i is a valid
Q
probability mass function on A. As a result we have Pr[X = x|E] = ki=1 p′′i (xi ), which proves that the
distribution of coordinates in X given E is still independent with each coordinate distributed according to
its probability mass function p′′i .
We now prove Lemma 4.3 by applying Lemma 4.5 thrice. We refer to functions pi , which describe the
probability of each coordinate cooperating, as cooperation probability functions.
Lemma 4.3. Let D be an independent distribution of assignments of vertices in V⋆ to [m]. Let C be a nonzero probability m-configuration that can be constructed by EmulatePhase for D. Let V⋆′ be the set of
vertices of V⋆ that are not fixed by C. Then D[C] is an independent distribution of vertices in V⋆′ on [m].
Proof. C can be expressed as

C = {Ri⋆ }i∈[m] , {Hi⋆ }i∈[m] , {Fi⋆ }i∈[m]



for some subsets Ri⋆ , Hi⋆ , and Fi⋆ of V⋆ , where i ∈ [m]. We write Φ to denote the random assignment of
vertices to sets selected in Line 1 of EmulatePhase. Φ is a random variable distributed according to D.
Let ER be the event that for all i ∈ [m], the reference set Ri generated for the i-th induced subgraph by
LocalPhase equals exactly Ri⋆ . A vertex v that is assigned to a set Vi is included in Ri with probability
exactly µR , independently of other vertices. Hence once we fix an assignment ϕ : V⋆ → [m] of vertices to
sets Vi , we can express the probability
of ER as a product of probabilities that each vertex cooperates. More
Q
formally, Pr[ER |Φ = ϕ] = v∈V⋆ qv (ϕ(v)) for cooperation probability functions qv : [m] → [0, 1] defined
as follows.
S
• If v ∈ i∈[m] Ri⋆ , there is exactly one i ∈ [m] such that v ∈ Ri⋆ . If v is not assigned to Vi , ER cannot
occur. If it is, v cooperates with ER with probability exactly µR , i.e., the probability of the selection
for Ri . For this kind of v, the cooperation probability function is
(
µR if v ∈ Ri⋆ ,
def
qv (i) =
0
if v 6∈ Ri⋆ .
21

S
• If v 6∈ i∈[m] Ri⋆ , v cooperates with ER if it is not selected for Rϕ(v) , independently of its assignment
ϕ(v), which happens with probability exactly 1 − µR . Therefore, the cooperation probability can be
def
defined as qv (i) = 1 − µR for all i ∈ [m].
We invoke Lemma 4.5 to conclude that the conditional distribution of values of Φ given ER is independent
as well.
We now define an event EH that both ER occurs and for all i ∈ [m], Hi , the set of heavy vertices
constructed for the i-th subgraph equals exactly Hi⋆ . We want to show that the conditional distribution of
values of Φ given EH is independent. Note that if Φ is selected from the conditional distribution given ER
(i.e., all sets Ri are as expected) and we fix the assignment φ : V⋆ → [m] of vertices to sets Vi , then each
vertex v ∈ V⋆ is assigned to Hφ(v) —this the only set Hi to which it can be assigned—independently of
other vertices. As a result, we can express the probability of EH given ER and ϕ being the Q
assignment as a
product of cooperation probabilities for each vertex. More precisely, Pr[EH |Φ = ϕ, ER ] = v∈V⋆ qv′ (ϕ(v))
for cooperation probability functions qv′ : [m] → [0, 1] defined as follows, where ∆⋆ is the threshold used
in the m executions of LocalPhase.
S
• If v ∈ i∈[m] Hi⋆ , then there is exactly one i such that v ∈ Hi⋆ . EH can only occur if v is included in the corresponding Hi . This cannot happen if v is not assigned to the corresponding Vi
by ϕ. If v is assigned to this Vi , it has to be selected for Hi , which happens with probability
µH (|N (v) ∩ Ri⋆ |/(µR ∆⋆ )). The cooperation probability function can be written in this case as
(
µH (|N (v) ∩ Ri⋆ |/(µR ∆⋆ )) if v ∈ Hi⋆ ,
def
′
qv (i) =
0
if v 6∈ Hi⋆ .
S
• If v 6∈ i∈[m] Hi⋆ , v cannot be included in Hi corresponding to the set Vi to which it is assigned for
EH to occur. This happens with probability 1 − µH (|N (v) ∩ Ri⋆ |/(µR ∆⋆ )). Hence, we can define
def
qv′ (i) = 1 − µH (|N (v) ∩ Ri⋆ |/(µR ∆⋆ )) for all i ∈ [m].

We can now invoke Lemma 4.5 to conclude that the distribution of values of Φ given EH is independent.
Finally, we define EF to be the event that both EH occurs and for each i ∈ [m], Fi , the set of friends
selected for the i-th induced subgraph, equals exactly Fi⋆ . We observe that once Φ is fixed to a specific
assignment ϕ : V⋆ → [m] and EH occurs (i.e., all sets Ri and Hi are as in C), then each vertex is independently included in Fϕ(v) with some specific probability that depends only on Hϕ(v) , which is already fixed.
In this setting, we can therefore express the probability of EF , which exactly specifies the composition of
sets Fi , as a product of values provided
by some cooperation probability functions qv′′ : [m] → [0, 1]. More
Q
precisely, Pr[EF |Φ = ϕ, EH ] = v∈V⋆ qv′′ (ϕ(v)) for qv′′ that we define next.
S
• If v ∈ i∈[m] Fi⋆ , then there is exactly one i such that v ∈ Fi⋆ . EF cannot occur if v is not assigned to
Vi and selected for Fi . Hence, the cooperation probability function for v is
(
µF (|N (v) ∩ Hi⋆ |/∆⋆ ) if v ∈ Fi⋆ ,
def
qv′′ (i) =
0
if v 6∈ Fi⋆ .
• If v 6∈

S

⋆
i∈[m] Fi ,

to whichever set Vi vertex v is assigned, it should not be included in Fi in order for
def

EF to occur. Hence, qv′′ (i) = 1 − µF (|N (v) ∩ Hi⋆⋆ ,t |/∆t ).

We invoke Lemma 4.5 to conclude that the distribution of values of Φ given EF is independent as well. This
is a distribution on assignments for the entire set V⋆ . If we restrict it to assignments of V⋆′ ⊆ V⋆ , we obtain
a distribution that first, is independent as well, and second, equals exactly D[C].
22

4.4 Near Uniformity
In this section we prove Lemma 4.4. We begin by showing a useful property of µH (see Table 2 for definition). Recall that GlobalAlg selects H, the set of heavy vertices, by taking all vertices of degree at least
∆/2. In LocalPhase the degree estimate of each vertex depends on the number of neighbors in the reference set in the vertex’s induced subgraph. We want the decision taken for each vertex to be approximately
the same, independently of which subgraph it is assigned to. Therefore, we use µH —which specifies the
probability of the inclusion in the set of heavy vertices—which is relatively insensitive to small argument
changes. The next lemma proves that this is indeed the case. Small additive changes to the parameter x to
µH have small multiplicative impact on both µH (x) and 1 − µH (x).
Lemma 4.6 (Insensitivity of µH ). Let δ ∈ [0, (α/2)−1 ] = [0, (48 ln n)−1 ]. For any pair x and x′ of real
numbers such that |x − x′ | ≤ δ,
µH (x′ ) ∈ JµH (x)(1 ± αδ)K
and

1 − µH (x′ ) ∈ J(1 − µH (x))(1 ± αδ)K .

Proof. We define an auxiliary function f : R → [0, 1]:
(

1
exp α2 r
if r ≤ 0,
def
2

f (r) =
α
1
1 − 2 exp − 2 r if r > 0.

It is easy to verify that for all r ∈ R, µH (r) = f (r − 1/2) and 1 − µH (r) = f (−(r − 1/2)). Therefore, in
order to prove the lemma, it suffices to prove that for any r and r ′ such that |r − r ′ | ≤ δ,
f (r)(1 − αδ) ≤ f (r ′ ) ≤ f (r)(1 + αδ),

(1)

i.e., a small additive change to the argument of f has a limited multiplicative impact on the value of f .
Note that f is differentiable in both (−∞, 0) and (0, ∞). Additionally, it is continuous in the entire
range—the left and right branch of the function meet at 0—and both the left and right derivatives at 0 are
equal. This implies that it is differentiable at 0 as well. Its derivative is
(

α
· exp α2 r
if r ≤ 0,
′
4

f (r) = α
α
if r > 0,
4 · exp − 2 r

which is positive for all r, and therefore, f is strictly increasing. Note that f ′ is increasing in (−∞, 0] and
decreasing in [0, ∞). Hence the global maximum of f ′ equals f ′ (0) = α/4.
In order to prove Inequality 1 for all r and r ′ such that |r − r ′ | ≤ δ, we consider two cases. Suppose
first that r ≥ 0. By the upper bound on the derivative of f ,
f (r) −

α
α
· |r − r ′ | ≤ f (r ′ ) ≤ f (r) + · |r − r ′ |.
4
4

Since r ≥ 0, f (r) ≥ 1/2. This leads to
f (r) − f (r) ·
By the bound on |r − r ′ |,

α
α
· |r − r ′ | ≤ f (r ′ ) ≤ f (r) + f (r) · · |r − r ′ |.
2
2

f (r)(1 − αδ) ≤ f (r ′ ) ≤ f (r)(1 + αδ),
23

which finishes the proof in the first case.
Suppose now that r < 0. Since f is increasing, it suffices to bound the value of f from below at r − δ
and from above and at r + δ. For r − δ, we obtain
α

 α 
1
f (r − δ) = exp
(r − δ) = f (r) exp − δ
2  2
2
α 
≥ f (r) 1 − δ ≥ f (r)(1 − αδ).
2
For r + δ, let us first define a function g : R → R as
def

g(y) =

α 
1
exp
y .
2
2

For y ≤ 0, f (y) = g(y). For y > 0, g′ (y) ≥ f ′ (y) and hence, for any y ∈ R, g(y) ≥ f (y). As a result, we
obtain
α

α 
1
(r + δ) = f (r) · exp
δ .
f (r + δ) ≤ g(r + δ) = exp
2
2
2
By the bound on δ in the lemma statement, α2 δ ≤ 1. It follows from the convexity of the exponential function
that for any y ∈ [0, 1], exp(y) ≤ y · exp(1) + (1 − y) · exp(0) ≤ 3y + (1 − y) = 1 + 2y. Continuing the
reasoning,

α 
f (r + δ) ≤ f (r) · 1 + 2 · δ = f (r)(1 + αδ),
2
which finishes the proof of Inequality (1).
The main result of this section is Lemma 4.4 that states that if a distribution D of vertex assignments
is near uniform, then EmulatePhase constructs a configuration C such that D[C] is near uniform as well,
and also, the maximum degree in the graph induced by the vertices not removed by EmulatePhase is
bounded.
Lemma 4.4. Let ∆, G⋆ = (V⋆ , E⋆ ), m, and D be parameters for EmulatePhase such that
• D is an independent and ǫ-near uniform distribution on assignments of vertices V⋆ to [m] for ǫ ∈
[0, (200 ln n)−1 ],
•

∆
m

2
≥ 4000µ−2
R ln n.

Let C be an m-configuration constructed by EmulatePhase. With probability at least 1 − n−4 both the
following properties hold:
• The maximum degree in the graph induced by the vertices not fixed in C is bounded by 34 ∆.

 
∆ −1/4
+ ǫ -near uniform.
• D[C] is 60α m
Proof overview (of Lemma 4.4). This is the most intricate proof of the entire paper. We therefore provide
a short overview. First, we list again the variables in EmulatePhase and LocalPhase to which we
refer in the proof and define additional convenient symbols. Then we introduce five simple random events
(Events 1–5) that capture properties needed to prove Lemma 4.4. In Claim 4.7, we show that the probability of all these events occurring simultaneously is high. The proof of the claim follows mostly from a
repetitive application of the Chernoff bound. In the next claim, Claim 4.8, we show that the occurrence of
24

all the events has a few helpful consequences. First, high degree vertices get removed in the execution of
EmulatePhase (which is one of our final desired properties). Second, each vertex v that is not fixed in
C has a very similar number of neighbors in all sets Ri and it has a very similar number of neighbors in all
sets Hi . In the final proof of Lemma 4.4, we use the fact that this implies that to whichever set Vi vertex
v was assigned in EmulatePhase, the probability of its removal in EmulatePhase was more or less
the same. This leads to the conclusion that if v was distributed nearly uniformly in D, it is distributed only
slightly less uniformly in D[C].
Notation. To simplify the presentation, for the rest of Section 4.4, we assume that ∆, G⋆ = (V⋆ , E⋆ ),
m, and D are the parameters to EmulatePhase as in the statement of Lemma 4.4. Additionally, for
each i ∈ [m], Ri , Hi , and Fi are the sets constructed by LocalPhase for the i-th subgraph in the execution of EmulatePhase. We
 also write C to denote the corresponding m-configuration, i.e., C =
{Ri }i∈[m] , {Hi }i∈[m] , {Fi }i∈[m] . Furthermore, for each v ∈ V⋆ , dbv is the estimate of v’s degree in the
subgraph to which it was assigned. This estimate is computed in Line 2 of LocalPhase. We also use ∆⋆
∆
.
to denote the rescaled threshold passed in all calls to LocalPhase, i.e., ∆⋆ = m
We also introduce additional notation, not present in EmulatePhase or LocalPhase. For each
def
v ∈ V⋆ , dv = |N (v) ∩ V⋆ |, i.e., dv is the degree of v in G⋆ . For each vertex v ∈ V⋆ , we also introduce a
def
notion of its weight: wv = µH (dv /∆), which can be seen as a very rough approximation of v’s probability
of being selected for the set of heavy vertices. For any v ∈ V⋆ and U ⊆ V⋆ , we also introduce notation for
the total weight of v’s neighbors in U :
X
def
Wv (U ) =
wu .
u∈N (v)∩U

Finally, for all i ∈ [m] and v ∈ V⋆ , we also introduce a slightly less intuitive notion of the expected number
of heavy neighbors of v in the i-th subgraph after the degree estimates are fixed in Line 2 of LocalPhase
and before vertices are assigned to the heavy set in Line 3:


X
def
hv,i =
µH dbu /∆⋆ .
u∈N (v)∩Vi

Obviously, each hv,i is a random variable.

Convenient random events. We now list five random events that we hope all to occur simultaneously with
high probability. The first event intuitively is the event that high-degree vertices are likely to be included in
the set of heavy vertices in Line 3 of LocalPhase.
Event 1
For each vertex v ∈ V⋆ such that dv ≥ 43 ∆,


1
µH dbv /∆⋆ ≥ 1 − n−6 .
2

Another way to define this event would be to state that dbv for such vertices v is high, but this form is more
suitable for our applications later. The next event is the event that all such vertices are in fact classified as

25

heavy.
Event 2
Each vertex v ∈ V⋆ such that dv ≥ 43 ∆ belongs to

S

i∈[m] Hi .

The next event is the event that low-degree vertices have a number of neighbors in each set Ri close to the
mean. This implies that if we were able to move a low-degree vertex v to Vi , for any i ∈ [m], its estimated
degree dbv would not change significantly.
Event 3

For each vertex v ∈ V⋆ such that dv < 34 ∆ and each i ∈ [m],
3
dv
1
3/4
≤ ∆⋆ + ǫ∆⋆ .
|N (v) ∩ Ri | −
µR
m
4
As a reminder, we use Wv (U ) to denote the expected number of vertices in N (v) ∩ U that are selected
as heavy, where every vertex u is selected with respect to its global degree du . The next event shows that
Wv (Vi ) does not deviate much from its mean.
Event 4
For each vertex v ∈ V⋆ such that dv < 34 ∆ and each i ∈ [m],
3
3/4
|Wv (Vi ) − Wv (V⋆ )/m| ≤ ∆⋆ + ǫ∆⋆ .
4
Recall that hv,i intuitively expresses the expected number of v’s neighbors in the i-th induced subgraph at
some specific stage in the execution of LocalPhase for the i-th induced subgraph. The final event is the
event that for all bounded hv,i , the actual number of v’s neighbors in Hi does not deviate significantly from
hv,i .
Event 5
For each vertex v ∈ V⋆ and each i ∈ [m], if hv,i ≤ 2∆⋆ , then
3/4

||N (v) ∩ Hi | − hv,i | ≤ ∆⋆ .
High probability of the random events. We now show that the probability of all the events occurring is
high. The proof follows mostly via elementary applications of the Chernoff bound.
Claim 4.7. If ǫ ∈ [0, 1/100] and
ity at least 1 − n−4 .

∆
m

2
≥ 4000µ−2
R ln n, then Events 1–5 occur simultaneously with probabil-

Proof. We consider all events in order and later show by the union bound that all of them hold simulta∆
≥
neously with high probability. In the proof of the lemma, we extensively use the fact that ∆⋆ = m
−2 2
4
15
4000µR ln n = 4 · 10 · ln n.
First, we consider Event 1 and Event 2, which we handle together. Consider a vertex v such that dv ≥
3
∆.
Let i⋆ be the index of the set to which it is assigned. Since D is ǫ-near uniform, the expectation of
4
∆
|N (v) ∩ Ri⋆ |, the number of v’s neighbors in Ri⋆ , is at least (1 − ǫ) 34 µR m
≥ 297
400 µR ∆⋆ . Since vertices are
both assigned to machines independently and included in the reference set independently as well, we can

26

apply Lemma 4.1 to bound the deviation with high probability. The probability that the number of neighbors
5
9
· 297
is smaller than 10
400 µR ∆⋆ ≥ 8 µR ∆⋆ is at most
!

 2

1
297
1
1
1
·
µR ∆⋆ ≤ 2 exp −
µR ∆⋆ ≤ 2n−9 ≤ n−6 .
2 exp − ·
3
10
400
405
2
Hence with probability at least 1 − 21 n−6 , dbv ≥

5
8 ∆⋆



and µH dbv /∆⋆ ≥ 1 − 12 n−6 . If this is the case,

v is not included in the set of heavy vertices
in Line 3 of LocalPhase with probability at most 21 n−6 .

Therefore, v has the desired value of µH dbv /∆⋆ and belongs to Hi with probability at least 1 − n−6 . By
⋆

the union bound, this occurs for all high degree vertices with probability at least 1 − n−5 , in which case both
Event 1 and Event 2 occur.
We now show that Event 3 occurs with high probability. Let v be an arbitrary vertex such that dv < 43 ∆
def
and let i ∈ [m]. Let Xv,i = |N (v) ∩ Ri |. Xv,i is a random variable. Since D is ǫ-near uniform, E [Xv,i ] ∈
J(1 ± ǫ)µR dv /mK. In particular, due to the bounds on dv and ǫ, E[Xv,i ] ≤ µR ∆⋆ . Due to the independence,
we can use Lemma 4.1 to bound the deviation of Xv,i from its expectation. We have


!2


1
1
3/4
≤ 2 exp − ·
Pr |Xv,i − E[Xv,i ]| > µR ∆⋆
· µR ∆⋆ 
1/4
3
∆⋆


1
1/2
≤ 2n−21 .
= 2 exp − µR ∆⋆
3
Hence with probability 1 − 2n−21 , we have
Xv,i − µR

dv
dv
dv
3/4
≤ |Xv,i − E[Xv,i ]| + E[Xv,i ] − µR
≤ µR ∆⋆ + ǫµR
m
m
m
3
3/4
≤ µR ∆⋆ + ǫµR ∆⋆ .
4

By dividing both sides by µR , we obtain the desired bound
Xv,i dv
3
1
dv
3/4
=
≤ ∆⋆ + ǫ∆⋆ .
−
|N (v) ∩ Ri | −
µR
m
µR
m
4
By the union bound, this holds for all v and i of interest—and therefore, Event 3 occurs—with probability
at least 1 − |V⋆ | · m · 2n−21 ≥ 1 − n−5 .
We now move on to Event 4. Consider a vertex v such that dv < 34 ∆ and i ∈ [m]. Note that since
the weight of every vertex is at most 1, Wv (V⋆ )/m ≤ dv /m < 34 ∆⋆ . Since D[C] is ǫ-near uniform,
3
101
Wv (V⋆ )/m ≤ 101
E [Wv (Vi )] ∈ J(1 ± ǫ)Wv (V⋆ )/mK. In particular, E [Wv (Vi )] ≤ 100
100 · 4 ∆⋆ ≤ ∆⋆ . Since
vertices are assigned to machines independently, we can apply Lemma 4.1 to bound the deviation of Wv (Vi )
from the expectation:


!2


1
1
3/4
≤ 2 exp − ·
Pr |Wv (Vi ) − E [Wv (Vi )]| > ∆⋆
· ∆⋆ 
1/4
3
∆⋆


1 1/2
≤ 2n−21 .
= 2 exp − ∆⋆
3
27

As a result, with probability at least 1 − 2n−21 ,
|Wv (Vi ) − Wv (V⋆ )/m| ≤ |Wv (Vi ) − E [Wv (Vi )]| + |E [Wv (Vi )] − Wv (V⋆ )/m|
3
3/4
3/4
3/4
≤ ∆⋆ + ǫWv (V⋆ )/m ≤ ∆⋆ + ǫdv /m ≤ ∆⋆ + ǫ∆⋆ .
4
By the union bound, this holds for all v and i of interest—and therefore, Event 4 occurs—with probability
at least 1 − |V⋆ | · m · 2n−21 ≥ 1 − n−5 .
To show that Event 5 occurs with high probability, recall first that hv,i is the expected number of v’s
neighbors to be added in Line 3 to Hi in the execution of LocalPhase for the i-th subgraph. Note that
the decision of adding a vertex to Hi is made independently for each neighbor of v. Fix a v ∈ V⋆ and
i ∈ [m] such that hv,i ≤ 2∆⋆ . We apply Lemma 4.1 to bound the probability of a large deviation from the
expectation:


!2


1
1
3/4
≤ 2 exp − ·
Pr ||N (v) ∩ Hi | − hv,i | > ∆⋆
· 2∆⋆ 
1/4
3
2∆⋆


1 1/2
≤ 2n−10 .
= 2 exp − ∆⋆
6
By the union bound the probability that this bound does not hold for some v and i such that hv,i ≤ 2∆⋆ is
by the union bound at most |V⋆ | · m · 2n−10 ≤ n−5 . Hence, Event 5 occurs with probability at least 1 − n−5 .
In summary, Events 1–5 occur simultaneously with probability at least 1 − 4 · n−5 ≥ 1 − n−4 by another
application of the union bound.
Consequences of the random events. We now show that if all the random events occur, then a few helpful
properties hold for every vertex v that is not fixed by the constructed configuration C. Namely, v’s degree is
at most 43 ∆, the number of v’s neighbors is similar in all sets Ri is approximately the same, and the number
of v’s neighbors is similar in all sets Hi .
Claim 4.8. If Events 1–5 occur for ǫ ∈ [0, (200 ln n)−1 ] and
properties hold for every vertex v ∈ V⋆ that is not fixed by C:

∆
m

2
≥ 4000µ−2
R ln n, then the following

1. dv < 43 ∆.
2. There exists χv such that for all i ∈ [m],

s

{
3
3/4
|N (v) ∩ Ri | /µR ∈ χv ± ∆⋆ + ǫ∆⋆
.
4



3. There exists ψv ∈ 0, 34 ∆⋆ such that for all i ∈ [m],
z
r

3/4
|N (v) ∩ Hi | ∈ ψv ± α ∆⋆ + ǫ∆⋆ .
2
4
∆
15
≥ 4000µ−2
Proof. We use in the proof of the claim the fact that ∆⋆ = m
R ln n = 4 · 10 · ln n. To prove
the lemma, we fix a vertex v that is not fixed by C. The first property is directly implied by Event 2. Suppose
that dv ≥ 43 ∆. Then v is included in the Hi corresponding to the subgraph to which it has been assigned
and v is fixed by C. We obtain a contradiction that implies that dv < 34 ∆.

28

For the second property, we now know that dv < 43 ∆. The property follows then directly from Event 3
def
with χv = dv /m.
def
The last property requires a more complicated reasoning. We set ψv = Wv (V⋆ )/m < 34 ∆⋆ . Consider
any i ∈ [m]. By Event 4,
{
s

3
3/4
.
(2)
Wv (Vi ) ∈ ψv ± ∆⋆ + ǫ∆⋆
4
Consider now an arbitrary u ∈ V⋆ . We bound the difference between wu =µH (du /∆),
which can be seen

b
as the ideal probability of the inclusion in the set of heavy vertices, and µH du /∆⋆ , the actual probability


def
−1/4
+ 43 ǫ . We
of this event in Line 3 of the appropriate execution of LocalPhase. Let δ⋆ = α ∆⋆
consider two cases.
• If du < 34 ∆, by Event 3, the monotonicity of µH , and Lemma 4.6,


{

 s
du
3
−1/4
µH dbu /∆⋆ ∈ µH
+ ǫ
± ∆⋆
∆
4
⊆ Jwu · (1 ± δ⋆ )K .
−1/4

+ 34 ǫ ≤ (200 ln n)−1 + (200 ln n)−1 ≤
Note that Lemma 4.6 is applied properly because ∆⋆
(48 ln n)−1 .




• If du ≥ 43 ∆, by Event 1, µH dbu /∆⋆ ∈ 1 − 21 n−6 , 1 . Concurrently, wu ∈ [µH (3/4), 1] =


1 − 21 n−12 , 1 . Because ∆⋆ is relatively small, i.e., ∆⋆ ≤ n,
z

 r 
−1/4
⊆ Jwu · (1 ± δ⋆ )K ,
µH dbu /∆⋆ ∈ wu 1 ± ∆⋆
which is the same bound as in the previous case.

It follows from the bound that we just obtained and the definitions of Wv and hv,i that
u
}


X
X
wu ~
hv,i =
µH dbu /∆⋆ ∈ v(1 ± δ⋆ ) ·
u∈N (v)∩Vi

u∈N (v)∩Vi

= JWv (Vi ) · (1 ± δ⋆ )K .

(3)

We now combine bounds (2) and (3):






3
3
3/4
3/4
hv,i ∈ ψv (1 − δ⋆ ) − ∆⋆ + ǫ∆⋆ (1 + δ⋆ ) , ψv (1 + δ⋆ ) + ∆⋆ + ǫ∆⋆ (1 + δ⋆ )
4
4

{
s


3
3/4
.
⊆ ψv ± ψv δ⋆ + ∆⋆ + ǫ∆⋆ (1 + δ⋆ )
4

Due to the lower bound on ∆⋆ , we obtain δ⋆ ≤ α (200 ln n)−1 + (200 ln n)−1 ≤ 1. This enables us to

29

simplify and further transform the bound on hv,i :
s


{
3
3/4
hv,i ∈ ψv ± ψv δ⋆ + 2 ∆⋆ + ǫ∆⋆
4
{
s

9
3
3
3/4
3/4
α∆⋆ + αǫ∆⋆ + 2∆⋆ + ǫ∆⋆
⊆ ψv ±
4
16
2
s

{
4 3/4
⊆ ψv ± α
∆⋆ + ǫ∆⋆
.
5
By applying the bound on ∆⋆ again, we obtain a bound on the magnitude of the second term in the above
bound:






4 3/4
1
1
4 −1/4
α
∆⋆ + ǫ∆⋆ = α
∆⋆
+ ǫ ∆⋆ ≤ 96 ln n
+
∆⋆ ≤ ∆⋆ .
5
5
200 ln n 200 ln n
This implies that hv,i ≤ ψv +∆⋆ ≤ 2∆⋆ . The condition in Event 5 holds, and therefore, ||N (v) ∩ Hi | − hv,i | ≤
3/4
∆⋆ . We combine this with the bound on hv,i to obtain
{ r
s

z

4 3/4
3/4
3/4
⊆ ψv ± α ∆⋆ + ǫ∆⋆ .
|N (v) ∩ Hi | ∈ ψv ± α ∆⋆ + αǫ∆⋆ + ∆⋆
5
Wrapping up the proof of near uniformity. We now finally prove Lemma 4.4. Recall that it states that
an ǫ-near uniform D is very likely to result in a near uniform D[C] with a slightly worse parameter and
that all vertices not fixed by C have bounded degree. The proof combines the last two claims: Claim 4.7
and Claim 4.8. We learn that C, the m-configuration constructed in the process is very likely to have the
properties listed in Claim 4.8. One of those properties is exactly the property that all vertices not fixed by
C have bounded degree. Hence we have to prove only the near uniformity property. We accomplish this by
observing that the probability of C equal to a specific m-configuration C⋆ with good properties—those in
Claim 4.8—does not depend significantly on to which induced subgraph a given vertex v not fixed in C⋆ is
assigned. This can be used to show that the conditional distribution of v given that C = C⋆ is near uniform
as desired.
Proof of Lemma 4.4. By combining Claim 4.7 and Claim 4.8, we learn that with probability at least 1− n−4 ,
all properties listed in the statement of Claim 4.8 hold for C, the configuration constructed by EmulatePhase.
Since one of the propertiesis exactly the
 same as in the statement of Lemma 4.4, it suffices to prove the
−1/4
+ ǫ -near uniform for C with this set of properties.
other one: that D[C] is 60α ∆⋆


ei }i∈[m] , {H
e i }i∈[m] , {Fei }i∈[m] to be an m-configuration that has non-zero probability
Fix Ce = {R
when EmulatePhase is run for D and has the properties specified
by Claim 4.8. Consider an arbitrary
h i
e
vertex v ∈ V⋆ . In order to prove the near uniformity of D C , we show that v is assigned by it almost
e i.e., C = C.
e For each i ∈ [m], let
uniformly to [m]. Let E be the event that EmulatePhase constructs C,
E→i be the event that v is assigned to the i-th induced subgraph. Let p : [m] → [0, 1] be the probability
mass function describing the probability of the assignment of v to each of the
in D. Obviously,
y
q 1 m subgraphs
p(i) = Pr[E→i ] for all i ∈ [m]. Due to the ǫ-near uniformity of D, p(i) = m (1 ± ǫ) .
def
For each i ∈ [m], let qi = Pr[E|E→i ]. In order to express all qi ’s in a suitable form, we conduct a
thought experiment. Suppose v were not present in the graph, but the distribution of all the other vertices in
30

e in this modified scenario. How
the modified D remained the same. Let q⋆ be the probability of E, i.e., C = C,
does the probability of E change if we add v back and condition on its assignment to a machine i? Note first
that conditioning on E→i does not impact the distribution of the other vertices, because vertices are assigned
to machines independently in D. In order for E still to occur in this scenario, v cannot be assigned to any
ei , H
e i , or Fei , for which it is considered. Additionally, as long as this the case, v does not impact the
of R
behavior of other vertices, which only depends on the content of these sets and independent randomized
decisions to include vertices. As a result we can express qi as a product of q⋆ and three probabilities: of v
ei , H
e i , or Fei .
not being included in sets R
 




ei
ei /µR
N (v) ∩ H
N (v) ∩ R
 · 1 − µF 
 .
(4)
qi = q⋆ · (1 − µR ) · 1 − µH 
∆⋆
∆⋆
Using the properties listed in Claim 4.8, we have

s

{
3
3/4
e
N (v) ∩ Ri /µR ∈ χv ± ∆⋆ + ǫ∆⋆
,
4

and

z
r

e i ∈ ψv ± α ∆3/4
,
N (v) ∩ H
⋆ + ǫ∆⋆

where χv and ψv are constants independent of machine i to which v has been assigned and ψ ≤ 43 ∆⋆ . In the
next step, we use these bounds to derive bounds on the multiplicative terms in Equation (4) that may depend
2
4
∆
15
−1
on i. We also repeatedly use the bounds ∆⋆ = m
≥ 4000µ−2
R ln n = 4 · 10 · ln n and ǫ ≤ (200 ln n)
from the lemma statement. First, due to Lemma 4.6,


{

s

ei /µR
N (v) ∩ R
3
 ∈ 1 − µH χv ± ∆−1/4
1 − µH 
ǫ
+
⋆
∆⋆
∆⋆
4
{

s
  
3
χv
−1/4
.
· 1 ± α ∆⋆
+ ǫ
⊆
1 − µH
∆⋆
4
−1/4

(Note that the application of Lemma 4.6 was correct, because ∆⋆
(96 ln n)−1 .) Second,


1 − µF 


ei
N (v) ∩ H
∆⋆





s

 ∈ 1 − µF



+ 34 ǫ ≤ (200 ln n)−1 + (200 ln n)−1 <


{
ψv
−1/4
± α ∆⋆
+ǫ
.
∆⋆


+ ǫ ≤ (96 ln n) · (200 ln n)−1 + (200 ln n)−1 < 1, the argument to
Since ψv /∆⋆ ≤ and α
µF in the above bound is always less than 4, and therefore, only one branch of µF ’s definitions gets applied.
Hence, we can eliminate µF :


s
ei
{

N (v) ∩ H
ψ
α
−1/4
v
∈ 1−
+ǫ .
∆⋆
±
1 − µF 
∆⋆
4∆⋆
4
3
4

−1/4
∆⋆

31

Since 1 −

ψv
4∆⋆

≥ 34 , we can further transform the bound to


1 − µF 

ei
N (v) ∩ H
∆⋆



def
def
−1/4
+ 34 ǫ and δ2 =
Let δ1 = α ∆⋆

α
3



∈

s

{
α  −1/4
ψv 
+ǫ
∆⋆
1±
1−
.
4∆⋆
3



−1/4
+ ǫ . As a result, every qi can be expressed as qi = ηv λi λ′i ,
∆⋆

where ηv is a constant independent of i, λi ∈ J1 ± δ1 K, and λ′i ∈ J1 ± δ2 K. For every i, we can also write
Pr[E ∧ E→i ] = Pr[E|E→i ] · Pr[E→i ] = ηv λi λ′i · p(i) =

ηv
λi λ′i λ′′i ,
m

where λ′′i ∈ J1 ± ǫK. We now express the conditional probability of v being assigned to the i-th subgraph in
D given E:
Pr[E ∧ E→i ]
λi λ′ λ′′
Pr[E→i |E] = Pm
= Pm i i ′ ′′ .
j=1 Pr[E ∧ E→j ]
j=1 λj λj λj
Note that for any i, this implies that

1 (1 + δ1 )(1 + δ2 )(1 + ǫ)
1 (1 − δ1 )(1 − δ2 )(1 − ǫ)
·
≤ Pr[E→i |E] ≤
·
.
m (1 + δ1 )(1 + δ2 )(1 + ǫ)
m (1 − δ1 )(1 − δ2 )(1 − ǫ)
Observe that
and

(5)


δ1 ≤ (96 ln n) · (7000 ln n)−1 + (250 ln n)−1 < 1/2,


1
· (96 ln n) · (7000 ln n)−1 + (200 ln n)−1 < 1/2.
3
Hence all of δ1 , δ2 , and ǫ are at most 1/2. We can therefore transform (5) to
δ2 ≤

1
1
· (1 − δ1 )2 (1 − δ2 )2 (1 − ǫ)2 ≤ Pr[E→i |E] ≤
· (1 + δ1 )(1 + δ2 )(1 + ǫ)(1 + 2δ1 )(1 + 2δ2 )(1 + 2ǫ),
m
m
and then

1
1
· (1 − 2δ1 − 2δ2 − 2ǫ) ≤ Pr[E→i |E] ≤
· (1 + 45δ1 + 45δ2 + 45ǫ).
m
m
Hence
s
{ s
{

1
1 
−1/4
+ǫ
Pr[E→i |E] ∈
· (1 ± 45(δ1 + δ2 + ǫ)) ⊆
· 1 ± 60α ∆⋆
,
m
m
h i


−1/4
which finishes the proof that D Ce is 60α ∆⋆
+ ǫ -near uniform.

5 Parallel Algorithm

In this section, we introduce our main parallel algorithm. It builds on the ideas introduced in EmulatePhase.
EmulatePhase randomly partitions the graph into m induced subgraphs and runs on each of them
LocalPhase, which resembles a phase of GlobalAlg. As we have seen, the algorithm performs well
even if vertices are assigned to subgraphs not exactly uniformly so long as the assignment is fully independent. Additionally, with high probability, if we condition on the configuration of sets Ri , Hi , and Fi
32

that were removed, the distribution of assignments of the remaining vertices is still nearly uniform and also
independent.
These properties allow for the main idea behind the final parallel algorithm. We partition vertices randomly into m induced subgraphs and then run LocalPhase multiple times on each of them with no repartitioning in the meantime. In each iteration, for a given subgraph, we halve the local threshold ∆⋆ . This
corresponds to multiple phases of the original global algorithm. As long as we can show that this approach
leads to finding a large matching, the obvious gain is that multiple phases of the original algorithm translate
to O(1) parallel rounds. This approach enables our main result: the parallel round complexity reduction
from O(log n) to O((log log n)2 ).
Algorithm 5: ParallelAlg(G, S)
The final parallel matching algorithm
Input:
• graph G = (V, E) on n vertices
• parameter S ∈ Z+ such that S ≤ n and S = nΩ(1) (each machine uses O(S) space)
Output: matching in G
1
2

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

∆ ← n, V ′ ← V , M ← ∅
while ∆ ≥ Sn (200 ln n)32 do
/* High-probability invariant: maximum degree in G[V ′ ] bounded by 32 ∆ */
jq k
n∆
m←
/* number of machines used */
S

1
/* number of phases to emulate */
τ ← 16 log120α (∆/m)
′
Partition V into m sets V1 , . . . , Vm by assigning each vertex independently uniformly at random.
foreach i ∈ [m] do in parallel
If the number of edges in G[Vi ] is greater than 8S, Vi ← ∅.

for j ∈ [τ ] do (Vi , Mi,j ) ← LocalPhase i, G[Vi ], ∆/ 2j−1 m
Sm
Vi S
V ′ ← i=1 S
m
τ
M ← M ∪ i=1 j=1 Mi,j
∆ ← ∆/2τ
Compute degrees of vertices V ′ in G[V ′ ] and remove from V ′ vertices of degree at least 2∆.
Directly simulate M ′ ← GlobalAlg(G[V ′ ], 2∆), using O(1) rounds per phase.
return M ∪ M ′

We present ParallelAlg, our parallel algorithm, as Algorithm 5. We write S to denote a parameter
specifying the amount of space per machine. After the initialization of variables, the algorithm enters
the main loop in Lines 2–11. The loop is executed as long as ∆, an approximate upper bound on the
maximum degree in the remaining graph, is large enough. The loop implements the idea of running multiple
iterations of LocalPhase on each induced subgraph in a random partition. At the beginning of the loop,
the algorithm decides on m, the number of machines, and τ , the number of phases to be emulated. Then it
creates a random partition of the current set of vertices that results in m induced subgraphs. Next for each
subgraph, the algorithm first runs a security check that the set of edges fits onto a single machine (see Line 7).
If it does not, which is highly unlikely, the entire subgraph is removed from the graph. Otherwise, the entire
subgraph is sent to a single machine that runs τ consecutive iterations of LocalPhase. Then the vertices
not removed in the executions of LocalPhase are collected for further computation and new matching
edges are added to the matching being constructed. During the execution of the loop, the maximum degree in
the graph induced by V ′ , the set of vertices to be considered is bounded by 32 ∆ with high probability. Once
33

the loop finishes, we remove from the graph vertices of degree higher than 2∆—there should be none—and
we directly simulate GlobalAlg on the remaining graph, using O(1) rounds per phase.

5.1 Some Properties of Thresholds
∆
inside the main loop
Before we analyze the behavior of the algorithm, we observe that the value of m
is at least polylogarithmic and that the same property holds for the rescaled threshold that is passed to
LocalPhase.

Lemma 5.1. Consider a single iteration of the main loop of ParallelAlg (Lines 2–11). Let ∆ and m be
set as in this iteration. The following two properties hold:
• ∆/m ≥ (200 log n)16 .


• The threshold ∆/ 2j−1 m passed to LocalPhase in Line 8 is always at least (∆/m)15/16 ≥
2
4000µ−2
R ln n.

Proof. Let τ be also as in this iteration of the loop. The smallest threshold passed to LocalPhase is
def
∆/(2τ −1 m). Let λ = S∆/n, where S is the parameter to ParallelAlg.
Due
p
√ to the condition in
n
32
Line 2, λ ≥ (200 ln n) . Note that ∆ = λn/S. Hence m ≤
n∆/S = S λ. This implies that
√
∆/m ≥ λ ≥ (200 ln n)16 , which proves the first claim. Due to the definition of τ ,
2τ −1 ≤ (120α)τ −1 ≤ (∆/m)1/16 .
This implies that
2
∆/(2τ −1 m) ≥ (∆/m)15/16 ≥ (200 ln n)15 > 4 · 1015 · ln4 n = 4000µ−2
R ln n.

We also observe that the probability of any set of vertices deleted by the security check in Line 7 of
ParallelAlg is low as long as the maximum degree in the graph induced by the remaining vertices is
bounded.
Lemma 5.2. Consider a single iteration of the main loop of ParallelAlg and let ∆ and V ′ be as in that
iteration. If the maximum degree in G[V ′ ] is bounded by 32 ∆, then the probability of any subset of vertices
deleted in Line 7 is n−8 .
Proof. Let m be as in the same iteration of the main loop of ParallelAlg. Consider a single vertex
v ∈ V ′ . The expected number of v’s neighbors assigned to the same subgraph is at most 32 ∆/m. Recall
∆
≥ 200 ln n. Since the assignment of vertices to machines is fully independent, by
that due to Lemma 5.1, m
Lemma 4.1 (i.e., the Chernoff bound), the probability that v has more than 2∆/m neighbors is bounded by
!

 2

1
1
1
3 ∆
2 exp − ·
≤ 2 exp − · 200 ln n ≤ n−10 .
· ·
3
3
2 m
18
Therefore, by the union bound, with probability 1 − n−9 , no vertex has more than 2∆ neighbors in the same
induced subgraph. As |V ′ | ≤ n, the expected number of vertices in each set Vi constructed in the iteration
of the main loop is at most n/m ≥ ∆/m ≥ 200 ln n. What is the probability that |Vi | > 2n/m? By the
independence of vertex assignments and Lemma 4.1, the probability of such event is at most




1
1 n
≤ 2 exp − · 200 ln n ≤ n−10 .
2 exp − ·
3 m
3
34

Again by the union bound, the event |Vi | ≤ 2n/m, for all i simultaneously, occurs with probability at least
1 − n−9 . Combining both bounds, with probability at least 1 − 2n−9 ≥ 1 − n−8 , all induced subgraphs have
at most 2n/m vertices and the degree of every vertex is bounded by 2∆/m. Hence the number of edges in
2∆
2n∆
one induced subgraph is at most 21 · 2n
m · m = m2 . By the definition of m and the setting of parameters
q
in the algorithm, m ≥ 12 n∆
S , where S is the parameter to ParallelAlg. This implies that the number
 q 2
of edges is at most 2n∆/ 21 n∆
= 8S in every induced subgraph with probability 1 − n−8 , in which
S
case no set Vi is deleted in Line 7 of ParallelAlg.

5.2 Matching Size Analysis
The parallel algorithm runs multiple iterations of LocalPhase on each induced subgraph, without repartitioning. A single iteration on all subgraphs corresponds to running EmulatePhase once. We now show
that in most cases, the global algorithm simulates EmulatePhase on a well behaved distribution with independently assigned vertices and all vertices distributed nearly uniformly conditioned on the configurations
of the previously removed sets Ri , Hi , and Fi . We also show that the maximum degree in the remaining
graph is likely to decrease gracefully during the process.
Lemma 5.3. With probability at least 1 − n−3 :
• all parallel iterations of LocalPhase in ParallelAlg on each induced subgraph correspond
to running EmulatePhase on independent and (200 ln n)−1 -near uniform distributions of assignments,
• the maximum degree of the graph induced by the remaining vertices after the k-th simulation of
EmulatePhase is 23 ∆/2k .
Proof. We first consider a single iteration of the main loop in ParallelAlg. Let ∆, τ , and m be set as

def
in this iteration of the loop. For j ∈ [τ ], let ∆j = ∆/ 2j−1 m be the threshold passed to LocalPhase
for the j-th iteration of LocalPhase on each of the induced subgraphs. The parallel algorithm assigns
vertices to subgraphs and then iteratively runs LocalPhase on each of them. In this analysis we ignore
the exact assignment of vertices to subgraphs until they get removed as a member of one of sets Ri , Hi , or
Fi . Instead we look at the conditional distribution on assignments given the configurations of sets Ri , Hi ,
and Fi removed in the previous iterations corresponding to EmulatePhase. We write Dj , 1 ≤ j ≤ τ , to
denote this distribution of assignments before the execution of j-th iteration of LocalPhase on the induced
subgraphs, which corresponds to the j-th iteration of EmulatePhase for this iteration of the main loop of
ParallelAlg. Additionally, we write Dτ +1 to denote the same distribution after the τ -th iteration, i.e.,
at the end of the execution of the parallel block in Lines 6–8 of ParallelAlg. Due to Lemma 4.3, the
distributions of assignments are all independent. We define ǫj , j ∈ [τ + 1], to be the minimum positive value
such that Dj is ǫj -near uniform. Obviously, ǫ1 = 0, since the first distribution corresponds to a perfectly
uniform assignment. We want to apply Lemma 4.4 inductively to bound the value of ǫj+1 as a function of
ǫj with high probability. The lemma lists two conditions: ǫj must be at most (200 ln n)−1 and the threshold
2
passed to EmulatePhase has to be at least 4000µ−2
H ln n. The latter condition holds due to Lemma 5.1.
Hence as long as ǫj is sufficiently small, Lemma 4.4 implies that with probability at least 1 − n−4 ,
!
!
 −15/64
−1/4

∆
∆
+ ǫj ≤ 60α
+ ǫj ,
ǫj+1 ≤ 60α
2τ −1 m
m
35

and no high degree vertex survives in the remaining graph. One can easily show by induction that if this

∆ −15/64
for all j ∈ [τ + 1]. In particular,
recursion is satisfied for all 1 ≤ j ≤ τ , then ǫj ≤ (120α)j−1 · m
by the definition of τ and Lemma 5.1, for any j ∈ [τ ],
τ −1

ǫj ≤ (120α)

·



∆
m

−15/64

≤



∆
m

1/16  −15/64  −11/64
∆
∆
·
≤
≤ (200 ln n)−1 ,
m
m

This implies that as long the unlikely events specified in Lemma 4.4 do not occur for any phase in any
iteration of the main loop of ParallelAlg, we obtain the desired properties: all intermediate distributions
of possible assignments are (200 ln n)−1 -near uniform and the maximum degree in the graph decreases at
the expected rate. It remains to bound the probability of those unlikely events occurring for any phase. By
the union bound, their total probability is at most log n · n−4 ≤ n−3 .
We now prove that the algorithm finds a large matching with constant probability.
Theorem 5.4. Let MOPT be an arbitrary maximum matching in a graph G. With Ω(1) probability, ParallelAlg
constructs a matching of size Ω(|MOPT |).
Proof. By combining Lemma 5.2 and Lemma 5.3, we learn that with probability at least 1−n·n−8 −n−3 ≥
1 − 2n−3 , we obtain a few useful properties. First, all relevant distributions corresponding to iterations of
EmulatePhase are independent and (200 ln n)−1 -near uniform. Second, the maximum degree in the
graph induced by vertices still under consideration is bounded by 32 ∆ before and after every simulated
execution of EmulatePhase, where ∆ is the corresponding. As a result, no vertex is deleted in Lines 7
or 12 due to the security checks.
We now use Lemma 4.2 to lower bound the expected size of the matching created in every EmulatePhase
simulation. Let τ⋆ be the number of phases we simulate this way. We have τ⋆ ≤ log n. Let Hj , Fj , and
Mj be random variables equal to the total size of sets Hi , Fi , and Mi created in the j-th phase. If the corresponding distribution in the j-th phase is near uniform and the maximum is bounded, Lemma 4.2 yields
E [Hj + Fj ] ≤ n−9 + 1200 · E [Mj ] ,
i.e.,


1
E [Hj + Fj ] − n−9 .
1200
Overall, without the assumption that the conditions of Lemma 4.2 are always met, we obtain a lower bound
E [Mj ] ≥

X

j∈[τ⋆ ]

E [Mj ] ≥

X

j∈[τ⋆ ]


n
1
E [Hj + Fj ] − n−9 − 2n−3 · ,
1200
2

in which we consider the worst case scenario that we lose as much as n/2 edges in the size of the constructed matching when the unlikely negative events happen. ParallelAlg continues the construction of
a matching by directly simulating the global algorithm. Let τ⋆′ be the number of phases in that part of the
algorithm. We define H′j , F′j , and M′j , for j ∈ [τ⋆′ ], to be random variables equal to the size of sets H, F ,
f in GlobalAlg in the j-th phase of the simulation. By Lemma 3.3, we have
and M
X

j∈[τ⋆′ ]

X 1
 


E M′j ≥
E H′j + F′j .
50
′
j∈[τ⋆ ]

36

By combining both bounds we obtain a lower bound on the size of the constructed matching. Let
X
X  
def
M⋆ =
E [Mj ] +
E M′j
j∈[τ⋆ ]

j∈[τ⋆′ ]

be the expected matching size, and let
X
X 

def
V⋆ =
E [Hj + Fj ] +
E H′j + F′j .
j∈[τ⋆ ]

j∈[τ⋆′ ]

We have

1
1
V⋆ − 2 .
1200
n
Consider a maximum matching MOPT . At the end of the algorithm, the graph is empty. The expected
number of edges in MOPT incident to a vertex in one of the reference sets is bounded by |MOPT | · 2µR ·
log n ≤ 10−5 |MOPT |. The expected number of edges removed by the security checks is bounded by n2 ·n−3 .
Hence the expected number of edges in MOPT deleted as incident to vertices that are heavy or are friends is
at least (1 − 10−5 )|MOPT | − 1/(2n2 ). Since we can assume without the loss of generality that the graph is
1
|MOPT | − n12 . For sufficiently
non-empty, it is at least 21 |MOPT |. Hence V⋆ ≥ 21 |MOPT |, and M⋆ ≥ 2400
large n (say, n ≥ 50), M⋆ ≥ Ω (|MOPT |) and by an averaging argument, ParallelAlg has to output an
O(1)-multiplicative approximation to the maximum matching with Ω(1) probability. For smaller n, it is not
difficult to show that at least one edge is output by the algorithm with constant probability as long as it is
not empty.
M⋆ ≥

Finally, we want to argue that the above procedure can be used to compute 2 + ǫ approximation to
maximum matching at the cost of increasing the running time by a factor of log(1/ǫ). The idea is to;
execute algorithm ParallelAlg to compute constant approximate matching; remove this matching from
the graph; and repeat.
Corollary 5.5. Let MOPT be an arbitrary maximum matching in a graph G. For any ǫ > 0, executing
ParallelAlg on G and removing a constructed matching repetitively, O(log(1/ǫ)) times, finds a multiplicative (2 + ǫ)-approximation to maximum matching, with Ω(1) probability.
Proof. Assume that the ParallelAlg succeeds with probability p and computes c-approximate matching.
Observe that each successful execution of ParallelAlg finds a matching Mc of size at least 1c |MOPT |.
Removal of Mc from the graph decreases the size of optimal matching by at least 1c |MOPT | and at most
by 2c |MOPT |, because each edge of Mc can be incident to at most two edges of MOPT . Hence, when the
size of the remaining matching drops to at most ǫ|MOPT |, we have an 2 + ǫ-multiplicative approximation
to maximum matching constructed. The number t of successful applications of ParallelAlg need to
satisfy.


1 t
≤ ǫ.
1−
c
This gives t = O(log(1/ǫ)). In ⌈t/p⌉ = O(log(1/ǫ)) executions, we have t successes with probability at
least 1/2 by the properties of the median of the binomial distribution.

37

6 MPC Implementation Details
In this section we present details of an MPC implementation of our algorithm. We also analyze its round and
space complexity. In the description we heavily use some of the subroutines described in [GSZ11]. While
the model used there is different, the properties of the distributed model used in [GSZ11] also hold in the
MPC model. Thus, the results carry over to the MPC model.
The results of [GSZ11] allow us to sort a set A of O(N ) key-value pairs of size O(1) and for every
element of a sorted list, compute its index. Moreover, we can also do a parallel search: given a collection A
of O(N ) key-value pairs and a collection of O(N ) queries, each containing a key of an element of A, we can
annotate each query with the corresponding key-value pair from A. Note that multiple queries may ask for
the same key, which is nontrivial to parallelize. If S = nΩ(1) , all the above operations can be implemented
in O(1) rounds.
The search operation allows us to broadcast information from vertices to their incident edges. Namely,
we can build a collection of key-value pairs, where each key is a vertex and the value is the corresponding
information. Then, each edge {u, v} may issue two queries to obtain the information associated with u and
v.

6.1 GlobalAlg
We first show how to implement GlobalAlg, which is called in Line 13 of ParallelAlg.
Lemma 6.1. Let S = nΩ(1) . There exists an implementation of GlobalAlg in the MPC model, which with
e rounds and uses O(S) space per machine.
high probability executes O(ln ∆)

Proof. We first describe how to solve the following subproblem. Given a set X of marked vertices, for each
vertex v compute |N (v) ∩ X|. When all vertices are marked, this just computes the degree of every vertex.
The subproblem can be solved as follows. Create a set AX = {(u, v) | u ∈ V, v ∈ X, {u, v} ∈
E} ∪ {(v, −∞), (v, ∞) | v ∈ V }, and sort its elements lexicographically. Denote the sorted sequence by
QX . Then, for each element of AX compute its index in QA .
Note that |N (v) ∩ X| is equal to the number of elements in QX between (v, −∞) and (v, ∞). Thus,
having computed the indices of these two elements, we can compute |N (v) ∩ X|.
Let us now describe how to implement GlobalAlg. We can compute the degrees of all vertices, as
described above. Once we know the degrees, we can trivially mark the vertices in H. The next step is to
compute F and for that we need to obtain |N (v) ∩ H|, which can be done as described above.
After that, GlobalAlg computes a matching in G[H ∪ F ] by calling MatchHeavy (see Algorithm 2).
In the first step, MatchHeavy assigns to every v ∈ F a random neighbor v⋆ in H. This can again be
easily done by using the sequence QH (i.e. QX build for X = H). Note that for each v ∈ F we know the
number of neighbors of v that belong to H. Thus, each vertex v can pick an integer rv ∈ [1, |N (v) ∩ H|]
uniformly at random. Then, by adding rv and the index of (v, −∞) in QH , we obtain the index in QH , which
corresponds to an edge between v and its random neighbor in H. The remaining lines of MatchHeavy are
straightforward to implement. The vertices can trivially pick their colors. After that, the set E⋆ can be easily
computed by transmitting data from vertices to their adjacent edges. Implementing the following steps of
MatchHeavy is straightforward. Finally, picking the edges to be matched is analogous to the step, when
for each v ∈ F we picked a random neighbor in H.
Overall, each phase of GlobalAlg (that is, iteration of the main loop) is executed in O(1) rounds.
e rounds as advertised.
Thus, by Lemma 3.3, GlobalAlg can be simulated in O(ln ∆)
38

6.2 Vertex and edge partitioning
We now show how to implement Line 5 and compute the set of edges that are used in each call to LocalPhase
in Line 8 of ParallelAlg. Our goal is to annotate each edge with the machine number it is supposed to
go to. To that end, once the vertices pick their machine numbers, we broadcast them to their adjacent edges.
Every edge that receives two equal numbers x is assigned to machine x.
In the implementation we do not check whether a machine is assigned too many edges (Line 7), but rather
show in Lemma 5.2 that not too many edges are assigned with high probability.

6.3 LocalPhase
We now discuss the implementation of LocalPhase. Observe that LocalPhase is executed locally.
Therefore, the for loop at Line 8 of ParallelAlg can also be executed locally on each machine. Thus,
we only explain how to process the output of LocalPhase.
Instead of returning the set of vertices and matched edges at Line 6 of LocalPhase, each vertex that
should be returned is marked as discarded, and each matched edge is marked as matched. After that,
we need to discard edges, whose at least one endpoint has been discarded. This can be done by broadcasting
information from vertices to adjacent edges. Note that some of the discarded edges might be also marked as
matched.

6.4 Putting all together
Lines 5, 7 and 8 can be implemented as described in sections 6.2 and 6.3. Lines 9 and 10 do not need an
actual implementation, as by that point all the vertices that are not marked as discarded constitute V ′ ,
and all the edges incident to V \ V ′ will be marked as discarded. Similarly, all the matched edges will be
marked as matched by the implementation of LocalPhase. All the edges and vertices that are marked
as discarded will be ignored in further processing. After all the rounds are over, the matching consists
of the edges marked as matched.
Let ∆⋆ be the value of ∆ at Line 12, and hence the value of ∆ at the end of the last while loop iteration.
Let ∆′ be the value of ∆ just before the last iteration, i.e. ∆⋆ = ∆′ /2τ , for the corresponding τ . Now
consider the last call of LocalPhase at Line 8. The last invocation has ∆′ /(2τ −1 ) as a parameter. On
the other hand, by Claim 4.7 and Claim 4.8 we know that after the last invocation of LocalPhase with
high probability there is no vertex that has degree greater then 43 ∆′ /(2τ −1 ) < 2∆⋆ . Therefore, with high
probability there is no vertex that should be removed at Line 12, and hence we do not implement that line
either.
An implementation of Line 13 is described in Section 6.1. Finally, we can state the following result.
Lemma 6.2. There exists an implementation
of ParallelAlg in the MPC model that with high probabiln
2
ity executes O (log log n) + max log S , 0 rounds.

Proof. In the proof we analyze the case S ≤ n. Otherwise, for the case S > n, we think of each machine
being split into ⌊S/n⌋ "smaller" machines, each of the smaller machines having space n.
We will analyze the number of iterations of the while loop ParallelAlg performs. Let ∆i and τi be
the value of ∆ and τ at the end of iteration i, respectively. Then, from Line 3 and Line 4 we have
r


1
1
S∆i−1
1
log120α (∆i−1 /m) ≥
log120α (∆i−1 /m) ≥
log120α
.
τi =
16
16
16
n
39

Define γ :=

1
32 log2 120α .

By plugging in the above bound on τi , from Line 11, we derive
1
− 16
log120α

τi

∆i = ∆i−1 · 2 ≤ ∆i−1 · 2

q

S∆i−1
n

log

S∆i−1
n
2 120α

2
− 32 log

= ∆i−1 · 2

= ∆1−γ
i−1

 n γ
S

(6)

To obtain the number of iterations the while loop of ParallelAlg performs, we derive for which
i ≥ 1 the condition at Line 2 does not hold.
Unraveling ∆i−1 further from (6) gives
∆i ≤

(1−γ)i
∆0

j
 n γ Pi−1
j=0 (1−γ)

S

≤n

(1−γ)i

 n γ 1−(1−γ)i
1−(1−γ)

S

i

= n(1−γ)

 n 1−(1−γ)i
S

(7)

Observe that (c log log n)−1 ≤ γ ≤ (32 log log n)−1 < 1/2, for an absolute constant c and n ≥ 4.
For S ≤ n and as γ < 1/2 we have
 n 1−(1−γ)i
S

On the other hand, for i⋆ =

log log n
γ

≤

n
.
S

(8)

≤ c(log log n)2 we have
i⋆

n(1−γ)

< log n.

(9)

Now putting together (7), (8), and (9) we conclude
∆ i⋆ <

n
ln n,
S


and hence the number of iteration the while loop of ParallelAlg performs is O (log log n)2 .

Total round complexity. Every iteration of the while loop can be executed in O(1) MPC rounds with
probability at least 1 − 1/n3 . Since there are O (log log n)2 iterations of the while loop, all the iterations
of the loop can be performed in O (log log n)2 many rounds with probability at least 1 − 1/n2 .
On the other hand, by Lemma 6.1 and the condition at Line 2 ofParallelAlg, the computation
of Line 13 of ParallelAlg can be performed in O log Sn (ln n)32 rounds. Putting theboth bounds
together we conclude that the round complexity of ParallelAlg is O (log log n)2 + log Sn for the case
S ≤ n. For the case S > n (recall that in this regime we assume that each machine is divided into machines
of space n) the round complexity is O (log log n)2 .

Acknowledgments

We thank Sepehr Assadi, Mohsen Ghaffari, Cameron Musco, Christopher Musco, Seth Pettie, and Govind
Ramnarayan for helpful discussions and comments. A. Czumaj was supported in part by the Centre for Discrete Mathematics and its Applications (DIMAP), Royal Society International Exchanges Scheme 2013/R1,
IBM Faculty Award, and the EPSRC award EP/N011163/1. A. Madry
˛
was supported in part by an Alfred
P. Sloan Research Fellowship, Google Research Award, and the NSF grant CCF-1553428. S. Mitrović was
supported in part by the Swiss NSF grant P1ELP2_161820. P. Sankowski was partially supported by grant
NCN2014/13/B/ST6/00770 of Polish National Science Center and ERC StG grant TOTAL no. 677651.

40

References
[ABB+ 17] Sepehr Assadi, MohammadHossein Bateni, Aaron Bernstein, Vahab S. Mirrokni, and Cliff
Stein. Coresets meet EDCS: algorithms for matching and vertex cover on massive graphs.
CoRR, abs/1711.03076, 2017.
[ABI86]

Noga Alon, László Babai, and Alon Itai. A fast and simple randomized parallel algorithm for
the maximal independent set problem. Journal of Algorithms, 7(4):567–583, 1986.

[AG15]

Kook Jin Ahn and Sudipto Guha. Access to data and number of iterations: Dual primal algorithms for maximum matching under resource constraints. In Proceedings of the 27th ACM on
Symposium on Parallelism in Algorithms and Architectures, SPAA 2015, Portland, OR, USA,
June 13–15, 2015, pages 202–211, 2015.

[AK17]

Sepehr Assadi and Sanjeev Khanna. Randomized composable coresets for matching and vertex
cover. In Proceedings of the 29th ACM Symposium on Parallelism in Algorithms and Architectures, SPAA 2017, Washington DC, USA, July 24–26, 2017, pages 3–12, 2017.

[ANOY14] Alexandr Andoni, Aleksandar Nikolov, Krzysztof Onak, and Grigory Yaroslavtsev. Parallel
algorithms for geometric graph problems. In Proceedings of the 46th ACM Symposium on
Theory of Computing, STOC 2014, New York, NY, USA, May 31–June 3, 2014, pages 574–583,
2014.
[Ass17]

Sepehr Assadi. Simple round compression for parallel vertex cover. CoRR, abs/1709.04599,
September 2017.

[BCH17]

Sayan Bhattacharya, Deeparnab Chakrabarty, and Monika Henzinger. Deterministic fully dynamic approximate vertex cover and fractional matching in O(1) amortized update time. In
Proceedings of the 19th International Conference on Integer Programming and Combinatorial
Optimization, IPCO 2017, Waterloo, ON, Canada, June 26–28, 2017, pages 86–98, 2017.

[BH87]

Paul Beame and Johan Hastad. Optimal bounds for decision problems on the CRCW PRAM. In
Proceedings of the 19th Annual ACM Symposium on Theory of Computing, STOC 1987, pages
83–93, New York, NY, USA, 1987.

[BHI15]

Sayan Bhattacharya, Monika Henzinger, and Giuseppe F. Italiano. Deterministic fully dynamic
data structures for vertex cover and matching. In Proceedings of the 26th Annual ACM-SIAM
Symposium on Discrete Algorithms, SODA 2015, San Diego, CA, USA, January 4–6, 2015,
pages 785–804, 2015.

[BHN16]

Sayan Bhattacharya, Monika Henzinger, and Danupon Nanongkai. New deterministic approximation algorithms for fully dynamic matching. In Proceedings of the 48th Annual ACM
SIGACT Symposium on Theory of Computing, STOC 2016, Cambridge, MA, USA, June 18–
21, 2016, pages 398–411, 2016.

[BHN17]

Sayan Bhattacharya, Monika Henzinger, and Danupon Nanongkai. Fully dynamic approximate maximum matching and minimum vertex cover in O(log3 n) worst case update time. In
Proceedings of the 28th Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2017,
Barcelona, Spain, Hotel Porta Fira, January 16–19, pages 470–489, 2017.
41

[BKS13]

Paul Beame, Paraschos Koutris, and Dan Suciu. Communication steps for parallel query processing. In Proceedings of the 32nd ACM SIGMOD-SIGACT-SIGART Symposium on Principles of Database Systems, PODS 2013, New York, NY, USA, June 22–27, 2013, pages 273–284,
2013.

[BKS14]

Paul Beame, Paraschos Koutris, and Dan Suciu. Skew in parallel query processing. In Proceedings of the 33rd ACM SIGMOD-SIGACT-SIGART Symposium on Principles of Database
Systems, PODS’14, Snowbird, UT, USA, June 22–27, 2014, pages 212–223, 2014.

[BS15]

Aaron Bernstein and Cliff Stein. Fully dynamic matching in bipartite graphs. In Proceedings of
the 42nd International Colloquium on Automata, Languages, and Programming, ICALP 2015,
Kyoto, Japan, July 6–10, 2015, Proceedings, Part I, pages 167–179, 2015.

[BS16]

Aaron Bernstein and Cliff Stein. Faster fully dynamic matchings with small approximation ratios. In Proceedings of the 27th Annual ACM-SIAM Symposium on Discrete Algorithms, SODA
2016, Arlington, VA, USA, January 10–12, 2016, pages 692–711, 2016.

[DG04]

Jeffrey Dean and Sanjay Ghemawat. MapReduce: Simplified data processing on large clusters.
In Proceedings of the 6th Conference on Symposium on Opearting Systems Design & Implementation, Volume 6, OSDI’04, pages 10–10, Berkeley, CA, USA, 2004. USENIX Association.

[DG08]

Jeffrey Dean and Sanjay Ghemawat. MapReduce: Simplified data processing on large clusters.
Commununication of the ACM, 51(1):107–113, January 2008.

[Edm65]

Jack Edmonds. Paths, trees and flowers. Canadian Journal of Mathematics, pages 449–467,
1965.

[FG17]

Manuela Fischer and Mohsen Ghaffari. Deterministic distributed matching: Simpler, faster,
better. CoRR, abs/1703.00900, 2017.

[FMS+ 10] Jon Feldman, S. Muthukrishnan, Anastasios Sidiropoulos, Clifford Stein, and Zoya Svitkina. On distributing symmetric streaming computations. ACM Transactions on Algorithms,
6(4):66:1–66:19, 2010.
[GSZ11]

Michael T. Goodrich, Nodari Sitchinava, and Qin Zhang. Sorting, searching, and simulation
in the MapReduce framework. In International Symposium on Algorithms and Computation,
pages 374–383. Springer, 2011.

[HKP99]

Michał Hańćkowiak, Michał Karoński, and Alessandro Panconesi. A faster distributed algorithm for computing maximal matchings deterministically. In Proceedings of the Eighteenth
Annual ACM Symposium on Principles of Distributed Computing, PODC ’99, pages 219–228,
New York, NY, USA, 1999. ACM.

[HKP01]

Michał Hańćkowiak, Michał Karoński, and Alessandro Panconesi. On the distributed complexity of computing maximal matchings. SIAM Journal on Discrete Mathematics, 15(1):41–57,
2001.

[HRVZ15] Zengfeng Huang, Božidar Radunović, Milan Vojnović, and Qin Zhang. Communication complexity of approximate matching in distributed graphs. In Proceedings of the 32nd International Symposium on Theoretical Aspects of Computer Science, STACS 2015, March 4–7, 2015,
Garching, Germany, pages 460–473, 2015.
42

[IBY+ 07] Michael Isard, Mihai Budiu, Yuan Yu, Andrew Birrell, and Dennis Fetterly. Dryad: Distributed
data-parallel programs from sequential building blocks. SIGOPS Operating Systems Review,
41(3):59–72, March 2007.
[II86]

Amos Israeli and Alon Itai. A fast and simple randomized parallel algorithm for maximal
matching. Information Processing Letters, 22(2):77–80, 1986.

[IS86]

Amos Israeli and Yossi Shiloach. An improved parallel algorithm for maximal matching. Information Processing Letters, 22(2):57–60, 1986.

[KKS14]

Michael Kapralov, Sanjeev Khanna, and Madhu Sudan. Approximating matching size from
random streams. In Proceedings of the 25th Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2014, Portland, Oregon, USA, January 5–7, 2014, pages 734–751, 2014.

[KMW06] Fabian Kuhn, Thomas Moscibroda, and Roger Wattenhofer. The price of being near-sighted.
In Proceedings of the 17th Annual ACM-SIAM Symposium on Discrete Algorithm, SODA 2006,
pages 980–989, Philadelphia, PA, USA, 2006. Society for Industrial and Applied Mathematics.
[KSV10]

Howard J. Karloff, Siddharth Suri, and Sergei Vassilvitskii. A model of computation for MapReduce. In Proceedings of the 21st Annual ACM-SIAM Symposium on Discrete Algorithms, SODA
2010, Austin, Texas, USA, January 17–19, 2010, pages 938–948, 2010.

[LMSV11] Silvio Lattanzi, Benjamin Moseley, Siddharth Suri, and Sergei Vassilvitskii. Filtering: a method
for solving graph problems in MapReduce. In Proceedings of the 23rd Annual ACM Symposium
on Parallelism in Algorithms and Architectures, SPAA 2011, San Jose, CA, USA, June 4–6, 2011,
pages 85–94, 2011.
[LPP15]

Zvi Lotker, Boaz Patt-Shamir, and Seth Pettie. Improved distributed approximate matching.
Journal of the ACM, 62(5):38:1–38:17, November 2015.

[Lub86]

Michael Luby. A simple parallel algorithm for the maximal independent set problem. SIAM
Journal on Computing, 15(4):1036–1053, 1986.

[McG05]

Andrew McGregor. Finding graph matchings in data streams. In Approximation, Randomization
and Combinatorial Optimization, Algorithms and Techniques, 8th International Workshop on
Approximation Algorithms for Combinatorial Optimization Problems, APPROX 2005 and 9th
InternationalWorkshop on Randomization and Computation, RANDOM 2005, Berkeley, CA,
USA, August 22-24, 2005, Proceedings, pages 170–181, 2005.

[OR10]

Krzysztof Onak and Ronitt Rubinfeld. Maintaining a large matching and a small vertex cover.
In Proceedings of the 42nd ACM Symposium on Theory of Computing, STOC 2010, Cambridge,
Massachusetts, USA, 5–8 June 2010, pages 457–464, 2010.

[PR07]

Michal Parnas and Dana Ron. Approximating the minimum vertex cover in sublinear time and a
connection to distributed algorithms. Theoretical Computer Science, 381(1-3):183–196, 2007.

[RVW16]

Tim Roughgarden, Sergei Vassilvitskii, and Joshua R. Wang. Shuffles and circuits: On lower
bounds for modern parallel computation. In Proceedings of the 28th ACM Symposium on Parallelism in Algorithms and Architectures, SPAA 2016, Asilomar State Beach/Pacific Grove, CA,
USA, July 11–13, 2016, pages 1–12, 2016.
43

[Whi12]

Tom White. Hadoop: The Definitive Guide. O’Reilly Media, Inc., 2012.

[ZCF+ 10] Matei Zaharia, Mosharaf Chowdhury, Michael J. Franklin, Scott Shenker, and Ion Stoica. Spark:
Cluster computing with working sets. In 2nd USENIX Workshop on Hot Topics in Cloud Computing, HotCloud’10, Boston, MA, USA, June 22, 2010.

44

