Foundations and Trends® in Optimization

Massively Parallel Computation:
Algorithms and Applications
Suggested Citation: Sungjin Im, Ravi Kumar, Silvio Lattanzi, Benjamin Moseley andSergei Vassilvitskii (2023), “Massively Parallel Computation: Algorithms and Applications”, Foundations and Trends® in Optimization: Vol. 5, No. 4, pp 340–417. DOI:
10.1561/2400000025.

Sungjin Im
University of California, Merced
Ravi Kumar
Google, Mountain View
Silvio Lattanzi
Google, Barcelona
Benjamin Moseley
Carnegie Mellon University
Sergei Vassilvitskii
Google, New YorkThis article may be used only for the purpose of research, teaching,
and/or private study. Commercial use or systematic downloading (byrobots or other automatic processes) is prohibited without explicit
Publisher approval.

Boston — DelftContents

1 Introduction
341
1.1 Purpose of This Monograph . . . . . . . . . . . . . . . . . 343
1.2 Prerequisites . . . . . . . . . . . . . . . . . . . . . . . . . 344
2 The MPC Model
345
2.1 Formal Definition . . . . . . . . . . . . . . . . . . . . . . 346
2.2 Example: Word Frequencies in Two Rounds . . . . . . . . 348
2.3 Other Related Models . . . . . . . . . . . . . . . . . . . . 350
2.4 Section Notes . . . . . . . . . . . . . . . . . . . . . . . . 353
3 Partitioning and Coresets354
3.1 Overview . . . . . . . . . . . . . . . . . . . . . . . . . . . 355
3.2 Application: Minimum Spanning Tree . . . . . . . . . . . . 355
3.3 Application: k-Center Clustering . . . . . . . . . . . . . . 357
3.4 Coresets . . . . . . . . . . . . . . . . . . . . . . . . . . . 358
3.5 Application: k-Center Clustering in Euclidean Space . . . . 359
3.6 Problems . . . . . . . . . . . . . . . . . . . . . . . . . . . 360
3.7 Section Notes . . . . . . . . . . . . . . . . . . . . . . . . 361
4 Sample and Prune
362
4.1 Overview . . . . . . . . . . . . . . . . . . . . . . . . . . . 362
4.2 Application: Top k Selection . . . . . . . . . . . . . . . . 366

4.3 Application: k-Center Clustering . . . . . . . . . . . . . . 366
4.4 Application: Monotone Submodular Maximization Subject
to a Cardinality Constraint . . . . . . . . . . . . . . . . . 368
4.5 Section Notes . . . . . . . . . . . . . . . . . . . . . . . . 369
5 Dynamic Programming
371
5.1 Overview . . . . . . . . . . . . . . . . . . . . . . . . . . . 372
5.2 Warm-up: Knapsack . . . . . . . . . . . . . . . . . . . . . 374
5.3 Interval Selection in MPC . . . . . . . . . . . . . . . . . . 376
5.4 Approximate Dynamic Programs . . . . . . . . . . . . . . 379
5.5 Section Notes . . . . . . . . . . . . . . . . . . . . . . . . 380
6 Round Reduction via Sampling381
6.1 k-core Decomposition and a Sequential Algorithm . . . . . 381
6.2 Parallelizing the Sequential Algorithm: O(log n) Rounds . . 383
6.3 Round Compression via Random Vertex Partitioning:O(log log n) Rounds . . . . . . . . . . . . . . . . . . . . . 386
6.4 Section Notes . . . . . . . . . . . . . . . . . . . . . . . . 388
7 Round Reduction via Graph Exponentiation
390
7.1 Approximate Core Decomposition . . . . . . . . . . . . . . 391
7.2 Connected Components . . . . . . . . . . . . . . . . . . . 396
7.3 Section Notes . . . . . . . . . . . . . . . . . . . . . . . . 402
8 Lower Bounds
403
8.1 Connectivity in MPC . . . . . . . . . . . . . . . . . . . . 403
8.2 Unconditional Lower Bounds . . . . . . . . . . . . . . . . 404
8.3 Conditional Lower Bounds . . . . . . . . . . . . . . . . . . 408
8.4 Section Notes . . . . . . . . . . . . . . . . . . . . . . . . 410
9 Conclusions

411

References412

Massively Parallel Computation:
Algorithms and Applications
Sungjin Im1 , Ravi Kumar2 , Silvio Lattanzi3 , Benjamin Moseley4 andSergei Vassilvitskii5
1 University of California, Merced, USA; sim3@ucmerced.edu
2 Google, Mountain View, USA; ravi.k53@gmail.com
3 Google, Barcelona, Spain; silviol@google.com
4 Carnegie Mellon University, USA; moseleyb@andrew.cmu.edu
5 Google, New York, USA; sergeiv@google.com

ABSTRACTThe algorithms community has been modeling the underlying key features and constraints of massively parallel frameworks and using these models to discover new algorithmic
techniques tailored to them. This monograph focuses on the
Massively Parallel Model of Computation (MPC) framework,
also known as the MapReduce model in the literature. It
describes algorithmic tools that have been developed to leverage the unique features of the MPC framework. These tools
were chosen for their broad applicability, as they can serve asbuilding blocks to design new algorithms. The monograph is
not exhaustive and includes topics such as partitioning andcoresets, sample and prune, dynamic programming, roundcompression, and lower bounds.

Sungjin Im, Ravi Kumar, Silvio Lattanzi, Benjamin Moseley and Sergei Vassilvitskii(2023), “Massively Parallel Computation: Algorithms and Applications”, Foundations
and Trends® in Optimization: Vol. 5, No. 4, pp 340–417. DOI: 10.1561/2400000025.
©2023 S. Im et al.

1Introduction

The modern era is witnessing a revolution in the ability to scale computations to massively large data sets. A key breakthrough in scalability
was the introduction of fast and easy-to-use distributed programming
models such as MapReduce (Dean and Ghemawat, 2008), Hadoop(hadoop.apache.org), and Spark (spark.apache.org). We refer to these
programming models as massively parallel frameworks.
Massively parallel frameworks were originally designed for relatively
simple types of computations such as counting the frequency of words
in a data set. Since then, they have been shown to be useful for a far
richer class of applications. The goal of a recent line of work is to study
these frameworks algorithmically to unlock their true underlying powerand expand their applicability. The hope is, through an algorithmic
investigation, to achieve successes similar to those on topics such as
cache-oblivious algorithms (Frigo et al., 2012) and data streaming
algorithms (McGregor, 2014).
Practically, massively distributed frameworks enable programmers
to easily deploy algorithms on tens to thousands of machines. Algorithmically, the frameworks have restrictions on their computational
expressive power to help ensure programs can be efficiently parallelized.

341

342

Introduction

The challenges are then to (i) develop simple tools that reveal fundamentals of massive computation and aid algorithm design and (ii)understand which computations can benefit from the framework.
The algorithms community has been addressing this problem bymodeling the underlying key features and constraints of massively parallel frameworks and using these models to discover new algorithmic
techniques tailored to them. The first model of massively parallel computation was introduced for the MapReduce framework by Karloff et al.
(2010) and several variants have been proposed since (Feldman et al.,2010; Koutris et al., 2018; Beame et al., 2017; Andoni et al., 2014; Goeland Munagala, 2012; Goodrich et al., 2011; Pietracaprina et al., 2012;
Roughgarden et al., 2016). Perhaps the main advantage of the modelin Karloff et al. (2010) is its relative simplicity. It captures framework
characteristics that are sufficient for algorithm design, without delving
into the plethora of system parameters. In this monograph, we will
primarily focus on this version of the model; we call it the Massively
Parallel Model of Computation (MPC). See Section 2 for formal details.
The MPC model is a special case of the Bulk-Synchronous-Parallel(BSP) model of Valiant (1990), where machines have sublinear memory(i.e., nδ for δ < 1 and input size n) and computation proceeds inalternating rounds of communication and sequential computation. The
MPC model can be thought of making different trade-offs than theclassic PRAM computational model. Much of the difference comes frombeing able to run a sequential algorithm on a small sublinear portion of
the data during a single round. Full details are given in Section 2.
The MPC model has a strong connection to practice and this isdemonstrated by algorithmic developments resulting in good practical
performance (Chierichetti et al., 2010; Bahmani et al., 2012a; Suri
and Vassilvitskii, 2011; Karloff et al., 2010; Mirzasoleiman et al., 2013;
Broder et al., 2014; Feldman et al., 2010; Zhao et al., 2012; Ene etal., 2011; Malkomes et al., 2015; Kumar et al., 2015; Bahmani et al.,2012b; Ene and Nguyen, 2015; Cohen-Addad et al., 2021b; CohenAddad et al., 2021a; Lattanzi et al., 2019; Ghaffari et al., 2019b; Bateni
et al., 2017; Assadi et al., 2019b; Bhaskara and Wijewardena, 2018)
and influencing software libraries. For example, theoretical algorithms

1.1. Purpose of This Monograph343

for k-means clustering have been incorporated in the Spark Machine
Learning software library1 (Bahmani et al., 2012b).
1.1

Purpose of This MonographThis line of work has demonstrated that massively parallel frameworks
are useful for some challenging applications. With this as a proofof-concept, an exciting area of research is to broaden the use of theframeworks to address a wide range of problems by using theoreticalmodels to drive algorithm design.
This monograph will describe algorithmic tools that have beendeveloped for massively distributed computing that leverage the uniquefeatures of the framework. The tools were chosen because we believe
they are generally applicable and can be used as building blocks todesign algorithms in the area.
This monograph is not exhaustive. However, it will cover the following areas.
• Partitioning and Coresets: This is one of the most natural
approaches for parallel algorithms design. The idea is to partition
the input to the problem across machines, and have each machine
solve the problem on the individual parts. The individual solutions
are then combined to build the solution to the overall problem.
• Sample and Prune: Another common approach to solve problems on large data sets is to use sampling to reduce problem
size. Unfortunately, sampling from simple distributions, such as
uniform, often misses too much information to solve a problem
near optimally. We discuss the iterative sample-and-prune method,which has been shown to be efficient for many problems.
• Dynamic Programming: Dynamic programming is a powerful
technique for solving problems. Unfortunately, it is typically difficult to parallelize. We discuss techniques for adapting certain
dynamic programs to the massively parallel setting.
1

https://spark.apache.org/docs/2.2.0/mllib-clustering.html

344

Introduction• Rounds Reduction: A simulation approach to solve problems ina parallel fashion is to apply a known algorithm, performing one
step in a single round of distributed computation. While simple,
it is often inefficient and leads to a large number of rounds. We
discuss round compression, where multiple iterative rounds arecompressed into a single round.
• Lower Bounds: Finally, we discuss the limitations of the massively parallel model of computation. We highlight the efforts todevelop lower bounds for the model and derive connections toother models of computation.
1.2

Prerequisites

This monograph will assume the basics on approximation algorithm
design and randomized algorithms. For a quick overview, we recommend the books by Williamson and Shmoys (2011, Chapter 2) and
Mitzenmacher and Upfal (2005, Chapters 1-4).

2
The MPC Model

The goal of this section is to formally introduce the massively parallel
computing (MPC) model and compare it to other concrete computational models. In some cases, the MPC model can provably simulate
algorithms in other models and vice versa. Further, many of the algorithmic techniques developed for the MPC model have found uses inparallel computing, distributed computing, and data stream algorithms.
Before we introduce the MPC model, we take a step back to consider
three characteristics that summarize the massively parallel framework.
The first is the frequency and synchronicity of communication: howoften do the machines coordinate with each other. The second is the
topology of the communication: what are the allowable communication
channels between machines? The third is the degree of parallelism: how
does the number of parallel tasks grow with the problem size? As wewill see below, different answers to these questions lead to different
models of computation. For instance, the PRAM model restricts neither
the frequency nor the topology, and allows for a super-linear degree ofparallelism; on the other hand, the LOCAL model restricts the topology
and parallelism.

345

346

The MPC Model

The different characteristics also have an effect on the difficultyof programming under these conditions. For example, multithreaded
programming can be a notoriously tricky endeavor, since different executions of the same piece of code may result in different code paths,
leading to code that is very hard to test, and bugs that can be hard
to reproduce. Additionally, an often ignored issue is that of system
failures: with computation happening concurrently on multiple piecesof hardware, the chance of one of them failing increases dramatically,
thus systems must be robust to failures, which leads to even more code
complexity.
Indeed, the development of MapReduce was largely motivated bytrying to hide as much of the system complexity as possible fromthe algorithm designer, at the cost of slightly limiting the model ofcomputation. As Dean and Ghemawat (2008) write in their seminalwork:
The issues of how to parallelize the computation, distributethe data, and handle failures conspire to obscure the original
simple computation with large amounts of complex code to
deal with these issues. As a reaction to this complexity, we
designed a new abstraction that allows us to express thesimple computations we were trying to perform but hides
the messy details of parallelization, fault-tolerance, data
distribution and load balancing in a library.
While the first uses of MapReduce were for simple computations,the framework has proven incredibly versatile and powerful. Researchers
have developed new algorithmic techniques tailored to this computational model and MapReduce-style algorithms are now known andimplemented for a large number of problems, from clustering, andsubmodular optimization, to basic graph problems.
2.1

Formal Definition

The MPC paradigm forces the algorithm designer to break up thecomputation into a sequence of synchronous rounds, where individualtasks must work in isolation during a round, and can communicate with

2.1. Formal Definition347

each other only between rounds. Rounds are relatively expensive, andthus the goal is to minimize the overall number of rounds an algorithm
takes.
Formally, consider an input of size N . To process it, we have pmachines, each with an M -bit memory. Initially, the input is distributed
among the memory of the p machines in an arbitrary manner. For
instance, machine 1 has bits 1 through M , machine 2 has bits M + 1
through 2M , and so on. The computation proceeds in rounds. In eachround each machine reads the M bits from its memory, performs anarbitrary computation on them, and sends its output to the machinesthat need it in the next round. After the final round of computation,
the machines write their result to the final output location. If at any
point one of the machines received more than M bits per round, thecomputation fails.
The model as described is quite general, we next specify the tradeoffs between the size of the input (N ), the number of machines (p), andthe memory for each machine (M ). Clearly in order to store the whole
input for the first round, we must have p ≥ N/M . The key limitationthat makes the MPC model different from other systems is the upperbounds placed on both M and p. Specifically, we require that M = N 1−ϵfor some constant ϵ, thus the amount of input available to each√ machineon any round is a vanishingly small fraction (e.g., M = N ). The′
amount of parallelism is also restricted, and we require that p = N 1−ϵfor some constant ϵ′ . Clearly ϵ′ + ϵ ≤ 1, else all of the input cannot be
stored.
The main metric for evaluating the efficiency of an algorithm in thismodel is the number of rounds that it takes. We aim for algorithms thattake a constant number of rounds, but will see that sometimes that is
not possible, and that a logarithmic number of rounds is necessary.
2.1.1

Discussion

While it may seem that requiring ϵ and ϵ′ to be arbitrary constants gives
too much freedom to the algorithm designer, currently almost all of thealgorithms developed can be adapted to be used with arbitrary settingsof ϵ, at the cost of increasing the number of rounds of computation

348

The MPC Model

within a constant factor. In fact, we will often see algorithms that runin O( 1ϵ ) rounds.
From the setting of the parameters, it is easy to see that the total′
size of the intermediate computation is bounded by M · p = N 2−ϵ−ϵ .
Thus, it is beneficial to keep ϵ′ as large as possible to limit the potential
increase in intermediate computation size. While the model allows forϵ′ to be an arbitrarily small constant, we will again see that mostalgorithms are memory-efficient in their intermediate computation, andsetting ϵ′ ≈ 1 − ϵ is enough.
2.2

Example: Word Frequencies in Two Rounds

Now that we have seen the MPC model, let us consider a simple problem
and give a simple two-round algorithm to solve it. In this problem, theinput is a collection of documents. Each document is a tuple ⟨L, W ⟩consisting of a numeric label L and a list W of words, where the words
are possibly duplicated. The goal is to output the number of times eachdistinct word appears across all documents. For example if the input is⟨0, [‘big’,‘data’]⟩, ⟨1, [‘big’]⟩, the output is (‘big’, 2), (‘data’, 1).
The total input size N is the total number of words across all
documents. Since many words are repeated often in documents (such as“the”),√ for simplicity, we assume that the number of distinct√ words isO( N ). We also assume that each document has at most O( N ) words
and that words√ are of constant size. We give a two-round algorithm
using p = Θ( N ) machines. Initially the documents are distributed
across the p machines.
Round 1In the first round, for each distinct word w on a machine’s local memory,the machine computes the frequency count of w on its local documents.
Let cw,i be the number of occurrences of word w on machine i. Now
each word w picks a unique machine, for example by hashing. Eachmachine i communicates cw,i to the machine designated for word w.

2.2. Example: Word Frequencies in Two Rounds

349

Round 2For each word w, the machine designated for it computes
outputs the resulting count.

Pp

i=1 cw,i andAnalysis
The algorithm runs in two rounds and clearly computes the correct
result. Initially, the data is partitioned equally√ across the machines
so the memory per machine is O(N/p) = O( N ); thus√the memory
requirements are met with ϵ = 1/2. Since there are O( N ) distinct
words, each can be assigned a unique machine given the√ choice of p.
Moreover, each machine sends and receives at most O( N ) pieces of
information between the two rounds, satisfying the communication
requirements.
Note that we made several assumptions for this analysis. The algorithm can be made more robust to relax some of these assumptions.
2.2.1

Easy and Hard Problems in MPC

The above warm-up demonstrates the power and versatility of the
MPC model. Similar techniques can be used to compute statistics
about datasets (e.g., the minimum or maximum element, median, otherquantiles) in constant number of rounds. These basic subroutines canthen be adapted to use for other algorithmic primitives like sorting.
However, many problems that are easy in the sequential model ofcomputation are much harder in MPC. As we will show in the rest of
the sections, we need new methods to adapt other common paradigms
such as dynamic programming, or common problems such as computing
matchings in bipartite and general graphs.
For graphs, in particular, there is an important distinction between
dense (Ω(n1+ϵ ) edges) and sparse (O(n) edges) settings. In the latter,
M = N 1−ϵ = o(n), and therefore one cannot load all of the nodes onto
a single machine. This leads to additional complexity, as even simple
aggregations across nodes take multiple rounds. This aspect is key tothe lower bound construction in Section 8. On the other hand, in thedense case, it is permissible to keep all of the nodes (and even Ω(n))

350

The MPC Modeledges on a machine, which makes some of these operations significantly
easier and allows for additional techniques, such as Sample and Prune(Section 4) and Round Reduction (Section 6).
2.3
2.3.1

Other Related Models
Streaming

In the standard streaming model the input arrives in a sequence thatcan be read in only one direction; reading the whole input sequence
from the first to the last constitutes a pass on in the input. The primary
goal is to perform a certain computation with a small number of passes
using memory whose size is sublinear in the input size. This model hassome subtle differences from the MPC model. In the streaming model
the machine is allowed to read the whole input, albeit in one direction.
In contrast, in the MPC model no single machine ever sees the entire
input. This makes it hard in general to simulate a streaming algorithm
in MPC. Further, streaming algorithms are typically expected to use
a much smaller memory (in many cases, poly log N ) than what eachmachine is allowed in the MPC model; this makes it hard in general tosimulate a MPC algorithm in streaming.
A variant of the streaming model is one augmented with a sorting
primitive. In this variant, a machine is capable of annotating each
item of the input with a key and sorting the items in the sequenceaccording to the keys; this sorting step is considered a pass. Sorting
greatly empowers the streaming model and in fact powerful enoughfor simulating MPC algorithms (albeit without the parallelism). For
example, graph connectivity is a hard problem in the standard streaming
model but can be solved in O(log N ) passes when sorting is allowed.
Yet another variant of streaming that is closer to MPC is the MUD(massive, unordered, distributed) computational model. In this model
the computation has three stages: a local function operates on each itemof the input and produces a message; an aggregator that combines (pairsof) the messages; an optional final post-processing step. The output candepend on the order in which the aggregator operates on the messages.
Streaming algorithms can easily simulate the MUD model while the2.3. Other Related Models

351

converse, for general functions, is not true. For symmetric functions,however, an algorithm in the MUD model can simulate a streaming
algorithm, with the same communication complexity and square of thespace complexity.
2.3.2

Parallel Computing

NC and PRAMs
The standard parallel random access machines (PRAM) model allows
the use of an arbitrary number of machines that share an unbounded
memory in a synchronous way. In each round, each machine does certain
local computations and reads from and/or writes to the shared memory.
A primary goal for studying this model is to understand how muchparallel computing can be exploited to minimize the number of rounds.
NC defines the class of problems that be solved efficiently in the PRAM
model. A problem is in NC if a polynomial (in N ) number of machines
can solve the problem in poly log N rounds.
Although the PRAM has been the most popular model to understand the pure power and limitations of parallel computing, the model
has seen limited application in practice. This is partially due to its
lack of restrictions on the number of machines, (even a linear number
is unrealistic when the input is large), as well as synchronization ofsuch large number of machines. The MPC model is a more realistic
alternative with fewer number of machines but each with significantly
more computing power.
Although the two models, PRAM and MPC, are different, any
CREW PRAM algorithm using at most O(N 2−ϵ ) machines and O(N 2−ϵ )memory can be simulated in MPC Here, CREW stands for concurrent
read and exclusive write, meaning that more than one machine can reada memory cell concurrently but only one can write to it in each round.
BSP
The bulk synchronous parallel model, aims to develop a more realistic
parallel computing model. In this model, computation proceeds in aseries of super-steps. In each super-step, each machine performs some

352

The MPC Model

local computations and sends messages to other machines. The machines
synchronize between the super-steps.
The model has parameters for the memory needed per machine,
local computation time, and time to send messages. The goal is to
reduce the total computation time, which is the sum over the rounds ofthe of the maximum local computations and the maximum time for amachine to receive all the messages.
MPC is a special case of the BSP model where the memory in themachines is restricted, and the number of rounds is used to measure
the running time. BSP gives a more refined analysis of distributed
algorithms, whereas, MPC streamlines the model to allow the algorithm
designer to focus on what are typically the most important aspects, forexample, the number of rounds.
2.3.3

Distributed Computing

Local ModelIn the Local model, there is an undirected graph where each node
represents a machine. Each node, while unaware of the topology, cancommunicate only with its neighbors by sending any amount of data ineach round. All communication happens synchronously in each round.
Note that this model is not as restrictive on the amount of communication allowed per round as the MPC model, but the communication itself
is restricted to between a node and its neighbors. At the end of thecomputation, each node is required to know its portion of the solution,e.g., for a coloring problem, each node should know its color in a propercoloring.
Despite the apparent differences, local algorithms have inspired
new MPC algorithms for various graph algorithms, including maximal
independent set, matching, and coloring; as well as reductions between
the models to prove conditional lower bounds in MPC (see Section 8).
Congested Clique Model
The congested clique model studies the power and the limitations of distributed computing when the amount of data transferred between each2.4. Section Notes

353

pair of computationally unbounded machines is limited for each round,e.g., O(log N ) bits. Note that each machine can communicate with all
the other machines simultaneously; thus, each machine can receive Ω(N )bits in total from other machines in each round. This is unlike the MPC
model where each machine in each round can send/receive o(N ) bits.
On the other hand, the congested clique model is more restrictive than
MPC as it limits the communication between each pair of machines.
Although the two models are not directly comparable to each other, it
is known that any MPC algorithm can be efficiently simulated in thecongested clique model assuming that every machine has a sufficiently
large memory to store all the data it receives from other machines in around.
2.4

Section Notes

MapReduce, as a parallel computing system, stems from the seminal
work of Dean and Ghemawat (2008). The first model formalizing MapReduce was given by Feldman et al. (2010), who gave more of a streaming
variant. The MPC model, which is the focus of this book was introduced
by Karloff et al. (2010).
The Bulk Synchronous Parallel (BSP) model was originally proposed by Valiant (1990), and its connections to MPC were explored by
Goodrich (2010).
The closely related Local model for distributed computing was
proposed by Linial (1987). While making different trade-offs than MPC,
the Local model has inspired numerous MPC algorithms, and lower
bound techniques.
Finally, the connections between MPC and the Congested Cliquemodel were first explored by Hegeman and Pemmaraju (2015).

3
Partitioning and Coresets

The size of the problem instance is a critical constraint for MPC algorithms. Therefore, a natural approach is to try and shrink the given
instance until it becomes small enough to fit in the memory of a single
machine. A simple way to achieve such a size reduction is to partition thegiven instance into smaller sub-instances across the available machines,
solve the sub-instance on each of the machines to obtain sub-solutions,and then combine the sub-solutions to obtain a solution to the given
instance.
We call this the partitioning approach. When the problem at hand
has no dependence between parts of the input, the partitioning approachis particularly powerful. For instance, suppose we want to count the
number of times a specific word appears in a large corpus. It is easy to seethat splitting the corpus across the machines into smaller sub-corpora,counting the number of occurrences of the word in each sub-corpus, andcombining all the counts yields the correct solution, while achieving the
instance-size reduction we seek.
Perhaps what is more surprising is that the same high-level partitioning approach works in situations where seemingly there is a lot
dependence between different parts of the input in producing an optimum solution.
354

3.1. Overview
3.1

355

Overview

Problems for which the partitioning approach can be applied have thefollowing characteristic. Let f be the function that we wish to computeand let A be an algorithm that computes or approximates f . Let X
be the given input. We define the following property of A that will be
useful in designing algorithms based on partitioning.
Definition 3.1 (Partition-friendly Algorithm). An algorithm A is partitionfriendly if for any input X and for any partition X1 ∪ · · · ∪ Xp of X, itholds that A(∪pi=1 A(Xp )) computes or approximates f (X).
Consider the following MPC algorithm to compute or approximate
f using a partition-friendly algorithm A.
Algorithm 1 Partitioning
PartitionA (X)
1: Arbitrarily partition X equally into X1 , . . . , Xp
2: For the ith partition Xi , let Yi = A(Xi )p

3: Fetch Yi ’s from the partitions to one machine to form Y = ∪i=1 Yi
4: returnA(Y )Since A is partition-friendly, the solution output by Algorithm 1 isan approximation to f . Now we discuss the memory requirements of
the algorithm. Since X was partitioned equally, the following statement
is easy to see.
Lemma 3.1. Let r be the size of the output of A. Then, setting thepnumber of partitions p = |X|/r ensures both |Y | and each of thep|Xi |’s are of size O( |X| · r).
3.2

Application: Minimum Spanning Tree

Consider the classical Minimum Spanning Tree (MST) problem. Let
G = (V, E) be an undirected graph on |V | = n vertices and |E| = medges, and let we ∈ R+ be the weight of edge e ∈ E. For ease, let theedges have distinct weights.

356

Partitioning and Coresets

Problem 3.2.1 (Minimum Spanning Tree). Given G = (V, E), find a
subset T ⊆ E of edges such that the edge-induced subgraph on V isPconnected, and the total weight of T , e∈T we , is minimized.
To apply the partitioning framework, for simplicity, we define A to
be any algorithm to find the minimum spanning forest. This is so that
we can use it for graphs that are not connected. Let the input X be
the set E of edges, along with their weights. Let T be the output of
Algorithm 1. We need two facts about A. The first is that the since it
outputs a forest, trivially the size of the output is n. Since |X| = m, bypLemma 3.1, setting p = m/n will make each sub-instance to be of√size O( mn), a substantial reduction from the size of the input graph
G when m is considerably greater than n.
Second, we need to argue that A is partition-friendly. In fact, we
will show that T is indeed the MST of G.
Lemma 3.2. T is the MST of G.
Proof. Let Ei = Xi be the partition of E and let Ti = Yi in Algorithm 1.
Our proof proceeds by showing that none of the edges that was
excluded in any partition, i.e., the edges in Ei \ Ti , can be a part of the
MST of G. Note that since the edge weights are distinct, the MST is
unique.
Recall the cycle property of MSTs: the maximum weight edge inany cycle in G cannot be in the MST, and conversely, any edge not in
the MST is the heaviest edge on some cycle in G.
Now consider an edge e ∈ Ei \ Ti that was removed by the algorithm.
By the cycle property, e must be the heaviest edge on some cycle C ⊂ Ei .
Since Ei ⊂ E, the edge is also the maximum cost edge on the same
cycle C in G, and therefore is not part of the optimal MST T .
Note that the approach above requires partitions be of size at leastΩ(n). If the system constraints are such that one cannot afford to store
all of the graph vertices on a single machine, then the partition approach
no longer works and we need to use other methods to find the MST inparallel.

3.3. Application: k-Center Clustering
3.3

357

Application: k-Center Clustering

The k-center clustering problem is one of the classical clustering problems. At a high level, given a set of n points, the goal is to cover them allby k balls of minimum radius. Formally, consider a metric space equippedwith a distance function d(·, ·) and let X be a set of points in it. The
metric assumption implies that (1) d(x, y)) = d(y, x) for all x, y ∈ X,(2) d(x, x) = 0 and (3: triangle inequality) d(x, y) + d(y, z) ≥ d(x, z)
for all x, y, z ∈ X. We assume each point takes constant memory tostore and the distances d(x, y) can be computed in constant time given
x and y. For a set C in the metric space and a point x ∈ X, letd(x, C) = minc∈C d(x, c).
Problem 3.3.1 (k-Center). Given X = {x1 , . . . , xn }, select k points
C = {c1 , . . . , ck } to minimize maxx∈X d(x, C).
The k-center problem is NP-hard, however there is a simple greedy
algorithm that produces a 2-approximation.Further, this approximation
guarantee is best possible for general metric spaces.
The greedy algorithm begins by selecting an arbitrary point x ∈ X
as the first center c1 . It then repeatedly selects the point in X that isfurthest away from any of the previously chosen centers, and adds it to
the set of centers. The resulting algorithm is a 2-approximation to the
k-center problem. See Algorithm 2 for a formal description.
Algorithm 2 Sequential greedy algorithm for k-center.
Seq-KC(X, k)
1: C ← ∅2: Add an arbitrary point x ∈ X to C
3: while |C| < k doy ← arg maxx∈X d(x, C)C ← C ∪ {y}6: end while
7: return C
4:

5:

We will once again appeal to the partitioning framework by defining
A to be Seq-KC. Let X be the input set of points and C be the output

358

Partitioning and Coresetsof Algorithm 1. As before, we need two facts about A. The first is thepeasy observation that the output is of size k.√
Setting p = n/k, we canensure no sub-instance is of size more than nk, which is sublinear in
the input size for k = o(n).
Second, we show that A is partition-friendly, however with a slightly
worse approximation factor than A.
Lemma 3.3. Algorithm 1 with A being Seq-KC outputs C that is an
8-approximation to the k-center of X.
Proof. Let OPT denote the value of the optimum k-center solution. We
first argue that for any i and any x ∈ Xi , it holds that d(x, Ci ) ≤ 4OPT.
Indeed, since Xi ⊂ X, the value of the optimum solution OPTi on
this partition is no larger than 2OPT. Since Seq-KC returns a 2approximation, we have d(x, Ci ) ≤ 2OPTi ≤ 4OPT.
Now consider Y = ∪i Ci . Since Y ⊂ X, as before, the value of the
optimum solution OPTf is at most the value of 2OPT. Therefore, forany x ∈ Y , we have d(x, C) ≤ 4OPT.
Putting these two facts together yields a 8-approximation. Indeed,
consider any point x ∈ X. If x ∈ Ci for some i, then d(x, C) ≤ 4OPT.
Otherwise, x ∈ Xi for some partition Xi with clustering Ci , and letz ∈ Ci be the point minimizing d(x, Ci ). Then, by the triangle inequality,d(x, C) ≤ d(x, z) + d(z, C) ≤ 4OPT + 4OPT = 8OPT.
A more careful analysis can show an approximation ratio of 4.
3.4

Coresets

An interesting generalization of the partitioning framework is the composable coreset framework. In this framework the input is still partitioned into X1 , . . . , Xp . However, instead of using the algorithm A twice
as in Algorithm 1, the idea is to use two different algorithms, one on thepartitions and another on the union of the outputs of the first algorithm.
The first algorithm can be thought of as computing a good summary of
the input partition. More formally,
Definition 3.2. An algorithm A′ computes an α-composable coreset if
for any input X and for any partition X1 ∪ · · · ∪ Xp of X, there exists

3.5. Application: k-Center Clustering in Euclidean Space359

an algorithm A such that A(∪pi=1 A′ (Xi )) computes an α-approximationof f (X).
Intuitively this can be useful because in some settings when a local
solution may not contain all the information needed to compute a good
global solution. As an application of this more general framework, wewill obtain an improved algorithm for k-center in Euclidean space.
An interesting variant of the α-composable coreset framework is
the randomized version, in which the input partition is assumed to berandom. Interestingly, there are problems (like submodular maximization and maximum matching) that do not admit a good composable
coreset for an arbitrary input partition, but do admit for a random
input partition.
3.5

Application: k-Center Clustering in Euclidean Space

We consider the k-center problem where the set X of input points isin the Euclidean space Rd . In this setting, assuming d is constant, it ispossible to improve upon the 8-approximation in Theorem 3.3 using thecomposable coreset framework. The main idea is to design an algorithm
A′ that outputs a set of points so that every point x in an input partition
Xi will have a close neighbor in A′ (Xi ).
Toward this goal, on every partition Xi we run the sequential algorithm Seq-KC (Algorithm 2) to obtain centers ci,1 , . . . , ci,k and theirrespective clusters Ci,1 , . . . , Ci,k . For a cluster Ci,j let δi,j be the maximum distance between a point in Ci,j and ci,j . Then for every cluster
Ci,j we construct a δi,j × · · · × δi,j d-dimensional grid centered at ci,j andgiven ϵ > 0, we further partition this grid into 16√ϵ 2d δi,j × · · · × 16√ϵ 2d δi,jd-dimensional sub-grids. Now for every non empty sub-grid the algorithm A′ chooses an arbitrary input point in Xi that falls inside thesub-grid; the output A′ (Xi ) is the set of all the points chosen from Xi .
To prove that the algorithm computes a useful composable coreset
we need to show: (i) Y = ∪i A′ (Xi ) is not too big and (ii) an algorithm
A such that A(Y ) is a good approximation to the Euclidean k-center.
We start with observing the first property, which is easy to see.

360

Partitioning and Coresets

Lemma 3.4. |Y | = O



1
kp
ϵd



, where p is the number of input partitions.

Lemma 3.5. There is an algorithm A such that A(Y ) is a (2 + ϵ)approximation to the k-center of X.
Proof. First note that each δi,j is upper-bounded by 2OPT. Indeed,since Xi ⊂ X, the value of the optimum solution on this partition OPTi
is no larger than OPT and moreover, Seq-KC is a 2-approximation
algorithm. So for every i and every x ∈ Xi d(x, A′ (Xi )) ≤ 4ϵ OPT.
Now consider any point x ∈ X. By construction, it has a point in Y
at distance at most 2ϵ OPT. This implies that there is a solution of costat most OPT + 2ϵ OPT, by the triangle inequality. Then once again
using the Seq-KC on Y , we obtain a (2 + ϵ)-approximation.
As before,
partitions of size n/k and n/k machines with using√ 
1memory O ϵd nk , we can obtain a (2 + ϵ)-approximation in two
rounds.
p

3.6pProblems

1. Generalize the MST algorithm for finding the maximum weight
independent set under a matroid constraint. More formally, consider a matroid of rank k where U is the set of elements and I isa collection of sets that are independent in the matroid. Say thateach element in u ∈ U has a positive weight wu and the weightof set in I is the sum of the weights on the elements in the set.
Give an algorithm that computes the maximum weight set in I
in O(1) MPC rounds.
2. Consider the maximal matching problem. We are given an undirected simple graph G = (V, E). Let n denote the number ofvertices and m the number of edges. For this problem we willassume that m = Θ(n2 ). Thus, the input size is N := Θ(n2 ). The
goal is to select a set of edges S ⊂ E that is a maximal1 matchingin O(1) MPC rounds.
3. Count the number of triangles in a given graph in O(1) rounds.
1
A subset S of edges is a matching if no two edges in S share an end point.
Further, a matching is maximal if there is no matching S ′ such that S ′ ⊇ S.

3.7. Section Notes
3.7

361

Section Notes

Partitioning is a common algorithmic technique and it was used for
MPC for the first time in Karloff et al. (2010). The generalization tocomposable coresets is due to Indyk et al. (2014)
Triangle counting via partitioning for MapReduce was introduced
by Suri and Vassilvitskii (2011), see Park et al. (2014) for an extension
to multiple rounds and Afrati et al. (2012) on a discussion on the sizeof the intermediate computation.
The 2-approximation algorithm for clustering is due to Gonzalez(1985). The (2 + ϵ)-approximation for k-center can be improved to 2
using Sample and Prune; see Section 4.3 and the Notes in Section 4 forfurther improvements.

4
Sample and Prune

In this section, we consider MPC algorithms based on a specific type ofsampling and testing framework. Generally, sampling is a powerful tool
to quickly estimate statistics of large data sets. For instance, uniform
sampling works for simple problems, such as computing the average:choosing a uniform random subset of the input and computing its
average is likely to be a good estimate of the true average. However,for more complex problems, different elements have different influenceon the final solution, and uniform random sampling may miss theseimportant elements and result in a significantly suboptimal solution.
In this section we present a powerful framework that we term sample
and prune. This is an iterative sampling method used to hone in on
important elements in the input, precisely addressing the previous issue.
4.1

Overview

Problems that are amenable in the sample-and-prune framework ask tofind a subset of size at most k from a universe U of size n optimizing agiven objective, subject to some constraints. When parallelism is not
required, these problems can usually be solved to (near-) optimality
by a simple greedy algorithm G. For instance, G may be the greedy362

4.1. Overview

363

algorithm to find a maximal independent set: given a list of vertices,
iteratively add a vertex to the solution as long as it is not adjacent toany of the previously added vertices. Generally, we assume G is a set
function that can be applied to any subset of U and returns a set of size
at most k. Further restrictions on G will be discussed shortly. Recall
that our memory size is Θ̃(M ).
Algorithm 3 Sample-and-prune framework.
Sample-and-PruneG (U )1: R ← U
2: S ← ∅3: while |R| > M do

Sample each element in R independently with probabilityΘ̃(M/|R|) and add it to S
5:Construct a tester TSG : R → {KEEP, PRUNE} using G,
where TSG (e) = PRUNE if and only if G(S) = G(S ∪ {e}).
6:R ← R \ {e ∈ R | TSG (e) = PRUNE}
7: end while
8: return G(R ∪ S)
4:

The framework presented in Algorithm 3 repeatedly samples input
elements to form a subset S, and then uses a tester TSG based on thealgorithm G to discard many of the input elements, thereby reducing
the problem size. More formally, the algorithm maintains the invariant
that R ∪ S contains enough information to find a good solution to
the problem. In particular, it ensures that the optimum solution to
the union of the sample S and the remaining elements R remains agood approximation to the solution to the original input U . The mainalgorithmic challenge in this framework is to design an efficient tester
TSG that satisfies the following two properties: (i) It should not prune
any important elements still remaining in R; and (ii) After each sample,
it should help to prune out a large number of elements.
Before we delve into the analysis of the sample-and-prune framework,
we first discuss how to implement it in MPC by outlining how to runeach of the iteration steps in Algorithm 3. The sampling step can

364

Sample and Prune

be done in parallel if the elements are evenly partitioned across themachines. The samples from the machines can be brought together on
one machine, where the tester TSG can be constructed. The tester isthen communicated to every machine and pruning step can once again
be done in parallel. Each of the above takes one MPC round.
We now proceed with the analysis, beginning with two definitions.
Definition 4.1 (Usefulness). Fix S ⊆ U and a set function G. An elemente ∈ U \ S is useful for S under G if G(S) ̸= G(S ∪ {e}); otherwise, it isuseless.
We also need the following monotonicity property, satisfied by mostgreedy algorithms.
Definition 4.2 (Monotonicity). A set function G is said to be monotone
if for any S ⊆ U , if e is useless for S, then it is useless for any S ′ ⊃ S.
A natural way of constructing a tester TSG satisfying Property (i)is to check for each e ∈ R if e is useful for S, i.e., check G(S) against
G(S ∪ {e}). If e is useless for S, then it can be pruned; TSG (e) returns
PRUNE. Otherwise, TSG (e) returns KEEP.
We first argue the correctness of Algorithm 3.
Lemma 4.1. If G is monotone, the solution G(R ∪ S) returned by
Algorithm 3 is as good as the solution returned by G(U ).
Proof. If an element e is pruned by TSG during an iteration of thealgorithm, then it is useless for S, which by monotonicity of G implies
e is useless for U as well. In other words, no useful element was pruned
and hence G(R ∪ S) = G(U ).
The only remaining thing to show is that at each iteration, a large
number of (useless) elements are pruned. To do this, we first upperbound the size of the family of testers for a monotone G.
G
Lemma 4.2. For any S, |S| > k, we have TSG ≡ TG(S). Hence, the totalknumber of distinct testers is O(n ).

4.1. Overview

365

Proof. Since G is monotone, if e is useless for G(S), then it will be useless for S ⊇ G(S). Therefore, every possible output of G(S) corresponds
to a possibly unique tester. Since G’s output has at most k elements,P
the total number of distinct testers is at most i≤k ni = O(nk ).
We now define what it means for a tester in this family to be good.
Consider an iteration of Algorithm 3 and let R be the remaining set ofelements during the iteration and S be the set of elements sampled so
far.
Definition 4.3 (Good tester). A tester family {TSG }S is good if for all
S ⊆ U it satisfies the following property: TSG (e) = PRUNE ⇐⇒ TSG ≡GTS∪{e}, for all e ∈ U .
In other words, if a tester TSG decides to prune an element e ∈ R,
then it will be functionally identical to that of a tester constructedby adding e to S. At the same time, if TSG decides to keep an elemente ∈ R, then it will differ from the tester constructed by adding e to S,
i.e., e has a material effect on the behavior of the tester.
For simplicity let M = nδ for some constant 0 < δ < 1. In each
iteration, let the sampling probability be 1/(n1−δ ). Then, the numberof samples in each iteration is O(nδ ) in expectation and is O(knδ log n)with probability 1−n−k by a tail bound. We now discuss the effectivenessof the test in pruning out useless elements. Fix an iteration. We wish toargue that a lot of elements are pruned by the tester. By contradiction,
fix a set R that is large, specifically, |R| > 10kn1−δ log n.
Recall that R is the set of elements that were kept (not pruned).
We claim that sampling any element from R would have changed thetester. This follows from the definition of a good tester. Indeed, for all
G
S and e we have TSG (e) = PRUNE ⇐⇒ TSG ≡ TS∪{e}and therefore forGany e′ ∈ R, TSG (e′ ) = KEEP and TSG ̸≡ TS∪{e′ } . Therefore, for a fixed
tester, we conclude that no element from R could have been sampled.
We can bound the probability of having the set R by the probabilityof not sampling every element in R. Missing all elements in R happens
with probability



1−

1
n1−δ

|R|



≤ exp −10kn

1−δlog n ·

1n1−δ

= n−10k .

366

Sample and Prune

Next, we would like to union bound this probability over all possiblenlarge R. Naively done, this will be futile since there are 10kn1−δlog ndifferent R’s. Instead, the key observation is that the total number oftesters is relatively small, i.e., O(nk ) by Lemma 4.2. Thus, using thefact that the tester (and the fixed S) determines R, we can simply apply
a union bound over the number of testers.
This gives the following strategy to solve a problem with sampleand-prune. Find a monotone greedy algorithm G and a corresponding
good tester. If the greedy algorithm returns at most k elements thenthe above analysis bounds the number of rounds.
4.2

Application: Top k Selection

As a starting example to illustrate how the sample-and-prune framework
works, we consider the problem of finding the largest k out of thegiven n elements (say, numbers); this is the top k selection problem.
For simplicity, let us assume every element is distinct. Note that thealgorithm we present is not the most memory-efficient for this problem.
An obvious way of selecting the top k elements is repeatedly choosing
the largest element from the remaining pool; call this greedy algorithm
G. It is easy to see that G is monotone and returns at most k elements.
The tester TS in this case is easily realized based on G: if e is notin the top k elements in S ∪ {e}, then it outputs PRUNE. Indeed, if e is
not in G(S ∪ {e}) then e ∈/ G(S ′ ∪ {e}) for S ′ ⊇ S. Thus, TS is a goodtester. The framework in Section 4.1 ensures the algorithm runs in asmall number of rounds.
We now argue the algorithm returns the optimal solution. We know
the tester will never discard one of the top k elements. Thus, they must
be returned in the end.
4.3

Application: k-Center Clustering

Recall the k-center clustering problem (Problem 3.3.1). We will give a2-approximation solution in this section using sample-and-prune. For
simplicity, we assume that the value of the optimum objective, OPT,
is known to the algorithm. We can always run the algorithm for each4.3. Application: k-Center Clustering

367

guessed value of OPT in parallel, with only a logarithmic factor blowup
in the memory requirements, by sacrificing a constant factor in theapproximation to OPT.
Our algorithm is based on one of the simple 2-approximate sequential
greedy algorithms G that works as follows. Set B = ∅. Fix an orderingof the elements of U . Add the first point in U to B, and remove all
points from U that are within distance 2OPT from B. Repeat this until
U = ∅. Output B as the final solution. To see the algorithm obtains a
2-approximation, it suffices to show that it terminates after selecting at
most k points.
We will build our tester on this greedy algorithm. Let G(S) be theoutput G gives on the sampled input S. Intuitively, we will discard
each point u ∈ U if it is within distance 2OPT from G(S). The only
tricky part is that since the greedy algorithm considers input points inorder, and its output is sensitive to the order the elements are presented.
To handle this, we will construct a canonical ordering on the fly overiterations of the Algorithm 3. Let Si be the points sampled in iterationi ≥ 1 and let Pi be the points pruned in the same iteration.
We will inductively define a canonical ordering of the points. Fora base case let C1 = G(S1 ). Construct a partial order where all points
in C1 come before S1 \ C1 . Inductively, let Ci = G(Si ∪i−1
j=1 Cj ) \ Ci−1
i−1
where G consider points in ∪j=1 Cj first and then considers other pointsof Si in an arbitrary but fixed order. This will ensure G returns ∪i−1
j=1 CjGfirst. The tester TS1 ∪···∪Si in the ith iteration prunes a point if it iswithin distance 2OPT from a point in C1 ∪ · · · ∪ Ci . The canonicalordering of U is C1 , S1 \C1 , P1 , followed by C2 , S2 \C2 , P2 , . . . . Note thatthe tester TSG1 ∪···∪Si is equivalent to running the greedy on the points
C1 ∪ P1 ∪ · · · ∪ Ci−1 ∪ Pi−1 ∪ Ci in the canonical order and pruning apoint if and only if it discards the point.
Under this canonical ordering, G’s monotonicity is immediate: if apoint is within distance 2OPT from X, then it must be within distance
2OPT from X ′ for any X ⊆ X ′ ⊆ U . Next, the algorithm returns
a 2-approximation since points are only discarded if they are within
2OPT of C1 ∪ · · · ∪ Cℓ where ℓ is the last iteration of the algorithm.

368

Sample and Prune

4.4

Application: Monotone Submodular Maximization Subject to a
Cardinality Constraint

We next consider the problem of maximizing a monotone submodular function under a cardinality constraint and provide an almost
1
2 -approximation using a simple threshold greedy algorithm. The input
to this problem is a universe U of n elements and a parameter k. The
goal is to select k elements from U to maximize an objective function
f that is monotone and submodular. To streamline the discussion, we
assume each element in U takes constant memory to store, the submodular function can be stored in constant memory and can be evaluatedon a machine in constant time.
We begin by formally defining the type of objective function.
Definition 4.4 ((Monotone) Submodular function). Let f : 2U → R+ .
Define fA (e) := f (A ∪ {e}) − f (A) to be the marginal increase of fwhen e is added to a set A. The function f is said to be submodular
if for every S ′ ⊆ S ⊆ U and u ∈ U \ S, we have fS ′ (u) ≥ fS (u). A
function f is said to be monotone if S ′ ⊆ S =⇒ f (S ′ ) ≤ f (S).
While there is a natural greedy algorithm that gives a (1 − 1/e)approximation,to illustrate the sample-and-prune technique, we will use
a simpler greedy algorithm G called threshold greedy, which achieves
1
2 -approximation. The algorithm G is based on the following observation.
Lemma 4.3. Let f be a monotone submodular function. If S ={s1 , . . . , st } ⊆ U, t ≤ k is any set such that(i) there is an ordering of elements in S such that for all 0 ≤ i < t,f{s1 ,...,si } (si+1 ) ≥ OPT/(2k) and(ii) if t < k, then fS (u) ≤ OPT/(2k), for all u ∈ U .
Then, f (S) ≥ OPT/2.
Proof. Let OPT be the value of an optimal solution S ∗ and let τ =P
Pk−1′
OPT/(2k). If t = k, then f (S) = k−1
i=0 fSi (si+1 ) ≥i=0 τ = kτ =OPT/2. If t < k, we know that fS′ (u∗ ) ≤ τ , for any element u∗ ∈ S ∗ .

4.5. Section Notes

369

Furthermore, since f is submodular, f (S ∪ S ∗ ) − f (S) ≤ τ · |S ∗ \ S| ≤OPT/2. We havef (S) ≥ f (S ∪ (S ∗ \ S)) −

OPT
OPT
1
≥ OPT −= OPT,
2
2
2

using the monotonicity of f .
This lemma can be used to obtain a greedy algorithm as follows. For
simplicity, as in Section 4.3, we assume that the algorithm knows thevalue of OPT. If S in the lemma statement has k elements, then S is
immediately 12 -approximation since every element in S has a marginal
gain at least OPT/(2k). Otherwise, if every element not in S has amarginal gain of at most OPT/(2k) when added to S, the S is still a 12 approximation. This gives us the greedy algorithm G, which sequentiallyaccepts an element if and only if the element yields a marginal gain of
1
at least 2k
OPT; up to k elements are accepted.
To build the tester using G, we will inductively define an orderingof the elements as in Section 4.3. The tester and the canonical ordering
are constructed on the fly.
We now argue that this is a good tester. Indeed, to see the tester1
is monotone, we just need to check that if fE ′ (e) < 2k
OPT, then1′fE (e) < 2k OPT for any E ⊆ E ⊆ U . This is an immediate consequenceof f ’s submodularity. As observed, the tester is designed to be equivalent
to running the greedy on the elements in the canonical order. Thus, thealgorithm is 12 -approximation by Lemma 4.3. The number of rounds
follows from the general sample-and-prune framework.
4.5

Section Notes

This section is based on work in Kumar et al. (2015), Lattanzi et al.
(2011), and Im and Moseley (2015). Nemhauser et al. (1978) showedthat the natural greedy algorithm gives a (1 − 1/e)-approximation to
the maximization of submodular functions in the sequential setting.
Natural adaptions of the algorithm are asymptotically worse in the
distributed setting; however, the breakthrough results of Ponte Barbosa
et al. (2015) and Ponte Barbosa et al. (2016) showed how randomization
coupled with the greedy algorithm can yield a (1 − 1/e)-approximation.

370

Sample and Prune

This can further be extended to show results when optimizing overvarious constraints such as a knapsack or matroid constraints.
The k-center problem has been considered using partitioning-based
techniques in Malkomes et al. (2015) and Ceccarello et al. (2019).

5
Dynamic Programming

Dynamic programming (DP) is a powerful algorithm design techniqueand is part of the basic toolkit. DP typically consists of the following
steps: (i) identifying subproblems, (ii) finding the right relationshipbetween them, often in the form of a recurrence, and (iii) implementing
the recurrence efficiently by reusing results from previous computations.
A vanilla DP implementation that closely follows the recurrence isusually sequential, making it less appealing for the MPC model. In thissection we study a framework to implement some DP algorithms in the
MPC model. A central difficulty in defining such a framework is thatthe recurrences are often problem-dependent, making it harder to finda generic method. Nevertheless, we identify key properties that enable
the existence of such framework in a principled way.
In particular, we use a framework that adapts a class of dynamic
programs to the MPC model in a polylogarithmic number of rounds.
While the resulting algorithms are not the best possible in terms of thenumber of rounds, this approach serves to illustrate the main ideas.

371

372
5.1

Dynamic Programming
Overview

To introduce the framework we start by identifying key properties thatallow for implementation in the MPC framework using a polylogarithmic
number of rounds. These properties can be rather rigid, and we later
discuss how to relax them via approximation; in particular we willshow how to use approximate dynamic programs to obtain efficientalgorithms.
Let us begin by defining some additional notation. Let x1 , . . . , xn be
the input; we assume that the input is ordered a priori. Now consider adynamic program recurrence D(i, v), where the first entry i is the index
of the input element and the second entry v ∈ V is a value; here V isthe set of possible values. It is intuitive to think of v as a integer, but
in some applications it could be a vector.
We now define two properties for D(·, ·) that will allow us to implement it efficiently in MPC.
Memory efficiency: Each entry of D(i, v) should be take up polylogarithmic memory and can contain one of at most a polylogarithmic
number of possible v values.
Bounded dependencies: Consider any two consecutive non-empty
intervals I1 and I2 of the input such that I1 = [j, k] and I2 = [k + 1, ℓ]with 0 ≤ j < k < ℓ ≤ n. Let D1 (·, ·) denote the optimal entries of the
dynamic program if the entire input only consisted of I1 . Similarly let
D2 (·, ·) denote the optimal entries of the dynamic program if the entire
input only consisted of I2 . Suppose that we would like to compute theoptimal entries of D1∪2 (·, ·) corresponding to the interval [j, ℓ], i.e., theconcatenation of I1 and I2 . Then it should hold that: (i) For any i ∈ I1 ,for any v ∈ V , D1∪2 (i, v) can be computed using the entry D1 (i, v), a
polylogarithmic number of entries from D2 , |I1 |, and |I2 |. We will let
S1,2 (i, v) be the set of entries from D2 needed to compute D1∪2 (i, v).
When the intervals I1 and I2 are clear in the context we may drop thesubscripts 1, 2 and 1 ∪ 2. (ii) The set S1,2 (i, v) can be obtained using
only D1 (i, v), |I1 |, and |I2 |.
The two properties guarantee that we can efficiently compute D(·, ·)in MPC. We will formalize this next.

5.1. Overview
5.1.1

373

Round Efficiency

We now show how to compute D(·, ·) in logarithmic number of rounds,
using the properties of memory efficiency and bounded dependencies.
We start by partitioning the input x1 , . . . , xn across the machines,
respecting the ordering. Let X[k] denote the interval (i.e., subset) ofindices of inputs stored on machine k. Each machine k computes D(i, v)
for each v and for each i ∈ X[k].
Next machines start to communicate to each other to compute theoptimal D(·, ·) for larger input sizes. Before describing the algorithm
we introduce some additional notation. Let X[k1 , k2 ] = ∪k∈[k1 ,k2 ] X[k],where k1 < k2 . For brevity, let Xi [k1 , k2 ] := X[k1 + k(i), k2 + k(i)] wherek(i) is the first index of the machine storing input xi . The computation
occurs in iterations. In iteration ℓ, each machine computes D(i, v) for
element xi in the machine, assuming that the only indices are Xi [0, 2ℓ ],we denote this quantity as Dℓ (i, v).
To proceed, assume Dℓ−1 (i, v) has been computed considering theindices in Xi [0, 2ℓ−1 ] and the goal now is for machine k(i) to compute Dℓ (i, v) considering the indices in Xi [0, 2ℓ ]. By assumption of thebounded dependencies property, there is a set S(i, v) of entries that canbe computed only using Dℓ−1 (i, v). If the entries in S(i, v) are known,
then Dℓ (i, v) can be optimally computed.
To do this, a fixed machine will have a collection of sets S(i, v) ofentries for each element xi stored on the machine. Using these sets, in one
round the algorithm collects the entries corresponding to S(i, v) stored
on other machines. In a second round, these machine communicate theentries back. Using them, the Dℓ (i, v)’s can be computed.
First we show that Algorithm 4 can be realized in the MPC model.
The correctness of the algorithm directly follows from the assumptions.
Lemma 5.1. Algorithm 4 can be implemented in the MPC model withnm machines in O(log m) rounds using Õ( m|V |) memory per machine,nwhere each machine communicates Õ( m |V |) bits per iteration.
Proof. Note that each machine stores O(n/m) inputs and thus storing
the D(i, v)’s for each v ∈ V and each i that is local to the machine
takes at most polylogarithmic memory by memory efficiency property.

374

Dynamic Programming

Algorithm 4 Dynamic Program
1: Each machine k computes D(i, v) for all v ∈ V using only its subset

X[k] of the inputs
2: D0 (i, v) ← D(i, v)
3: for ℓ = 0, 1, . . . , log m do
4:
{Do the following in parallel}5:
for each input index i on machine k and value v ∈ V do
6:
Compute S(i, v) from Dℓ (i, v)
Fetch Dℓ (i′ , v ′ ) for all (i′ , v ′ ) ∈ S(i, v) by requesting from the7:respective machines
8:{This is done for all i on machine k simultaneously}
9:
Compute Dℓ+1 (i, v) using Dℓ (i′ , v ′ ) for all (i′ , v ′ ) ∈ S(i, v)
10:
end for
11: end for
12: return Dlog m (·, ·)For each iteration ℓ, a machine requests entries S(i, v) for all i on
the machine, where by the bounded dependencies property, |S(i, v)| ispolylogarithmic.
The proof is complete by observing that each iteration can be donein constant number of rounds and there are O(log m) iterations.
5.2

Warm-up: Knapsack

We first consider the knapsack problem to illustrate the framework.
This problem is significantly easier than the interval selection problem
we will subsequently discuss but it will serve as a warm-up example.
In the knapsack problem, we are given n items where each itemi ∈ [n] has size si and weight wi . The goal is to maximize the total
weight of items packed into a knapsack of capacity S. This problem
is weakly NP-hard and there exist algorithms whose running time isPpolynomial in S and n, or in i wi and n. For any subset X ⊆ [n], letPPw(X) := i∈X wi and s(X) := i∈X si . Also let W := w([n]), which we
assume is polynomial in n for simplicity. Recall the following sequential
dynamic program where we compute D(i, v) := minX⊆[i]:w(X)≥v s(X). In

5.2. Warm-up: Knapsack375

words, D(i, v) refers to the smallest memory one has to use to achieve
weight v by choosing some items from the subset [i]. The following
recurrence is elementary:D(i, v) :=min{D(i − 1, v), wi + D(i − 1, max{v − wi , 0})}0i ∈ [n], v ∈ [W ]i = 0 or v = 0

For simplicity suppose the items are stored in the following manner:the first n/m items are in machine 1, the next n/m items are in machine
2, and so forth.
The first issue in simulating the dynamic program in MPC is that
there are too many entries to compute. Hence, we will compress themby only considering weight values v that are powers of 1 + ϵ, which will
incur a (1 + ϵ)-factor loss in the approximation ratio; let V be the set ofweights considered. The second issue is that each machine stores only
n/m items and a naive implementation would need n/m rounds.
To fix the second issue, we will have to use parallelization moreaggressively. To this end, we define an extended notion of subproblems. For simplicity of notation, assume that every machine has
only one item, i.e., m = n; removing this assumption is straightforward. Machine i will be responsible for computing {D(i, v)}v∈V . LetDℓ (i, v) := minX⊆[i]\[i−2ℓ ]:w(X)≥v s(X); we let [i − 2ℓ ] = ∅ if i ≤ 2ℓ . In
words, Dℓ (i, v) is a local version of D(i, v) where it only pretends that
there are items i − 2ℓ + 1, . . . i. Clearly we have D(i, v) = Dlog n (i, v).
Thus, to obtain an O(log n) round algorithm, it suffices to show how
machine i can compute Dℓ (i, v) in round ℓ, assuming that Dℓ−1 (·, ·) has
already been computed:Dℓ (i, v) =min

v1 ,v2 ∈V :v1 +v2 ≈v

Dℓ−1 (i − 2ℓ−1 , v1 ) + Dℓ−1 (i, v2 ).

(5.1)

Here, v1 + v2 ≈ v implies an approximate equality within a factorof 1 + ϵ, i.e., v/(1 + ϵ) < v1 + v2 ≤ v. Eqn. (5.1) can be easily shownby first assuming that v1 and v2 can take any integer value up to W
and lowering their value as little as possible to ensure v1 , v2 ∈ V . Thisapproximation incurs a (1 + ϵ)-factor loss in the value we obtain in
every iteration, thus (1 + ϵ)log n -factor in total. Therefore to obtain a(1 + ϵ)-approximation we scale down ϵ by a factor of log n. Thus, wewill have |V | = O( 1ϵ log W ) = O( 1ϵ log n).

376

Dynamic Programming

Note that this can be efficiently simulated in MPC because machine
i can compute its own entries {Dℓ (i, v)}v∈V by accessing only theO( 1ϵ log n) entries stored on machine i − 2ℓ−1 (and itself).
5.3

Interval Selection in MPC

In this section, we show how interval selection fits into the MPC framework using Algorithm 4. For this problem we will introduce an approximate dynamic program. Later we will abstract out the approximate
dynamic programming piece and discuss general guidelines for developing an approximate dynamic program in Section 5.4.
In the interval selection problem, there is a collection of intervals
x1 , . . . , xn where the ith interval xi is [si , ei ] with weight wi . We assume
intervals are ordered by their ending time. The goal is to select a subset
of intervals of maximum total weight that do not intersect. To solve thisproblem, we consider the following dynamic program. Let B(i, j) = v
Pfor some value v ∈ [1, i∈[n] wi ] denote the optimal objective if the
input instance only contains intervals xi , . . . xj .
Unfortunately, the dynamic program B(i, j) satisfies neither the
memory efficiency property nor the bounded dependency property. The
key idea is to transform this dynamic program into another with theseproperties.
The first idea is to “swap” the value v with the index j. Define a newrecurrence C(i, v) := min{j | B(i, j) = v}. That is, C(i, v) is the leastindex j such that there is a solution to the sub-instance {xi , . . . , xj }with value at least v. Define C(i, v) = ∞ if {j | B(i, j) = v} = ∅.
We can compute C(i, v) using the following recurrence. For the basecase, we have C(i, 0) = i and C(n, v) = ∞ for all v. Inductively, forv > 0 we have:C(i, v) = min {j2 | v1 + v2 = v, j1 = C(i, v1 ), j2 = C(j1 , v2 )}. (5.2)
v1 ,v2 ≥0

Intuitively, we guess a “split” of v into v1 and v2 and concatenate
solutions corresponding to picking up value at least v1 and value atleast v2 . If we compute C(i, v) for all v, then this suffices to computeB(i, j) for all j.

5.3. Interval Selection in MPC

377

Note that C(·, ·) still does not satisfy the memory efficiency andbounded dependencies properties. Interestingly we can relax it using
approximation to solve this issue.
5.3.1

Approximate DP for Interval Selection

We now show how to approximate C(i, v) using less memory. The key
idea is to “sketch” the values. Specifically we want to compute therecurrence only for v’s of the form ρk for some non-negative integer k,where ρ := (1 + ϵ/t) and t is a parameter to be chosen later. Note thatsince B(1, n) is poly(n), we only need to consider integer exponentsk ∈ O( ϵt log n); let V := {ρk } be the set of values considered.
Let C ′ (i, v) be the approximation of C(i, v) where i ∈ [n] and v ∈ V .
Note that C ′ (·, ·) has only O( ϵt n log n) entries and can be computed as
C ′ (i, v) = min {j2 | v/ρ ≤ v1 + v2 ≤ v · ρ, j1 = C ′ (i, v1 ), j2 = C ′ (j1 , v2 )} .
v1 ,v2 ∈V(5.3)

Note that we lose a factor of ρ = 1 + ϵ/t in tracking the weights
each time we apply this recurrence. If we think of this recursive computation as a tree, by choosing t to be its depth, we can still ensure an
approximation of ρt = 1 + O(ϵ). Key is that the dynamic programming
framework given for the MPC setting ensures the depth is at most log n.
Notice this does not depend on the values of the weights, but rather
the total number of intervals.
Lemma 5.2. The recurrence C ′ (·, ·) satisfies the memory efficiency andbounded dependency properties.
Proof. We can assume that the weights are polynomial sized by sacrificing an arbitrarily small factory in the optimal value. For this reason, therecurrence is memory efficient as we need only consider a logarithmic
number of entries ρk in V for k ∈ [O(log n)].
Now we consider the bounded dependency property. Consider any
two substrings I1 and I2 of ordering such that I1 = [j, k] and I2 =[k + 1, ℓ] with 0 ≤ j < k < ℓ ≤ n. Let C1′ (i, v) be the recurrence in (5.3)
computed on I1 and similarly C2′ (i, j) on I2 . Let C1∪2 be the recurrence
for I1 ∪I2 . We can compute C1∪2 (i, v) as follows from C1 (·, ·) and C2 (·, ·).

378

Dynamic ProgrammingFirst C1∪2 (i, v) = C2 (i, v) for all i ∈ I2 . Next consider an i ∈ I1 . If
C(i, v) ̸= ∞ we have C1∪2 (i, v) = C1 (i, v). Otherwise we compute thisas the following.
′
C1∪2(i, v) = min(5.4){j2 | v/ρ ≤ v1 + v2 ≤ v · ρ, C1′ (i, v1 ) ̸= ∞, j2 = C2′ (x2 , v2 )(5.5)

v1 ,v2 ∈V

where x2 is the first element in I2 larger than C1′ (i, v1 )}.
In this recurrence we need only consider |V | many entries fromC2 (·, ·) for each i, v1 pair. This is because there are V entries and eachone has exactly one corresponding value v2 . The required indices (x2 , v2 )can be directly computed from C1 (i, v1 ). Thus, we have the bounded
dependency property.
This lemma along with Lemma 5.1 shows that the C ′ (·, ·) can becomputed in MPC. In the next section, we bound guarantees on thequality of the solution returned by C ′ (·, ·).
5.3.2

Approximation Guarantees for Interval Selection

The next lemma bounds the final guarantee of computing C ′ (·) using
Algorithm 4. The key is that in each recursive step a (1 + ϵ/t) factor canbe lost in the objective value. However, we know that the longest chainof dependencies in the dynamic programming computation is at mostO(log n). This follows from Algorithm 4 running in O(log n) rounds andonly on such dependency is added for any entry in each iteration.
Lemma 5.3. Computing C using Algorithm 4 returns a (1 − O(ϵ))approximation to B(1, n).
Proof. We show the following stronger claim: For an input xi andvalue v ∗ ∈ V , let Cℓ (i, v ∗ ) be the value of C(i, v ∗ ) pretending that weonly have the intervals in Xi [1, 2ℓ ]. Then, there exists v ∈ V such thatv > v ∗ /ρℓ and Cℓ′ (1, v) ≤ Cℓ (1, v ∗ ). Note that this claim would complete
the proof as the value of the solution given by the subproblems Cℓ′ (i, v)
corresponds to the largest v ∈ V such that Cℓ′ (i, v) < ∞.

5.4. Approximate Dynamic Programs379

We prove the claim by induction on ℓ. The base case for ℓ = 0 isclear since we set C0′ (i, v) = C(i, v) using only the intervals stored inmachine k.
To show the inductive step, fix an iteration ℓ ≥ 1, interval i, and value∗v ∈ V . Consider the set S of inputs achieving v ∗ , i.e., S ⊆ Xi [1, 2ℓ ] andthe total value of the inputs in S is v ∗ . Note that if S is fully contained inXi [1, 2ℓ−1 ] or in Xi [2ℓ−1 + 1, 2ℓ ] we are done by the induction hypothesis.
Otherwise, let Xj1∗ be the largest index input in S ∩ Xi [1, 2ℓ−1 ]. Let
v1∗ , v2∗ be such that j1∗ = Cℓ−1 (i, v1∗ ), j2∗ = Cℓ−1 (j1∗ , v2∗ ), and v ∗ = v1∗ + v2∗ .
Note that v2∗ can be computed from the intervals in Xi [2ℓ−1 + 1, 2ℓ ].
By the induction hypothesis, there exist v1 , v2 ∈ V with v1 > v1∗ /ρℓ−1
and v2 > v2∗ /ρℓ−1 such that′′Cℓ−1
(i, v1 ) ≤ Cℓ−1 (i, v1∗ ) and Cℓ−1
(j1 , v2 ) ≤ Cℓ−1 (j1 , v2∗ ),′ (i, v ); if X ∈ X [1, 2ℓ−1 ], then let I be the smallest
where j1 = Cℓ−1
1
j1
i
j1
index input in Xi [2ℓ−1 + 1, 2ℓ ]. Due to the way the algorithm is defined,
we have Cℓ′ (i, v) ≤ Cℓ−1 (j1 , v2∗ ), where v ∈ V such that v > (v1 +v2 )/ρ >′ (i, v ) ≤ C ′ (i, v ∗ ) = j ∗ and(v1∗ + v2∗ )/ρℓ = v ∗ /ρℓ . Note that j1 = Cℓ−1
1
2
1
ℓ−1
both inputs Xj1 and Xj1∗ are in Xi [2ℓ−1 + 1, 2ℓ ]. Further, recall that v2∗
is computed from the inputs in Xi [2ℓ−1 + 1, 2ℓ ]. Thus, by definition of′ , we have C
∗
∗ ∗
Cℓ−1
ℓ−1 (j1 , v2 ) ≤ Cℓ−1 (j1 , v2 ), which immediately implies
Cℓ′ (i, v) ≤ Cℓ−1 (j1∗ , v2∗ ) = Cℓ (i, v ∗ ), as desired.

The above lemmas imply the following result, setting t = Ω(log n).
Theorem 5.4. There is an MPC algorithm to compute a (1 − ϵ)approximate solution to interval selection. The algorithm uses Õ(n/m)
memory per machine and runs in O(log n) rounds.
5.4

Approximate Dynamic Programs

Many natural dynamic programs will not satisfy the bounded dependency property or memory efficiency. However, often it is possible totransform a dynamic program D(i, v) for i ∈ [n] and v ∈ V into an alternative dynamic program C(i, v) for v ∈ VC where VC is much smallerthat V so that C(i, v) satisfies the bounded dependency and memory

380

Dynamic Programming

efficiency properties. The trade-off is that C(i, v) is sub-optimal, but isan approximate solution.
An example of this was given in the prior section. In this section, wegive general guidelines for reducing the dependencies via approximation.
Approximation via Sketching: Consider a recurrence D(i, v) wherev ∈ V corresponds to the objective value. Say that there is a corresponding recurrence C(i, v) where v ∈ VC such that VC ⊆ V and VC has
poly-logarithmic size so that C(·, ·) satisfies memory efficiency. Further,assume that C has a corresponding recurrence satisfies the bounded
efficiency property.
The recurrence C need not be an exact dynamic program. Rather, thekey is the following. Say that we compute C using Algorithm 4. Further,say that in each recursive computation of C, at most a (1 + ϵ/t) factor
is lost for any 0 < ϵ < 1 and integer t. Then by setting t = Ω(log n),
the proof in Lemma 5.3 can be extended to show that C(·, ·) is a
(1 + ϵ)-approximation for the overall problem.
Using such a framework it is possible to obtain (1+ϵ)-approximation1
algorithms using O( ϵδ) rounds of MPC with O(n) total memory andδ
O(n ) memory per machine for constants ϵ, δ > 0 for the problems ofweighted interval selection, optimal binary search tree, and the longest
increasing subsequence.
5.5

Section Notes

The framework described in this section is due to Im et al. (2017).

6
Round Reduction via Sampling

In this section we develop a family of techniques to reduce the numberof rounds of MPC algorithms when working with large graphs.
The key idea is to identify properties (e.g., vertex degree) that are
well preserved when working with a random subset of the data. As
our primary focus is on graphs, such a random subset can be obtainedby sampling either edges or vertices; these two approaches leads totwo different guarantees. As a case study, we will consider the k-coredecomposition problem but the same technique can be applied to several
classical problems such as matching and maximum independent set.
The k-core problem can be solved sequentially by a simple iterative
sequential algorithm. In this section we will show how to use edge
sampling to modify this algorithm to obtain an O(log n)-round algorithm
that uses near-linear memory per machine. We will then extend theanalysis via vertex partitioning to get an O(log log n)-round algorithm
that also uses near-linear memory.
6.1

k-core Decomposition and a Sequential Algorithm

A wide range of data mining, machine learning, and social network analysis problems can be solved by identifying dense regions in large graphs
381

382

Round Reduction via Sampling

and understanding the role of vertices in a density-based hierarchicaldecomposition of the graph. A commonly used technique for this task is
the k-core decomposition: the k-core of a graph is a maximal subgraphwhere every vertex has induced degree at least k.
Formally, let G = (V, E) be a graph with |V | = n vertices and|E| = m edges. For a vertex v ∈ G we denote by d(v) the degree ofthe vertex in G. If H is an induced subgraph of G, for any vertexv ∈ H we denote by dH (v) the degree of v in H. A k-core is a maximal
subgraph H ⊆ G such that ∀v ∈ H we have dH (v) ≥ k. For any k the
k-core is unique and possibly disconnected. We say that a vertex v has
coreness number k if it belongs to the k-core but not to the (k + 1)-core.
We denote the coreness number of vertex v in the graph G by CG (v);we may drop the subscript notation when the graph is clear from thecontext. We let V≥t := {v ∈ V | CG (v) ≥ t} denote the set of vertices
with coreness number at least t in the original graph G. We define V≤tsimilarly.
We also define the core-labeling for a graph G as the labeling where
every vertex v is labeled with its coreness number. It is worth notingthat this labeling is unique and that it defines a natural hierarchicaldecomposition of G as shown in Figure 6.1. In the sequential setting asimple iterative greedy algorithm computes the k-core decomposition
efficiently. In Algorithm 5 we provide the pseudocode for it.

Figure 6.1: Hierarchical decomposition induced by the coreness numbers.

6.2. Parallelizing the Sequential Algorithm: O(log n) Rounds

383

Algorithm 5 Sequential k-core algorithm.
1: Input: G = (V, E)
2: Output: Coreness numbers {CG (v)}v∈V
3: VH ← V
4: for ℓ ← 0 to n do
5:
Repeatedly remove any v with dH (v) = ℓ from VH and set CG (v) ← ℓ
6: end for

6.2

Parallelizing the Sequential Algorithm: O(log n) Rounds

It is easy to construct a graph for which the sequential algorithm cantake Ω(n) iterations to label all vertices. In this section we present a
simple technique to obtain an MPC algorithm that only uses O(log n)rounds and almost linear memory to solve the problem approximately.
The first step toward this goal is to define relaxed notions of k-coredecomposition and coreness number. We define an (1−ϵ)-approximate kcore of G to be a subgraph H that (i) H contains the k-core of G and (ii)∀v ∈ H, dH (v) ≥ (1 − ϵ)k. In other words, a (1 − ϵ)-approximate k-coreof G is a subgraph of the ((1 − ϵ)k)-core of G and a supergraph of the
k-core of G. In Figure 6.2 we illustrate the 3-core and a 2/3-approximate
3-core for a small graph.

Figure 6.2: Example of 3-core and 2/3-approximate 3-core.

Similarly, in a (1 − ϵ)-approximate core-labeling of a graph G, eachvertex is labeled with a number between its coreness number and its
1
coreness number multiplied by 1−ϵ.
The main intuition behind our MPC algorithm is to compute coreness numbers in decreasing order by grouping them in O(log n) buckets
and solving the problem for each bucket in O(1) rounds. In particular

384

Round Reduction via Samplingfor decreasing i, vertices with coreness numbers in the range (2i−1 , 2i ]are processed, and all the edges whose both endpoints have corenessvalue larger than 2i are ignored as they will already be labeled. The
remaining edges are sampled with probability Θ̃(2−i ), which reduces
the maximum coreness value in the remaining graph to Õ(1). Here, only
the vertices whose degrees are considerably larger than 2i−1 still haveincident sampled edges and can be labeled approximately. The reason
starting from the bucket with the largest coreness numbers is because
to fit the sampled edges into a single machine we have do significantly
down sample edges, so only high-degree vertices are distinguishable
after sampling.
The following pseudocode shows the O(log n)-round MPC algorithm.
Algorithm 6 Approximate coreness for all vertices.
1: Input: G = (V, E) and an approximation parameter ϵ2: Output: Approximate coreness number {C˜G (v)}v∈V
3: Γ0 ← ∅4: for i ← 1 to log1+ϵ n do
5:
Find Γi ⊆ V s.t. (i) Γi ⊇ V≥(1−ϵ)i−1 n and (ii) Γi ∩ V≤(1−ϵ)i n = ∅6:C˜G (v) ← (1 − ϵ)i−1 n for all v ∈ Γi \ Γi−1
7: end for
Recall that V≥t denote the set of vertices with coreness number at
least t in the original graph G. We label an unlabeled vertex v if its
coreness number is too big for the iteration, i.e., CG (v) ≥ (1 − ϵ)i−1 ;conversely, if a vertex’s coreness number is too small, we defer its
labeling to subsequent iterations. We have the freedom to handle theother vertices either way. It is immediate that this algorithm yields(1 − 2ϵ)-approximate1 coreness numbers in O( 1ϵ log n) iterations.
It remains to show how to compute Γi in O(1) rounds given Γi−1that satisfies the properties (i) and (ii). Towards this goal, we use
the following memory-efficient algorithm based on edge sampling. It
is essentially combining Algorithm 5 with edge sparsification. In thefollowing note that H is different from the subgraph induced on V \Γi−1 .
1More precisely, (1 − ϵ)2 -approximate.

6.2. Parallelizing the Sequential Algorithm: O(log n) Rounds

385

Algorithm 7 Computing Γi , given Γi−1 satisfying (i) and (ii)log n
1: k ← n(1 − ϵ)i−1 and p ← min{1, 50kϵ}2
2: EH ← edges sampled in parallel independently from E \ E[Γi−1 ] withprobability p, where E[Γi−1 ] is the edges with both end points in Γi−1

3: Let H = (VH ← V, EH )4: Repeatedly remove vertices v from VH such that dH (v) < (1 − ϵ/2)pk
5: Γi ← VH

Lemma 6.1. Given Γi−1 , Algorithm 7 correctly computes Γi , w.h.p.
nProof. We assume that p < 1, and consequently 50 log< 1, as otherkϵ2wise H equals G for the unlabeled vertices and the lemma immediatelynfollows. Observe that this assumption also implies k > 50 log, whichϵ2will be important for showing that our bounds hold w.h.p.
We first show V≥k ⊆ Γi . By definition of coreness, each v ∈ V≥k has
at least k neighbors in V≥k . For any u ∈ V≥k , we thus have E[dH0 (u)] ≥n, where H0 is the subgraph H right after the sampling before
pk ≥ 50 log
ϵ2
no vertices are removed. Then, by a Chernoff bound, with probability
at least 1 − n−4 , dH0 (u) ≥ (1 − ϵ/2)pk. By a union bound, this holds
for all vertices with probability at least 1 − n−3 . Therefore, Algorithm 7
never removes vertices from V≥k , meaning V≥k ⊆ Γi .
We next show Γi ∩V≤(1−ϵ)k = ∅. For each v ∈ V≤(1−ϵ)k , let Ev denotethe set of edges incident to v in the k ′ -core of G where k ′ = CG (v).
In other words, Ev is the set of witness edges that certify that v has
coreness number k ′ . By definition of V≤(1−ϵ)k , |Ev | ≤ (1 − ϵ)k. It thenfollows that |Ev ∩ H0 | ≤ (1 − ϵ/2)pk for all v ∈ V≤(1−ϵ)k w.h.p. Thus,
all vertices in V≤(1−ϵ)k are removed from VH .

Finally we argue that the algorithm can be realized using Õ(n) memory per machine. This follows from the following simple observations.
Lemma 6.2. For any k, the number of edges incident to V≤k is at mostk|V≤k |.
Lemma 6.3. The number of edges sampled is O( ϵ12 n log n) w.h.p.

386
6.3

Round Reduction via Sampling
Round Compression
O(log log n) Rounds

via

RandomVertexPartitioning:

In this section we show how to exponentially reduce the number ofrounds used by the algorithm in the previous section. The main idea,
instead of sampling the edges independently, is to randomly partition
the vertices among different machines and analyze the induced subgraphin parallel. This “round compression” idea enables to simulate multiple
rounds of the MPC algorithm in much fewer number of rounds.
Partitioning the vertices across 1/p machines uniformly at random isequivalent, from each machine’s point of view, to sampling each vertex
with probability 1/p. The main advantage of vertex sampling over edge
sampling, which was used in Section 6.2, is the following. A vertex oforiginal degree d has an expected degree of pd after both edge sampling
and vertex sampling (conditioned on it being sampled in case of vertex
sampling). However, the resulting graph size is very different: the graphhas mp edges in expectation after edge sampling but only mp2 edges in
expectation after vertex sampling. See Figure 6.3.

Figure 6.3: Difference between vertex sampling and edge sampling with p = 12 .

In Algorithm 6, we first sampled edges with probability Θ̃(1/n)(hiding logarithmic terms and setting ϵ = 1/2) to identify high-degree
vertices of degree in [n/2, n]. If the graph is dense, the resulting graph6.3. Round Compression via Random Vertex Partitioning

387

could have Θ(n) edges, which would barely fit in a single machine ofmemory Θ̃(n). This was the main bottleneck to parallelization. That is,
identifying lower degree vertices requires more aggressive sampling. For√
example, to identify vertices of degree about n, we have to sample√
edges with probability p = Θ(1/ n). But the sampled edges can be as
many as mp = Ω(n1.5 ) (for dense graphs). In contrast, vertex samplingwith the same probability yields a subgraph of size mp2 = O(n). Thus,√
we can handle all degrees and eventually coreness numbers in [ n, n]
in O(1) rounds. By subsequently handling vertices of degree [n1/4 , n1/2 ][n1/8 , n1/4 ], . . . , we will arrive at O(log log n) rounds.
The following pseudocode is presented to formally describes thehigh-level flow, which is a natural generalization of Algorithm 6. The
definition of Γi remains unchanged.
Algorithm 8 Approximate coreness via round compression.
1: Input: G = (V, E) and an approximation parameter ϵ2: Output: Approximate coreness number {C̃G (v)}v∈V
3: Γ0 ← ∅4: for i ← 1 to O(log log n) do
i−1
5:k ← n1/2√
6:
for all j such that (1 − ϵ)j n ∈ [ k, k] do
7:Find Γj ⊆ V satisfying (i) and (ii) described in Algorithm 6
8:
CG (v) ← (1 − ϵ)j−1 n for all v ∈ Γj \ Γj−1
9:
end for
10: end for
To obtain an O(log log n)-round algorithm, we would like to execute
each iteration of the outer for loop in constant number of rounds.
Formally, we show the following.
Lemma 6.4. Given a set Γ such that V≥k ⊆ Γ and V≤(1−ϵ)k ∩ Γ = ∅,we can compute in O(1) rounds Γj such that V≥(1−ϵ)j−1 n ⊆ Γj and√V≤(1−ϵ)j n ∩ Γj = ∅, for all for j such that (1 − ϵ)j n ∈ [ k, k].
The proof is almost as for Lemma 6.1.
Intuitively, this can be done in parallel because the same Γ is used
for all such j. The following procedure adapts Algorithm 7 to use vertex
sampling. It outlines how to compute each Γj .

388

Round Reduction via Sampling√
Algorithm 9 Computing Γi for each j s.t. (1 − ϵ)j−1 n ∈ [ k, k] givenΓ.
n
1: k ′ ← (1 − ϵ)j−1 n and p ← 50klog′ ϵ2
2: Assign each vertex V \ Γ uniformly at random among p1 machines
3: for each machine do4:
Let H = (VH , EH ) be the induced subgraph on the vertices assigned tothe machine

5:
Repeatedly remove vertices v from VH such that dH (v) < (1 − ϵ/2)pk ′6:
Γj ← VH
7: end forLemma 6.5. The induced graphs Hi have O(n log2 n/ϵ4 ) edges w.h.p.
√
Proof. Consider a fixed machine and consider k ′ = k, which resultsin the highest sampling probability. Then, the fixed machine has an edge
2nafter the partitioning with probability p2 = Θ( log). Observation 6.2
kϵ4
implies that there are at most kn edges in E[V \ Γ]. Thus, the machine2nis assigned O( log)kn edges in expectation. An appropriate use of thekϵ4
Chernoff bounds completes the proof.
6.4

Section Notes

The content of this section is mainly based on Esfandiari et al. (2018)
and Ghaffari et al. (2019b) The O(log n)-round algorithm presented inthis section is inspired by the filtering technique from Section 4 and was
first presented in Esfandiari et al. (2018). The use of round compression
to efficiently estimate the coreness number was introduced in Ghaffari
et al. (2019b).
Round compression has found many uses in the MPC model. The
technique was first introduced by Czumaj et al. (2018), who obtainthe first algorithm for matching that runs in sub-logarithmic numberof rounds and uses near-linear memory. Their result has then been
improved in a series of follow-up (Behnezhad et al., 2019b; Ghaffari
et al., 2018; Assadi et al., 2019a), leading to the current best result of a
(1 + ϵ)-approximate matching in O(log log n) rounds. These techniques
have been used in related problems such as computing independent sets

6.4. Section Notes

389(Ghaffari et al., 2018), vertex cover (Assadi et al., 2019a), and graphcoloring (Chang et al., 2019).

7
Round Reduction via Graph Exponentiation

In this section we introduce a new technique called graph exponentiationthat improves the running time of MPC graph algorithms when memory
per machine is strongly sublinear in the number of vertices. The mainidea behind graph exponentiation is that if the decision of an algorithm
for a vertex v in round i only depends on v’s ith neighborhood1 , thenwe can simulate multiple rounds in parallel by loading the extended
neighborhood for every vertex. Here is an example.
Suppose that an algorithm runs in O(log n) rounds and all the choicesof the algorithm for every vertex in round i only depend on its ith√neighborhood. Furthermore, suppose that an O( log n)-neighborhoodof every single vertex can fit on a machine. Then one could split the√O(log n) rounds of the algorithm in O( log n) phases, each consisting√√of O( log n) rounds, and simulate the O( log n) rounds in a single√
round by aggregating the O( log n) neighborhood of each vertex into√a single machine. It is possible to collect the O( log n) neighborhoodof each vertex using only O(log log n) rounds (by iteratively sending,in step j, the 2j−1 -neighborhood to all of the 2j−1 th neighbors). In
1

The ith neighborhood of vertex v is defined as the set of vertices that arereachable from v by traversing at most i edges.

390

7.1. Approximate Core Decomposition

391√
this way one would obtain an MPC algorithm using Õ( log n) rounds.
√
Unfortunately in many cases the O( log n)-neighborhood does not fit
effortlessly in a single machine; hence, this technique is often combinedwith sampling and other problem-specific ideas. Figure 7.1 illustrates
graph exponentiation.

Figure 7.1: Visual representation√ of the graph√exponentiation technique. A

T -round algorithm is divided in T phases of T rounds that are executed
locally. In the figure, T = 4. To load the 4-neighborhood efficiently for every
vertex in step j every vertex sends its 2j−1 neighbors to all its 2j−1 th neighbors.
The vertices v receive in this doubling process in the first and second steps
are colored orange and red, respectively.

We apply graph exponentiation approach to two problems, finding
approximate core decomposition and finding connected components.
7.1

Approximate Core Decomposition

In Section 6 we presented efficient algorithms for approximate k-coredecomposition that used memory per machine that is almost linear in
the number of vertices of the graph. In this section we focus on the morechallenging setting where machines have strictly sublinear memory, i.e.,each machine has memory nα for some constant α < 1. In this setting,392

Round Reduction via Graph Exponentiation

we first present a simple (2 + ϵ)-approximation algorithm that runs inO(log n) rounds; we then show, using graph exponentiation, how to√
improve it to run in Õ( log n) rounds.
7.1.1

O(log n)-round Algorithm

For a graph G = (V, E), let V≤k be the set of vertices with corenessnumber ≤ k and let D≤(2+ϵ)k the set of vertices with degree ≤ (2 + ϵ)k.
We let degS (u) denote u’s degree in the subgraph induced on S ⊆ V .
The O(log n)-round algorithm is based on the following simple
observation:
|V

|

≤k
.
Lemma 7.1. |V≤k \ D≤(2+ϵ)k | ≤ 1+ϵ/2

Using this, for any fixed k we can find a (2 + ϵ)-approximate V≤kby the following method (Algorithm 10). The algorithm repeatedly
removes vertices of degree less than 2(1 + ϵ)k and adds them to Λ. From
Lemma 7.1 it follows that Λ is unchanged after Θ( 1ϵ log n) rounds.
Algorithm 10 Computing (2 + ϵ)-approximate V≤k for fixed k.
1: Input: Graph G = (V, E) and a threshold k
2: Output: Λ such that V≤k ⊆ Λ ⊆ V≤2(1+ϵ)k3: Λ ← ∅4: for Θ( 1ϵ log n) rounds do
5:
Find S := {u ∈ V | degV (u) ≤ (2 + ϵ)k}6:
V ←V \S7:Λ←Λ∪S
8: end for

It is easy to see that Algorithm 10 computes Λ as desired. To
implement the algorithm in the MPC model, we use the fact that it
only needs to scan the adjacency list of each vertex to find S, which canbe done using memory max(∆, nα ), where ∆ is the maximum degree inthe graph. With slightly more care, the dependence on ∆ can in fact
be removed.
We next show how to compute approximate coreness numbers. For
each integer i ≥ 1, let Λi be such that V≤(1+ϵ)i n ⊆ Λi ⊆ V≤(2+ϵ)(1+ϵ)i nand let Λ0 := V≤0 . We can compute all Λi , 0 ≤ i ≤ log log1+ϵ n inparallel in O( 1ϵ log n) rounds, using Algorithm 10. We declare u has

7.1. Approximate Core Decomposition

393

coreness number (2 + ϵ) · (1 + ϵ)i for the highest i such that u ∈ Λi . Then,from by definition of Λi , we have (1 + ϵ)i−1 n ≤ CG (u) ≤ (2 + ϵ)(1 + ϵ)i n,
which implies a ((2 + ϵ)(1 + ϵ))-approximate coreness labeling.
To summarize, a primitive that we used to obtain a (2 + ϵ)approximate algorithm was the following: identifying and removing
a set S of vertices in constant number of rounds from V≤k such that(i) each vertex in S has coreness number at most (2 + ϵ)k and (ii) thesize of V≤k decreases by a constant factor. Lemma 7.1 offers the basis
for the primitive, which states S can be the set of vertices of degree at
most (2 + ϵ)k in the remaining graph.
7.1.2√
O( log n)-round Algorithm√
To reduce the required number of rounds to Õ( log n), we will modify
the primitive as follows: Can we remove a set S of vertices in O(log log n)rounds from V≤k ensuring (i) each vertex in S has coreness number
at most (2√+ 3ϵ)k and (ii) the size of V≤k decreases by a factor of
1/(1 + ϵ/6) log n ? If this is feasible, by repeatedly applying the primitive√√
Θ( log n) times, we will achieve Õ( log n) rounds. We will constructthis new primitive will by compressing multiple rounds using graphexponentiation combined with a couple of other ideas, detailed below.
We start by observing a certain local property in Algorithm 10:
whether a vertex u is removed from V in the ith iteration of the forloop depends only on u’s ith neighborhood, i.e., the vertices that arewithin i hops from u. More precisely, whether u ∈ Si or not only depends
on u’s ith neighborhood. Indeed, this can be verified by seeing that every
vertex u in Si must be adjacent to some vertex in Si−1 for otherwise, umust have been added to the solution in the (i − 1)st iteration.
As discussed earlier, this suggests a way to simulate Algorithm 10 in√
MPC more efficiently: if we could store the O( log n)-neighborhood of√every single vertex in a machine we could simulate O( log n) rounds in√almost a single round; this would lead to an Õ( log n)-round algorithm.
√
Unfortunately it is often not possible to load the entire O( log n)neighborhood of every vertex in a machine. Thus, the key challenge lies
in simulating graph exponentiation in a memory efficient manner.

394

Round Reduction via Graph Exponentiation

The key idea is to use sampling. We observe that Lemma 7.1 offerssome flexibility: instead of removing all vertices of degree less than
(2 + ϵ)k, we can try to remove all vertices of degree, say, less than
(2 + ϵ/3)k but none of degree higher than (2 + 3ϵ)k; the remaining
vertices can be handled arbitrarily. It is easy to show that this modified
process still decreases V≤k by a constant factor. Thus, we only need toapproximately measure the degree of each vertex.
The following lemma allows us to run Algorithm 10 using (2 + 2ϵ3 )pk
as a new threshold after sampling each edge with probability p. Notethat (i) in the modified primitive comes from its guarantees. Its proof
is a direct application of a Chernoff bound.
Lemma 7.2. Let G′ be the ngraph obtainedby sampling every edge ofo
10 log n
G with probability p = min 1, (ϵ/3)2 k . Then, w.h.p. it holds:• If dG (v) ≤ (2 + 3ϵ )k, then dG′ (v) < (2 + 2ϵ
3 )pk.
• If dG (v) ≥ (2 + 3ϵ)k, then dG′ (v) ≥ (2 + 2ϵ
3 )pk.
√
However, even after sampling, the O( log n)-neighborhood of somevertex may be too large to fit in O(nα ) memory. To tackle this problem,at the beginning of every phase we freeze vertices with significantly highdegrees and we do not delete any frozen vertices in the phase. Interestingly we can show that this does not effect the algorithm too much.
Indeed by Lemma 6.2, there are not many vertices with coreness number
smaller than k yet have such high degree. Furthermore, by “ignoring”√
all the frozen vertices, after sampling the O( log n)-neighborhood ofevery vertex fits in a single machine’s memory, whp.
To make the high-level ideas more transparent, we only focus on√
how we can simulate the first log n iterations of Algorithm 10 inO(log log n) MPC rounds. We can make the total memory usage at
most nδ factor more than the whole input size for any constant δ > 0.
This is achieved by the following algorithm.
Every vertex in V \ F has a degree at most h. Therefore, after
sampling it has a degree at most hp in expectation and at most 2hp√
whp by a Chernoff bound. Thus, for every vertex u ∈ V√\ F , u’s log nneighborhood in (V \ F, E ′ ) has size at most (2hp) log n ≤ n2δ for7.1. Approximate Core Decomposition395√
any constant ϵ and sufficiently large n. This implies that the log nneighborhood fits in a single machine and we can process all non-frozen
vertices in parallel by using at most n2δ factor more memory than
the input size in total. Further, as observed before, we can determine√√
if Algorithm 10 adds v to Γ within n iterations only using v’s nneighborhood. Using graph exponentiation, this can be simulated in√log( log n) = O(log log n) rounds.
We now check properties (i) and (ii) needed for the primitive. Thanks
to Lemma 7.2, every vertex added to Λ in Algorithm 11 has corenessnumber at most (2+3ϵ)k; thus Λ satisfies (i). Further, due to Lemmas 7.2
and 7.1 with threshold (2 + ϵ/3)k, we know that |V≤k \ F \ Λ| ≤1√|V≤k \ F |. Further, by Lemma 6.2, we know that |F | ≤log n(1+ϵ/6)

2k|V≤k |/h =√1|V≤k |. Therefore, Λ satisfies (ii).
2 log nAlgorithm 11 Compressing
via graph exponentiation√

log n rounds into O(log log n)-rounds

1: Input: Graph G = (V, E) and a coreness threshold k
2: Output: Λ such that (i) Λ ⊆ V≤(2+3ϵ)k , (ii) |V≤k \ Λ| ≤√2√|V≤k |(1+ϵ/6) log n(frozenn vertices)o
10 log n
4: E ← edges sampled i.i.d. with probability p = min 1, (ϵ/3)
2k√
5: Each vertex collects in V \ F its log n-neighborhood in (V \ F, E ′ ) inparallel in O(log log n) rounds
6: Simulate Algorithm 10 with graph (V√\ F, E ′ ) threshold (2 + 2ϵ
3 )pk foreach v ∈ V \ F ; if v ∈ Si for some i ≤ log n, then add v to Λ

3: F ← vertices with degree ≥ h := 2k · 2

δ log n′Thus, by repeating Algorithm 11 q times such that2√(1+ϵ/6) log n

q

<

1
that V≤k ⊆ Λ ⊆ V≤(2+3ϵ)k . And this can be donen , we will have Λ such√in O(log log n)q = Õ( log n) rounds for any fixed constant ϵ > 0. This
produces essentially the same output as Algorithm 10 but using only√Õ( log n) rounds. The remaining procedure is almost identical. Thus,√
we can compute (2 + ϵ)-approximate coreness in Õ( log n) rounds.

396
7.2

Round Reduction via Graph Exponentiation
Connected Components

Finding connected components in an unweighted graph is a fundamental
primitive with many practical applications. In this section we firstdescribe a basic sequential algorithm. Then we will discuss how toparallelize it to obtain an O(log n)-round algorithm using sublinear
memory. We will then show how to modify it using graph exponentiation
to obtain an Õ(log D) algorithm, where D is the diameter of the graph.
We first present a simple sequential algorithm for finding connectedcomponents (Algorithm 12).
Algorithm 12 Sequential connected component algorithm.
1: Input: Graph G = (V, E)
2: Output: Set S of connected components of G
3: S = ∅4: ∀v ∈ V, S = S ∪ {v}
5: while ∃S ∈ S that has an edge to another component S ′ ∈ S do
6:
S = S \ S, S ′7:
S = S ∪ {S ∪ S ′ }8: end while
9: Output S

Note that the algorithm can be efficiently implemented in sequential
setting using a union-find data structure and it returns the correctconnected components of the graph. Next, we will discuss how toparallelize this algorithm to run in O(log n) rounds.
7.2.1

O(log n)-round Algorithm

The main idea to parallelize Algorithm 12 is to activate multiple connected components in every round. But, we cannot arbitrarily let every
connected component to merge with a neighboring connected component
at the same time, since it can lead to long merging chains.
To circumvent this problem we design a simple merging strategy
where in every round the algorithm merges only disjoint sets of connectedcomponents. In particular, the following steps are done in constantnumber of rounds: (i) each connected component in S picks either red
or green uniformly at random, (ii) each connected component informs

7.2. Connected Components397

all its neighboring connected components about its color choice, and(iii) every red connected component selects a random green neighboring
connected component (if any). In this way disjoint “stars” are formed,
each consisting of a central green connected component connected to
one or more red neighboring connected component(s). Then, we merge
all connected components in each star. Figure 7.2 presents a visual
representation of the process. See Algorithm 13 for a formal description.

Figure 7.2: In step (a), we represent each connected component with a vertex.

In step (b), each connected component picks a random color. In step (c) every
red components pick a random neighboring green components and finally instep (d) the connected components are collapsed.

Theorem 7.3. For large enough constant C, Algorithm 13 computes
with high probability the connected components of G in O(log n) rounds
in MPC using machines with sublinear memory.
Proof. Let nδ be the memory per machine where δ ∈ ( 12 , 1)2 . We first
discuss how to implement the algorithm in MPC and then prove its
correctness.
2

We assume that δ > 21 only for simplicity.

398

Round Reduction via Graph Exponentiation

Algorithm 13 Parallel connected components algorithm.
1: Input: Graph G = (V, E)
2: Output: Set S of connected components of G
3: S = ∅4: ∀v ∈ V, S = S ∪ {v}
5: for C log n rounds in parallel do
6:
for S ∈ S do
7:
S selects a random color {red, green}
8:
S sends its color to its neighboring connected components
if S is red and has at least one neighboring green connected compo9:

nent thenS select a random neighboring green connected component andmerges with it
11:
end if
12:
end for
13: end for
14: Output S

10:

There are two obstacles to implementing Algorithm 13 in the MPC
model. First, a connected component may have size more than nδ , inwhich case it will be split across machines. Second, in the selection step,a green component may be selected by more than nδ red components,
in which case, again, the merge step needs to be distributed.
Both of these issues can be addressed by a single level of indirection:
one can use a two level tree to route all of the necessary communication.
For instance, in the first case, each large component can have nδ vertices
selected as “coordinators,” and all of the other vertices are assigned toa unique coordinator. All of the communication is first passed to thecoordinators, who then pass the information to the individual vertices.
Since we had assumed δ > 1/2, a single level of indirection suffices, but
it is easy to extend the same argument for arbitrarily small δ. A similar
approach can be used to handle the case of many red vertices connecting
to a single green vertex.
Now we turn our attention to correctness. Clearly the algorithm
does not merge disconnected components so we only need to show thatevery connected component is correctly identified. To prove this we
focus on a single connected component C of size k. Initially, we have k7.2. Connected Components

399

distinct components and we will now show that if we have more than
one active connected component in C after each execution of the forloop, the number of connected components decreases in expectation
by a factor of 34 . Note that a connected component is not merged ina round of the algorithm if it either selects the color green (happens
with probability 12 ) or if none of its neighbors is colored green (happens
with probability at most 14 since every component in C has at least
one neighboring component.) So every component is not merged withprobability at most 34 . Thus in expectation the number of components
in C decreases by 34 in every round. Hence with constant probability,
a constant fraction of the connected components is merged in every
round and so with high probability the process converges to a single
connected component in O(log k) rounds.
7.2.2

Õ(log D)-round Algorithm

To improve the round efficiency of the algorithm presented in Section 7.2.1, a key observation is that it does not always make sense tosample the green and the red color with the same probability. Suppose hypothetically that all of the connected components would haveneighborhood of size nγ for constant γ in every round of the algorithm.
γThen, by coloring every component green with probability n− 2 and redotherwise we would make more progress. In fact, the probability of aγconnected component failing to merge would be at most n− 3 and so thealgorithm would converge in O( γ1 ) rounds. Unfortunately, the hypothetical condition may not hold. Nevertheless, we will show how to leverageon the double exponential size reduction techniques to circumvent thisobstacle. In particular we show how to obtain an O( γ1 log D)-roundalgorithm.
The main idea is that connected components with small neighborhoods can be efficiently modified to become connected components withlarge neighborhoods. In particular, every connected component can send
all its neighboring components to all its neighbors iteratively. In thisway, in i rounds every connected component receives its 2i -neighborhood.
Unfortunately one cannot run this exponentiation until convergencesince it can require too much memory. However, one can run this process

400

Round Reduction via Graph Exponentiationδ

until every connected component has at least n 2 neighboring connectedcomponents. At that point every connected component colors itself
δgreen with probability n− 3 or red otherwise. Then every red connectedcomponent selects a neighboring green connected component and merges
with it as before. In Figure 7.3 we present a visualization of the process,which can be shown to converge in O( γ1 log D) rounds.

Figure 7.3: In step (a), we represent each connected component with a vertex.

In step (b), grows its neighborhood. In step (c) every connected component
select its colors randomly. In step (d) every red component picks a randomneighboring green component and the connected components are collapsed.

We now present the pseudo-code in Algorithm 14.
Theorem 7.4. With high probability, Algorithm 14 computes the connected components of G in O( 1δ log D)-rounds in the MPC model where
each machine has memory nδ , 21 < δ < 1.
Proof. The implementation details of this algorithm are very similar tothat of Theorem 7.3. The only additional difficulty is to implementation
the graph exponentiation process, but this can be easily done using acoordinator and by noticing that the total number of edges received bya single machine in the doubling phase is bounded by O(nδ ).

7.2. Connected Components

401

Algorithm 14 Õ(log D) connected component algorithm.
1: Input: Graph G = (V, E).
2: Output: The set S of connected components of G
3: S = ∅4: ∀v ∈ V, S = S ∪ {v}
5: for C log n rounds in parallel do
6:
for log D rounds in parallel do
7:
for S ∈ S doδ8:
if S neighborhood is smaller than n 2 thenδ9:
if S has a neighboring connected component S ′ with n 2 + 1

neighboring connected component thenS connects with all neighboring connected components of S ′else
S connects to all the neighboring connected components of
its neighboring connected component
13:
end if14:
end if15:
end for16:
end for17:
for S ∈ S do
δ18:
if S neighborhood is larger than n 2 thenδ
19:
S colors itself green with probability n− 3 or red otherwise
20:
S sends its color to its neighboring connected component
21:
if S is red and has at least one neighboring green connectedcomponent then22:
S select a random neighboring green connected component andmerge with it
23:
end if24:
else
25:
if S is the smallest id components between its neighbors then26:
S collapse all its neighbors in a single connected component27:
end if28:
end if
29:
end for
30: end for
31: Output S
10:
11:
12:

Furthermore, we note that in O(log D) rounds of graph exponentiation, a connected component is either transformed into a clique orδinto a graph where every vertex has degree at least n 2 . In the first case,the connected component is found in a single round. In the second case,402

Round Reduction via Graph Exponentiationδthe number of active connected components decreases by a n− 4 factor,
with high probability. Thus with constant probability the algorithm
converges to the right solution in O( 1δ log D) rounds.
7.3

Section Notes

The content of this section is mainly based on Ghaffari et al. (2019b)
and Andoni et al. (2018). In particular the first parallel algorithm using
sublinear memory and sub-logarithmic rounds for k-core decomposition
was presented in Ghaffari et al. (2019b). The first parallel algorithm
using less then O(log n) parallel rounds and sublinear memory has beenpresented in Andoni et al. (2018).
The graph exponentiation technique was first introduced to speed-up
algorithm in the distributed LOCAL model by Lenzen and Wattenhofer(2010) and then adapted to the MPC model by Ghaffari and Uitto (2019)to provide efficient algorithms for matching and maximum independent
set. Algorithm 10 is reminiscent of the densest subgraph algorithm for
MPC due to Bahmani et al. (2012a). To the best of our knowledge,
there is no algorithm with better than 2-approximate algorithm thatruns in o(log n) rounds using strictly sublinear memory for the k-coredecomposition problem.
Developing algorithms for graph connectivity has been an important
topic in the MPC model; see Andoni et al. (2018), Behnezhad et al.
(2019a), and Coy and Czumaj (2022) for recent work on this topic.

8
Lower Bounds

Owing to numerous applications, graph problems have received significant attention in the MPC model. In previous sections, we studied
MPC algorithms for vertex cover, connected components, maximum
matching, independent set, and many others.
8.1

Connectivity in MPC

While new algorithms have been developed, there seems to exist a barrier
to obtaining constant round algorithms for many of these problems.
Intuitively, this may be due to graph properties depending on the global
structure, which is difficult to grasp in a small number of rounds wheneach machine can only see part of the input graph. The sharpest exampleof this is the graph connectivity problem, for which we can state thefollowing challenge:
Given an n-vertex undirected graph whose edges are arbitrarily partitioned across machines each with memory O(nα )for some constant α < 1, can we determine if the graph isconnected in o(log n) rounds?
Recall the O(log n)-round algorithm in Section 7.2. Can we do better?
403

404

Lower Bounds

To appreciate this question, we will consider the following problem.
Problem 8.1.1 (1-vs-2-cycle). Given an undirected graph on n vertices
and n edges where the edges are arbitrarily placed across machines ofmemory size M = O(nα ) for α < 1, determine if it is a single cycle oflength n or two cycles of length n/2.
Even this simple instance of the graph connectivity problem has
resisted an o(log n)-round algorithm.
We can, however, formally rule out natural approaches for solving
this problem. For example, consider the approach of merging edges toobtain paths, retaining only the endpoints of the path (which is memoryefficient), and iterating to merge adjacent paths. For merging, note thatpaths sharing endpoints must be on the same machine. However, it
seems hard to merge a super constant number of paths into a single path
during a single round. Indeed, this idea can be formalized to show that
it is hard to decrease the total number of paths stored across machines
by more than a constant factor, which implies a lower bound of Ω(log n)rounds for algorithms using this approach.
Generally, it is believed that the connectivity problem admits noo(log n)-round algorithm. However, proving such a statement would
resolve a long standing open problem in computational complexity.
In this section, we will first discuss an unconditional lower boundshowing that graph connectivity (and many other graph problems)
need Ω(logM n) rounds, and improving this lower bound would imply
a breakthrough result in circuit complexity theory, i.e., NC1 ̸= P.
We then discuss conditional lower bounds, showing a reduction frommaximum matching and maximal independent set problems to thegraph connectivity, and showing that they require Ω(log log n) rounds.
8.2

Unconditional Lower Bounds

We first discuss why traditional computational complexity tools are hard
to use to obtain unconditional lower bounds. Consider communication
complexity, a standard lower bound tool, which quantifies the amount ofcommunication needed between different parties owning different piecesof the input to jointly compute a function. Given that the difficulty

8.2. Unconditional Lower Bounds

405

of the graph connectivity comes from each machine seeing only partof the input, communication complexity seems appealing. However,in an MPC setting, the total amount of communication is allowed
to exceed the input size. Unfortunately, communication complexity
becomes meaningless here since the entire input can be communicated.
Circuit complexity offers a different set of tools for showing lower
bounds. A (Boolean) circuit takes n binary inputs, (x1 , . . . , xn ) ∈ {0, 1}n ,processes them via interconnected gates, such as ‘and’, ‘or’, ‘not’, andproduces a binary output. The depth of a gate is the length of thelongest path from any input to the gate and the depth of the circuit is
the maximum depth of all gates. If every gate can take at most f inputs,
then the circuit’s fan-in is f . In the MPC model, while each machine’s
computation in round r can be viewed a “super” gate of depth r in acircuit, there are fundamental differences between MPC and circuits.
First, a circuit is a static object while in MPC, depending on the local
computation result, a machine can send data to different machines inthe shuffle phase. Second, in MPC, a machine can choose to (be silentand) send out no data after the local computation, while each gate in acircuit always has an output.
The two differences are closely related to each other. Obviously,
dynamic communication topology can give more power to MPC and it
becomes more effective with silence being allowed since it can reduce
unnecessary communication. Further, silence itself can carry extra
information—for example, receiving no data from machine i could
imply that the machine does not have the data that is desired. In fact,a Boolean circuit computation can be simulated in MPC, essentiallymeaning that MPC is more powerful than circuit computation.
Lemma 8.1. Every Boolean circuit of depth d and fan-in 2 can be
simulated in O(d/ log M ) MPC rounds.
Proof. Each gate of depth log2 M depends on at most M inputs aseach gate has fan-in 2. It is easy to see that all gates of up to depth
log2 M can be simulated in one round of MPC. Repeating this completes
the proof.
The contrapositive of this immediately yields the following.

406

Lower Bounds

Corollary 8.2. If a problem P in P requires ω(log n/ log M = logM n)
MPC rounds, then the problem admits no Boolean circuit of depthO(log n) and fan-in 2, i.e., P ∈/ NC1 .
It is a long-standing open question if P ̸= NC1 . Thus, we cannot
expect a better than Ω(logM n) lower bound without a breakthroughin circuit complexity.
8.2.1

Overview of Ω(logM n) Lower BoundIn the remainder of this section, we sketch an Ω(logM n) lower bound.
The high-level strategy will consist of the following steps.
1. Defining an M -shuffle computation, which is more powerful thanthe MPC model; hence any lower bound for the M -shuffle model
would imply the same lower bound for MPC. Roughly speaking,the model allows unlimited number of machines for computationand exponential time local computation.
2. Showing any R-round computation of the M -shuffle model can be
expressed as a Boolean function that is a multi-linear polynomialof degree at most M R .
3. Showing most graph properties, including connectivity, require
high-degree polynomials.
8.2.2

M -Shuffle Model

Defining a model that is simpler yet more powerful than MPC will help
obtain the desired lower bounds. To highlight the main ideas, we only
present the important features of the M -shuffle model. The key insightto the modeling is to explicitly account for a machine not communicatingwith another machine through the use of a special symbol, ⊥.
• There is no limit on the number of machines available. Thus, we
can assume that each machine u is used only in a specific roundr(u) ∈ {1, . . . , R}, where R is the number of rounds.
• Each machine has an ordered set {1, . . . , M } of input ports.

8.2. Unconditional Lower Bounds

407• In each round, each machine u sends a message αuv (·) ∈ {0, 1, ⊥}M
to each machine v with r(v) > r(u).
• Machine v receives 0, 1, or ⊥ on its ith input port from every
machine u with r(u) < r(v). If the machine receives more than one
non ⊥ symbol on each port, the computation is declared invalid.
Otherwise, machine v’s input, denoted as g(v), is naturally defined:
g(v)i is 1 (0, resp.) if and only if its ith port receives a 1 (0, resp.);otherwise ⊥.
We assume for ease of analysis that each machine’s input ports areordered. We leave it as an exercise to show that the assumption can beremoved and how the model can extend to capture randomization.
8.2.3

Representing M -Shuffle Computation by Polynomials

Now we show that any R-round computation of the M -shuffle model
can be expressed as a polynomial of degree at most M R . We sketch themain idea here. Let I(·) be the binary indicator function. We would liketo show that for any machine v and any specific input z ′ to the machine,I(g(v) = z ′ ) can be expressed as a polynomial of degree at most M r(v) .
To illustrate the idea, we only show that I(g(v) = z ′ ) is a polynomialof degree at most M 2 for a fixed machine v from round 2. Repeating
this argument will give the desired claim: a machine from round 3 willtake messages from a set of machines from round 1 or 2 and take theiraggregation as its input. Let fuit (x) be a Boolean function that hasvalue 1 if and only if machine u sends a symbol t ∈ {0, 1, ⊥} to machinev on port i when the input is x. Machine u is from round 1 and has
memory M bits, so can depend on at most M input variables. Usingy1 ∧ y2 = y1 y2 , y1 ∨ y2 = (1 − y1 )(1 − y2 ), ¬y1 = 1 − y1 , y1 = y12 forany y1 , y2 ∈ {0, 1}, it is easy to see that fuit can be expressed as apolynomial of degree M . Then, we haveI(g(v)i = 0) =Xu∈U

fui0 (x),I(g(v)i = 1) =X

fui1 (x),u∈U

I(g(v)i = ⊥) = 1 − I(g(v)i = 0) − I(g(v)i = 1),408

Lower Bounds

where we used the fact that v receives at most one non-⊥ symbol onport i. Thus, we have,I(g(v) = z ′ ) =Y

I(g(v)i = zi′ ),i∈[M ]

which proves that I(g(v) = z ′ ) can be represented as a polynomial of
degree M 2 , as desired.
8.2.4

Graph Connectivity is a High Degree Polynomial

It is well-known that any Boolean function f : {0, 1}n → {0, 1} can beP
represented as a multilinear polynomial S⊆[n] h(S)xS where h(S) ∈Q{0, 1} and xS := i∈S xi , using the fact that x2i = xi . For a given f ,this multilinear polynomial is unique and its degree is called the degreeof f .
Consider the following simple graph problem. There are n+1 vertices,
indexed 0, 1, 2, . . . , n. Edges can be present only between vertices i − 1
and i for i ∈ [n] and xi indicates the presence or absence of the edgeQ(i − 1, i). Then, the Boolean formula ni=1 xi of degree n variables hasvalue 1 if and only if the graph is connected. As shown before, anR-round M -shuffle can compute a polynomial of degree at most M R ,and therefore, it immediately follows that even this special case of graphconnectivity requires Ω(logM n) MPC rounds.
In general, graph connectivity is one example of a monotone graphproperty. Recall that for undirected graphs, a graph property is independent of the vertex labeling, is monotone if it becomes false when a
new edge is added to the graph, and is non-trivial unless the property
holds for all graphs or does not hold for any graph. It is known that any
non-trivial monotone graph property has Ω(n2 ) decision-tree complexity,
and any Boolean function f of degree d has decision-tree complexity
at most 2d4 . Together these imply that computation of any monotone
graph property requires Ω(logM n) rounds in the M -shuffle model.
8.3

Conditional Lower Bounds

Due to the barriers in obtaining a logarithmic lower bound for Problem 8.1.1, there have been efforts to prove super-constant lower bounds

8.3. Conditional Lower Bounds

409

for other graph problems, assuming a logarithmic lower bound forconnectivity. We highlight some of these recent results. The first is aconditional lower bound for s-t-connectivity in terms of the diameter.
Theorem 8.3. If there is no o(log n)-round MPC algorithm for Problem 8.1.1, then there is no o(log D)-round MPC algorithm for solving
s-t-connectivity problem on graphs of diameter D.
Conditional lower bounds for many graph problems can also be
obtained.
Theorem 8.4. If there is no o(log n)-round MPC algorithm for Problem 8.1.1, then there is no o(log log n)-round MPC algorithm that computes an O(1)-approximate maximum matching, an O(1)-approximate
vertex cover, or a maximal independent set.
These conditional lower bounds are obtained using a novel connection
between the graph connectivity problem and the LOCAL model ofcomputation, described next. In the LOCAL model, each vertex of agiven graph only knows its own identity, the identity of its neighbors,and the total number of vertices; in particular, it does not know thewhole graph. In each round, each vertex performs some computation
based on its knowledge and then sends messages to its neighbors. At
the end of these distributed steps of computation, each vertex needs toknow its part of the output. For example, in the maximum matchingproblem, each vertex needs to know the vertex to which it is matched(if at all). In the maximal independent set problem, each vertex needs
to know if it indeed belongs to the independent set.
The connection can be informally described as follows.
Theorem 8.5. Suppose a graph problem has a D-round lower bound in
the LOCAL model, where D ≤ logγ n for some constant γ < 1. Then,
there is no o(log D)-round MPC algorithm for the problem unless there
is an o(log n)-round algorithm for Problem 8.1.1.
Theorem 8.4 then immediately follows from applying the knownpΩ( log n/ log log n)-round lower bound in the LOCAL model for thegraph problems in the statement.

410

Lower Bounds

The proof of Theorem 8.5 is quite involved; we only provide ahigh-level description of the main ideas. Suppose a graph problem has
a D-round lower bound in the LOCAL model. Then, the idea is toshow that if there is an MPC algorithm A solving this graph problem
in o(log D) rounds, then this algorithm must see certain “far away”
information (i.e., information that lies more than D hops away) to
produce the correct result. Specifically, one can construct two graphs
G and G′ with specialized vertices v and v ′ such that G and G′ areisomorphic within D hops from v and v ′ respectively, but the output
at v and v ′ are different when running A. Using this, the idea is toconstruct an o(log D)-round MPC algorithm for solving the D-diameters-t-connectivity problem by using the o(log D)-round algorithm A as
an oracle, which will contradict Theorem 8.3.
8.4

Section Notes

The lower bounds and the formalization of the M -Shuffle was introduced
by Roughgarden et al. (2016), the conditional lower bounds are due
to Ghaffari et al. (2019a). Finally, Charikar et al. (2020) showed an
unconditional lower bound of Ω(logM n) for the 1-vs-2-cycle problem
by using a connection between query complexities and Boolean formuladegrees.
Many more results are known for restricted settings. Im and Moseley(2019) showed that a certain class of algorithms require Ω(log n) rounds
to solve the 1-vs-2-cycle problem. A related result was shown earlier by
Beame et al. (2017) in the context of relational data sets. A lower boundunder similar algorithmic limitations was given for a certain game by
Jacob et al. (2014).
For specific problems, Pietracaprina et al. (2012) gave a lower boundfor matrix multiplication assuming that all elementary products must
be computed. Bilardi et al. (2012) gave tight lower bounds on the fan-in
for computing the Fast Fourier Transform in a restricted BSP model.

9Conclusions

The MPC model has emerged as a valuable formalization of modern
parallel computing, encompassing many different frameworks and implementations, such as MapReduce, Hadoop, and Spark, among others. The
sublinear memory constraint, coupled with the goal of minimizing thetotal number of rounds forces the algorithm designer to parallelize thecomputation not too coarsely (respecting the memory constraints), andnot too finely (keeping to a small number of rounds). This sweet-spot
has led to new algorithms that we have covered in this monograph.
We have presented a lot of different techniques that are used indesign of MPC algorithms, but the coverage is not comprehensive by
design. We have chosen approaches that unify multiple results andidentify the key algorithmic and analytical insights. Our focus was on
exploring and understanding these techniques; for many problems wedeliberately did not present state-of-the-art results.
The field of MPC algorithms continues to be actively pursued by the
research community and the demand for new and more efficient MPC
algorithms continues to rise among practitioners. We hope this survey
will be useful to both these communities and will act as a conduit for
new problems and new algorithms.

411

References

Afrati, F. N., A. D. Sarma, S. Salihoglu, and J. D. Ullman. (2012). “Upper and Lower Bounds on the Cost of a Map-Reduce Computation”.
arXiv: 1206.4377.
Andoni, A., A. Nikolov, K. Onak, and G. Yaroslavtsev. (2014). “Parallel
Algorithms for Geometric Graph Problems”. In: STOC. 574–583.
Andoni, A., Z. Song, C. Stein, Z. Wang, and P. Zhong. (2018). “Parallel
Graph Connectivity in Log Diameter Rounds”. In: FOCS. 674–685.
Assadi, S., M. Bateni, A. Bernstein, V. S. Mirrokni, and C. Stein.
(2019a). “Coresets Meet EDCS: Algorithms for Matching and Vertex
Cover on Massive Graphs”. In: SODA. 1616–1635.
Assadi, S., M. Bateni, and V. S. Mirrokni. (2019b). “Distributed
Weighted Matching via Randomized Composable Coresets”. In:
ICML. 333–343.
Bahmani, B., R. Kumar, and S. Vassilvitskii. (2012a). “Densest Subgraph in Streaming and MapReduce”. PVLDB. 5(5): 454–465.
Bahmani, B., B. Moseley, A. Vattani, R. Kumar, and S. Vassilvitskii.
(2012b). “Scalable K-Means++”. PVLDB. 5(7): 622–633.
Bateni, M. H., S. Behnezhad, M. Derakhshan, M. T. Hajiaghayi, R.
Kiveris, S. Lattanzi, and V. Mirrokni. (2017). “Affinity clustering:
Hierarchical clustering at scale”. In: NIPS. 6867–6877.
Beame, P., P. Koutris, and D. Suciu. (2017). “Communication steps forparallel query processing”. JACM. 64(6): 40:1–40:58.
412

References

413

Behnezhad, S., L. Dhulipala, H. Esfandiari, J. Lacki, and V. S. Mirrokni.
(2019a). “Near-Optimal Massively Parallel Graph Connectivity”. In:
FOCS. 1615–1636.
Behnezhad, S., M. Hajiaghayi, and D. G. Harris. (2019b). “ExponentiallyFaster Massively Parallel Maximal Matching”. In: FOCS. 1637–1649.
Bhaskara, A. and M. Wijewardena. (2018). “Distributed Clustering via
LSH Based Data Partitioning”. In: ICML. 569–578.
Bilardi, G., M. Scquizzato, and F. Silvestri. (2012). “A lower boundtechnique for communication on BSP with application to the FFT”.
In: ECPP. 676–687.
Broder, A. Z., L. G. Pueyo, V. Josifovski, S. Vassilvitskii, and S. Venkatesan. (2014). “Scalable K-Means by ranked retrieval”. In: WSDM.
233–242.
Ceccarello, M., A. Pietracaprina, and G. Pucci. (2019). “Solving k-center
Clustering (with Outliers) in MapReduce and Streaming, almost as
Accurately as Sequentially”. Proc. VLDB Endow. 12(7): 766–778.
Chang, Y., M. Fischer, M. Ghaffari, J. Uitto, and Y. Zheng. (2019).
“The Complexity of (∆+1) Coloring in Congested Clique, Massively
Parallel Computation, and Centralized Local Computation”. In:
PODC. 471–480.
Charikar, M., W. Ma, and L.-Y. Tan. (2020). “New lower bounds for
Massively Parallel Computation from query complexity”. In: SPAA.
141–151.
Chierichetti, F., R. Kumar, and A. Tomkins. (2010). “Max-cover in
map-reduce”. In: WWW. 231–240.
Cohen-Addad, V., S. Lattanzi, S. Mitrovic, A. Norouzi-Fard, N. Parotsidis, and J. Tarnawski. (2021a). “Correlation Clustering in ConstantMany Parallel Rounds”. In: ICML. 2069–2078.
Cohen-Addad, V., S. Lattanzi, A. Norouzi-Fard, C. Sohler, and O.
Svensson. (2021b). “Parallel and Efficient Hierarchical k-Median
Clustering”. In: NeurIPS.
Coy, S. and A. Czumaj. (2022). “Deterministic massively parallel connectivity”. In: STOC. 162–175.
Czumaj, A., J. Lacki, A. Madry, S. Mitrovic, K. Onak, and P. Sankowski.
(2018). “Round compression for parallel matching algorithms”. In:
STOC. 471–484.

414

References

Dean, J. and S. Ghemawat. (2008). “MapReduce: Simplified Data
Processing on Large Clusters”. CACM. 51: 107–113.
Ene, A., S. Im, and B. Moseley. (2011). “Fast clustering using MapReduce”. In: KDD. 681–689.
Ene, A. and H. L. Nguyen. (2015). “Random Coordinate Descent Methods for Minimizing Decomposable Submodular Functions”. In: ICML.
787–795.
Esfandiari, H., S. Lattanzi, and V. Mirrokni. (2018). “Parallel andStreaming Algorithms for K-Core Decomposition”. In: ICML. 1396–
1405.
Feldman, J., S. Muthukrishnan, A. Sidiropoulos, C. Stein, and Z. Svitkina. (2010). “On distributing symmetric streaming computations”.
TALG. 6(4): 66:1–66:19.
Frigo, M., C. E. Leiserson, H. Prokop, and S. Ramachandran. (2012).
“Cache-Oblivious Algorithms”. TALG. 8(1): 4.
Ghaffari, M., T. Gouleakis, C. Konrad, S. Mitrovic, and R. Rubinfeld.
(2018). “Improved Massively Parallel Computation Algorithms for
MIS, Matching, and Vertex Cover”. In: PODC. 129–138.
Ghaffari, M., F. Kuhn, and J. Uitto. (2019a). “Conditional Hardness
Results for Massively Parallel Computation from Distributed Lower
Bounds”. In: FOCS. FOCS ’19.
Ghaffari, M., S. Lattanzi, and S. Mitrovic. (2019b). “Improved Parallel
Algorithms for Density-Based Network Clustering”. In: ICML. 2201–
2210.
Ghaffari, M. and J. Uitto. (2019). “Sparsifying Distributed Algorithms
with Ramifications in Massively Parallel Computation and Centralized Local Computation”. In: SODA. 1636–1653.
Goel, A. and K. Munagala. (2012). “Complexity Measures for MapReduce, and Comparison to Parallel Computing”. arXiv: 1211.6526.
Gonzalez, T. F. (1985). “Clustering to minimize the maximum intercluster distance”. TCS. 38: 293–306.
Goodrich, M. T. (2010). “Simulating Parallel Algorithms in the MapReduce Framework with Applications to Parallel Computational Geometry”. arXiv: 1004.4708.

References

415

Goodrich, M. T., N. Sitchinava, and Q. Zhang. (2011). “Sorting, Searching, and Simulation in the Mapreduce Framework”. In: ISAAC. 374–
383.
Hegeman, J. W. and S. V. Pemmaraju. (2015). “Lessons from thecongested clique applied to MapReduce”. TCS. 608: 268–281.
Im, S. and B. Moseley. (2015). “Brief Announcement: Fast and Better
Distributed MapReduce Algorithms for k-Center Clustering”. In:
SPAA. 65–67.
Im, S. and B. Moseley. (2019). “A Conditional Lower Bound on Graph
Connectivity in MapReduce”. arXiv: 1904.08954.
Im, S., B. Moseley, and X. Sun. (2017). “Efficient massively parallel
methods for dynamic programming”. In: STOC. 798–811.
Indyk, P., S. Mahabadi, M. Mahdian, and V. S. Mirrokni. (2014).
“Composable core-sets for diversity and coverage maximization”. In:
PODS. 100–108.
Jacob, R., T. Lieber, and N. Sitchinava. (2014). “On the complexityof list ranking in the parallel external memory model”. In: MFCS.
384–395.
Karloff, H., S. Suri, and S. Vassilvitskii. (2010). “A Model of Computation for MapReduce”. In: SODA. 938–948.
Koutris, P., S. Salihoglu, and D. Suciu. (2018). “Algorithmic Aspectsof Parallel Data Processing”. Foundations and Trends in Databases.
8(4): 239–370.
Kumar, R., B. Moseley, S. Vassilvitskii, and A. Vattani. (2015). “Fast
Greedy Algorithms in MapReduce and Streaming”. TOPC. 2(3):
14:1–14:22.
Lattanzi, S., T. Lavastida, K. Lu, and B. Moseley. (2019). “A frameworkfor parallelizing hierarchical clustering methods”. In: ECML/PKDD.
73–89.
Lattanzi, S., B. Moseley, S. Suri, and S. Vassilvitskii. (2011). “Filtering:a method for solving graph problems in MapReduce”. In: SPAA.
85–94.
Lenzen, C. and R. Wattenhofer. (2010). “Brief announcement: exponential speed-up of local algorithms using non-local communication”.
In: PODC. 295–296.

416

References

Linial, N. (1987). “Distributive graph algorithms global solutions fromlocal data”. In: FOCS. 331–335.
Malkomes, G., M. J. Kusner, W. Chen, K. Q. Weinberger, and B.
Moseley. (2015). “Fast Distributed k-Center Clustering with Outlierson Massive Data”. In: NIPS. 1063–1071.
McGregor, A. (2014). “Graph stream algorithms: a survey”. SIGMOD
Record. 43(1): 9–20.
Mirzasoleiman, B., A. Karbasi, R. Sarkar, and A. Krause. (2013). “Distributed Submodular Maximization: Identifying Representative Elements in Massive Data”. In: NIPS. 2049–2057.
Mitzenmacher, M. and E. Upfal. (2005). Probability and Computing:Randomized Algorithms and Probabilistic Analysis. Cambridge University Press.
Nemhauser, G. L., L. A. Wolsey, and M. L. Fisher. (1978). “An Analysis
of Approximations for Maximizing Submodular Set Functions–I”.
Math. Program. 14(1): 265–294.
Park, H.-M., F. Silvestri, U. Kang, and R. Pagh. (2014). “MapReduce
Triangle Enumeration With Guarantees”. In: CIKM. 1739–1748.
Pietracaprina, A., G. Pucci, M. Riondato, F. Silvestri, and E. Upfal.
(2012). “Space-round Tradeoffs for MapReduce Computations”. In:
ICS. 235–244.
Ponte Barbosa, R. da, A. Ene, H. L. Nguyen, and J. Ward. (2015). “ThePower of Randomization: Distributed Submodular Maximization on
Massive Datasets”. In: ICML. Vol. 37. 1236–1244.
Ponte Barbosa, R. da, A. Ene, H. L. Nguyen, and J. Ward. (2016).
“A New Framework for Distributed Submodular Maximization”. In:
FOCS. 645–654.
Roughgarden, T., S. Vassilvitskii, and J. T. Wang. (2016). “Shuffles andCircuits (On Lower Bounds on Massively Parallel Computation)”.
In: SPAA ’16.
Suri, S. and S. Vassilvitskii. (2011). “Counting triangles and the curseof the last reducer”. In: WWW. 607–614.
Valiant, L. G. (1990). “A bridging model for parallel computation”.
CACM. 33(8): 103–111.
Williamson, D. P. and D. B. Shmoys. (2011). The Design of Approximation Algorithms. Cambridge University Press.

References

417

Zhao, Z., G. Wang, A. Butt, M. Khan, V. Kumar, and M. Marathe.
(2012). “SAHAD: Subgraph Analysis in Massive Networks Using
Hadoop”. In: IPDPS. 390–401.