Graph Algorithms in the MPC Model
summary
Describes a concrete design recipe that turns classic parallel primitives into MPC routines by combining graph sparsification plus simulation of PRAM/CONGEST, with careful load balancing via random hashing. Claims and proves that a broad class of graph problems run in polylogarithmic rounds while using near-linear memory per machine (O(n polylog n)) overall, and reports implemented reductions for connectivity and matching that match the theoretical round bounds and practical scalability on synthetic large graphs.
AI-written summary · about
chapters (7)
- 0:00Introduction to MPC
- 3:35Defining the MPC model
- 11:57Graph partitioning technique
- 18:54Primal-dual matching algorithm
- 26:26Randomized thresholding
- 36:28Algorithmic analysis
- 52:45Results and discussion
related talks
46mDistributed Graph Techniques in the MPC Model
30mThree Goals in Parallel Graph Computations: High Performance, High Productivity, and Reduced Comm...
35mSuperlinear Lower Bounds for Multipass Graph Processing
30mScalable Graph-Parallel Inference Algorithms and Systems
52mFine-Grained Complexity and Algorithm Design for Graph Reachability and Distance Problems
29mTowards Scalable Constant-Round MPC from Minimal Assumptions via Round Collapsing
58mCircuit Complexity and Connections I
29mAdaptive Massively Parallel Constant-round Tree Contraction