Massively Parallel Computation: Algorithms and Applications

The 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 as building blocks to design new algorithms. The monograph is not exhaustive and includes topics such as partitioning and coresets, sample and prune, dynamic programming, round compression, 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.

• Publication year

  2023

• Venue

  Found. Trends Optim.

• Publication date

  Unknown publication date

• Fields of study

  Computer Science, Engineering

• Identifiers
  DOI 10.1561/2400000025
• External record

  Open on Semantic Scholar

• Source metadata

  Semantic Scholar

• No claims are published for this paper.

• No concepts are published for this paper.

• Deterministic massively parallel connectivity

  2021influential reference
• Correlation Clustering in Constant Many Parallel Rounds

  2021cited by this paper
• Parallel and Efficient Hierarchical k-Median Clustering

  2021cited by this paper
• New lower bounds for Massively Parallel Computation from query complexity

  2020cited by this paper
• Conditional Hardness Results for Massively Parallel Computation from Distributed Lower Bounds

  2019cited by this paper
• Near-Optimal Massively Parallel Graph Connectivity

  2019cited by this paper
• A Framework for Parallelizing Hierarchical Clustering Methods

  2019cited by this paper
• Distributed Weighted Matching via Randomized Composable Coresets

  2019cited by this paper
• A Conditional Lower Bound on Graph Connectivity in MapReduce

  2019cited by this paper
• Exponentially Faster Massively Parallel Maximal Matching

  2019cited by this paper
• Improved Parallel Algorithms for Density-Based Network Clustering

  2019cited by this paper
• Parallel and Streaming Algorithms for K-Core Decomposition

  2018cited by this paper
• The Complexity of (Δ+1) Coloring in Congested Clique, Massively Parallel Computation, and Centralized Local Computation

  2018cited by this paper
• Improved Massively Parallel Computation Algorithms for MIS, Matching, and Vertex Cover

  2018cited by this paper
• Algorithmic Aspects of Parallel Data Processing

  2018cited by this paper
• Parallel Graph Connectivity in Log Diameter Rounds

  2018cited by this paper
• Solving k-center Clustering (with Outliers) in MapReduce and Streaming, almost as Accurately as Sequentially

  2018cited by this paper
• Sparsifying Distributed Algorithms with Ramifications in Massively Parallel Computation and Centralized Local Computation

  2018cited by this paper
• Distributed Clustering via LSH Based Data Partitioning

  2018cited by this paper
• Coresets Meet EDCS: Algorithms for Matching and Vertex Cover on Massive Graphs

  2017cited by this paper
• Efficient massively parallel methods for dynamic programming

  2017cited by this paper
• Round compression for parallel matching algorithms

  2017cited by this paper
• Affinity Clustering: Hierarchical Clustering at Scale

  2017cited by this paper
• Fast and Better Distributed MapReduce Algorithms for k-Center Clustering

  2015influential reference
• A New Framework for Distributed Submodular Maximization

  2015cited by this paper
• Fast Distributed k-Center Clustering with Outliers on Massive Data

  2015cited by this paper
• Random Coordinate Descent Methods for Minimizing Decomposable Submodular Functions

  2015cited by this paper
• The Power of Randomization: Distributed Submodular Maximization on Massive Datasets

  2015cited by this paper
• Scalable K-Means by ranked retrieval

  2014cited by this paper
• On the Complexity of List Ranking in the Parallel External Memory Model

  2014cited by this paper
• Lessons from the Congested Clique applied to MapReduce

  2014cited by this paper
• Graph stream algorithms: a survey

  2014cited by this paper
• Composable core-sets for diversity and coverage maximization

  2014cited by this paper
• MapReduce Triangle Enumeration With Guarantees

  2014cited by this paper
• Communication steps for parallel query processing

  2013influential reference
• Parallel algorithms for geometric graph problems

  2013influential reference
• Fast greedy algorithms in mapreduce and streaming

  2013cited by this paper
• Scalable K-Means++

  2012cited by this paper
• A Lower Bound Technique for Communication on BSP with Application to the FFT

  2012cited by this paper
• Upper and Lower Bounds on the Cost of a Map-Reduce Computation

  2012cited by this paper
• Densest Subgraph in Streaming and MapReduce

  2012cited by this paper
• SAHAD: Subgraph Analysis in Massive Networks Using Hadoop

  2012cited by this paper
• Complexity Measures for Map-Reduce, and Comparison to Parallel Computing

  2012cited by this paper
• Sorting, Searching, and Simulation in the MapReduce Framework

  2011cited by this paper
• Filtering: a method for solving graph problems in MapReduce

  2011cited by this paper
• Counting triangles and the curse of the last reducer

  2011cited by this paper
• Space-round tradeoffs for MapReduce computations

  2011cited by this paper
• Fast clustering using MapReduce

  2011cited by this paper
• The Design of Approximation Algorithms

  2011cited by this paper
• A model of computation for MapReduce

  2010cited by this paper
• Max-cover in map-reduce

  2010cited by this paper
• Simulating Parallel Algorithms in the MapReduce Framework with Applications to Parallel Computational Geometry

  2010cited by this paper
• MapReduce: simplified data processing on large clusters

  2008influential reference
• On distributing symmetric streaming computations

  2008cited by this paper
• Probability and Computing: Randomized Algorithms and Probabilistic Analysis

  2005cited by this paper
• Cache-oblivious algorithms

  1999cited by this paper
• A bridging model for parallel computation

  1990cited by this paper
• Distributive graph algorithms Global solutions from local data

  1987cited by this paper
• Clustering to Minimize the Maximum Intercluster Distance

  1985cited by this paper
• An analysis of approximations for maximizing submodular set functions—I

  1978cited by this paper

• Maximal Palindromes in MPC: Simple and Optimal

  2025cites this paper
• Scaling Parallel Algorithms to Massive Datasets using Multi-SSD Machines

  2025cites this paper
• Fast attention mechanisms: a tale of parallelism

  2025cites this paper
• Benefits and Limitations of Communication in Multi-Agent Reasoning

  2025cites this paper
• TD-Orch: Scalable Load-Balancing for Distributed Systems with Applications to Graph Processing

  2025influential citation
• Fully Scalable MPC Algorithms for Euclidean k-Center

  2025cites this paper
• Complexity landscape for local certification

  2025cites this paper
• Density-Dependent Graph Orientation and Coloring in Scalable MPC

  2025cites this paper
• Fast and Accurate Fair k-Center Clustering in Doubling Metrics

  2024cites this paper
• One-layer transformers fail to solve the induction heads task

  2024cites this paper
• Positional Attention: Out-of-Distribution Generalization and Expressivity for Neural Algorithmic Reasoning

  2024cites this paper
• Fully Scalable MPC Algorithms for Clustering in High Dimension

  2023cites this paper