An Introduction to Distributed, Massively Parallel, and Local Computation Algorithms
summary
Introduces three concrete models and concrete translations: synchronous message‑passing measures rounds, giving Johansson’s randomized coloring that finishes in log n rounds (state‑of‑art ≈ log^2 log n, open whether ≪ log log n); a primal–dual fractional matching grows values multiplicatively in ≈ log Δ rounds and yields a 2+ε approximation; any r‑round distributed algorithm yields an LCA with roughly Δ^r queries; MPC uses edge sampling + centralized greedy to get a constant‑round MPC maximal matching when each machine has n^{1+Ω(1)} memory, while fully‑scalable best upper bound is ≈ √(log n) rounds and beating log log n / √(log n) remains open.
AI-written summary · about
chapters (8)
- 0:00Computation models overview
- 1:04Distributed algorithms basics
- 21:30Local computation algorithms
- 30:17Distributed vs local models
- 46:15MPC origins and memory
- 53:32MPC algorithms and bounds
- 1:09:23Techniques in models
- 1:17:35Open problems & Q&A
related talks
46mDistributed Graph Techniques in the MPC Model
31mNear-Optimal Distributed Implementations of Dynamic Algorithms for Symmetry Breaking Problems
29mTowards Scalable Constant-Round MPC from Minimal Assumptions via Round Collapsing
30mLocal Problems on Trees from the Perspectives of Distributed Algorithms, Finitary Factors, and Descr
47mMassively Parallel Evaluation of Relational Queries I
30mOn the Optimal Round Complexity of Multi-Party Computation in the Plain Model
53mMapReduce Algorithmics
31mSome Novel Computational Models to Think About