# A Fundamental Tradeoff between Computation and Communication in Distributed Computing

arXiv: https://arxiv.org/abs/1604.07086 · HTML: https://mlsanity.com/paper/1604.07086/

## Key facts

- Cited by 12 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 24 Apr 2016.

## Built on by (most cited first, 12 of 12)

- [Edge Artificial Intelligence for 6G: Vision, Enabling Technologies, and Applications](https://mlsanity.com/paper/2111.12444/) (2021)
- [Stochastic Coded Federated Learning with Convergence and Privacy Guarantees](https://mlsanity.com/paper/2201.10092/) (2022)
- [Robust Federated Learning with Connectivity Failures: A Semi-Decentralized Framework with Collaborative Relaying](https://mlsanity.com/paper/2202.11850/) (2022)
- [Optimal Expert Selection for Distributed Mixture-of-Experts at the Wireless Edge](https://mlsanity.com/paper/2503.13421/) (2025)
- [STSyn: Speeding Up Local SGD with Straggler-Tolerant Synchronization](https://mlsanity.com/paper/2210.03521/) (2022)
- [Information-Theoretic Decentralized Secure Aggregation with Passive Collusion Resilience](https://mlsanity.com/paper/2508.00596/) (2025)
- [Communication Efficient Distributed Learning over Wireless Channels](https://mlsanity.com/paper/2209.01682/) (2022)
- [Privacy-aware Berrut Approximated Coded Computing for Federated Learning](https://mlsanity.com/paper/2405.01704/) (2024)
- [Decentralized Kernel Ridge Regression Based on Data-Dependent Random Feature](https://mlsanity.com/paper/2405.07791/) (2024)
- [Adaptive Worker Grouping For Communication-Efficient and Straggler-Tolerant Distributed SGD](https://mlsanity.com/paper/2201.04301/) (2022)
- [Generalized Lagrange Coded Computing: A Flexible Computation-Communication Tradeoff for Resilient, Secure, and Private Computation](https://mlsanity.com/paper/2204.11168/) (2022)
- [MD-AirComp+: Adaptive Quantization for Blind Massive Digital Over-the-Air Computation](https://mlsanity.com/paper/2602.18332/) (2026)

## Abstract (arXiv)

How can we optimally trade extra computing power to reduce the communication load in distributed computing? We answer this question by characterizing a fundamental tradeoff between computation and communication in distributed computing, i.e., the two are inversely proportional to each other. More specifically, a general distributed computing framework, motivated by commonly used structures like MapReduce, is considered, where the overall computation is decomposed into computing a set of "Map" and "Reduce" functions distributedly across multiple computing nodes. A coded scheme, named "Coded Distributed Computing" (CDC), is proposed to demonstrate that increasing the computation load of the Map functions by a factor of r (i.e., evaluating each function at r carefully chosen nodes) can create novel coding opportunities that reduce the communication load by the same factor. An information-theoretic lower bound on the communication load is also provided, which matches the communication load achieved by the CDC scheme. As a result, the optimal computation-communication tradeoff in distributed computing is exactly characterized. Finally, the coding techniques of CDC is applied to the Hadoop TeraSort benchmark to develop a novel CodedTeraSort algorithm, which is empirically demonstrated to speed up the overall job execution by 1.97× - 3.39×, for typical settings of interest.