Chapter Summary

Chapter Summary

Key Points

• 1.

  Coded MapReduce (LMYA 2018) extends MAN coded caching to distributed analytics. With per-file replication $r$, shuffle communication drops by factor $r$ — directly analogous to the caching gain $1 + t$.

• 2.

  Memory-communication-computation tradeoff. Extra compute (redundant map) substitutes for shuffle bandwidth. Optimal $r^* = \sqrt{T_\text{shuffle}/T_\text{map}}$ — non-trivial in compute-heavy workloads.

• 3.

  Gradient coding (Tandon-Lei-Dimakis-Karampatziakis 2017) tolerates $s$ stragglers at storage overhead $s+1$. Master decodes from any $K - s$ workers.

• 4.

  Coded matrix multiplication (Lee-Lam-Pedarsani-Papailiopoulos- Ramchandran 2017) uses Reed-Solomon / polynomial codes for straggler-tolerant matmul.

• 5.

  Distinct primitives for distinct goals. Coded MapReduce saves bandwidth; gradient coding saves latency. They compose but are not interchangeable.

• 6.

  CommIT contribution: Joudeh-Caire (2024) — coded gradient methods for federated learning, handling heterogeneous client data and integrating with privacy mechanisms.

• 7.

  Unified coded-computing framework. Coded caching, coded shuffling, coded MapReduce, gradient coding, coded matmul — all share the memory/storage ⇌ communication tradeoff, with different metrics and different combinatorial encodings.