References & Further Reading
References
- S. Li, M. A. Maddah-Ali, Q. Yu, and A. S. Avestimehr, A Fundamental Tradeoff Between Computation and Communication in Distributed Computing, 2018
Foundational paper on coded MapReduce. Establishes the computation-communication tradeoff $L(r) = (1/r)(1 - r/K)$.
- R. Tandon, Q. Lei, A. G. Dimakis, and N. Karampatziakis, Gradient Coding: Avoiding Stragglers in Distributed Learning, 2017
Original gradient coding paper. Introduces redundancy for straggler tolerance in distributed ML.
- K. Lee, M. Lam, R. Pedarsani, D. Papailiopoulos, and K. Ramchandran, Speeding Up Distributed Machine Learning Using Codes, 2017
Coded matrix multiplication via Reed-Solomon codes. Straggler-tolerant distributed linear algebra.
- J. Dean and S. Ghemawat, MapReduce: Simplified Data Processing on Large Clusters, 2008
Original MapReduce paper from Google. Foundation of distributed analytics frameworks (Hadoop, Spark).
- J. Dean and L. A. Barroso, The Tail at Scale, 2013
Introduces the straggler problem at scale. Motivation for gradient coding and coded matmul.
- S. Li and M. A. Maddah-Ali, Coded Computing: Tutorial and Recent Advances, 2020
Canonical survey of coded computing, unifying coded caching, coded shuffling, coded MapReduce, and gradient coding.
- H. Joudeh and G. Caire, Coded Gradient Methods in Federated Learning, 2024
CommIT contribution: gradient coding for FL with heterogeneous client data. Integrates with differential privacy.
- M. A. Maddah-Ali and U. Niesen, Fundamental Limits of Caching, 2014
MAN scheme. Foundation for coded computing's combinatorial structure.
- K. Wan, D. Tuninetti, and G. Caire, Fundamental Limits of Distributed Data Shuffling, 2020
Coded data shuffling (Ch 15), the companion to coded MapReduce in the CommIT line.
- Q. Yu, M. A. Maddah-Ali, and A. S. Avestimehr, Polynomial Codes: an Optimal Design for High-Dimensional Coded Matrix Multiplication, 2017
Polynomial codes for coded matmul, improving on Lee et al.
- N. Raviv, R. Tandon, A. G. Dimakis, and I. Tamo, Gradient Coding from Cyclic MDS Codes and Expander Graphs, 2018
Cyclic MDS codes for gradient coding — improves on TLDK'17 with explicit constructions.
- S. Dutta, V. Cadambe, and P. Grover, Short-Dot: Computing Large Linear Transforms Distributedly Using Coded Short Dot Products, 2016
Coded distributed computation of large linear transforms — precursor to coded matmul.
Further Reading
Resources for deeper study of coded computing.
Coded computing tutorial
Li, Ali (2020). 'Coded Computing: Tutorial and Recent Advances,' Foundations and Trends
Canonical survey of coded-computing subfield. Bridges coded caching with distributed computing.
Original LMYA paper
Li, Maddah-Ali, Yu, Avestimehr (2018). 'A Fundamental Tradeoff...,' IEEE TIT
Core paper for §16.1-16.2. Full proof of the memory-computation tradeoff.
Gradient coding origin
Tandon, Lei, Dimakis, Karampatziakis (2017). 'Gradient Coding: Avoiding Stragglers,' ICML
§16.3 foundation. Original gradient coding construction and straggler-tolerance proof.
CommIT federated learning + coding
Joudeh, Caire (2024). 'Coded Gradient Methods in Federated Learning'
CommIT extension to FL setting with privacy integration.