The DOI matches its Crossref record; 52 of the 52 references it cites were found in a registry or an index.
A Fundamental Tradeoff Between Computation and Communication in Distributed Computing
Abstract
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.
Overview
The claims and statistics of this paper haven’t been checked yet.
Run the check — free, no account needed. It reads the open-access text and checks the sources it cites.
Integrity signals
Registry
Cites
Statistics
Verification
Claims the paper makes
The claims and statistics of this paper haven’t been checked yet.
Run the check — free, no account needed. It reads the open-access text and checks the sources it cites.
Self-check
Percentages, sums and reported differences re-computed from the paper’s own numbers.
The self-check needs the paper’s full text.
Citations
Cites
Ahlswede, R., Cai, N., Li, S.-Y. R., & Yeung, R. W. (2000) · IEEE Transactions on Information Theory · doi:10.1109/18.850663 · Cited by 7,814
Self-citationFog computing and its role in the internet of things
Bonomi, F., Milito, R., Zhu, J., & Addepalli, S. (2012) · Proceedings of the first edition of the MCC workshop on Mobile cloud computing · doi:10.1145/2342509.2342513 · Cited by 6,244
Ghemawat, S., Gobioff, H., & Leung, S.-T. (2003) · ACM SIGOPS Operating Systems Review · doi:10.1145/1165389.945450 · Cited by 4,984
(2010) · Cited by 4,411
A scalable, commodity data center network architecture
Al-Fares, M., Loukissas, A., & Vahdat, A. (2008) · ACM SIGCOMM Computer Communication Review · doi:10.1145/1402946.1402967 · Cited by 3,175
MapReduce: Simplified Data Processing on Large Cluster
Senior Software Developer, A. U., & Dayalan, M. (2018) · International Journal of Research and Engineering · doi:10.21276/ijre.2018.5.5.4 · Cited by 2,948
Dryad: distributed data-parallel programs from sequential building blocks
Isard, M., Budiu, M., Yu, Y., Birrell, A., & Fetterly, D. (2007) · Proceedings of the 2nd ACM SIGOPS/EuroSys European Conference on Computer Systems 2007 · doi:10.1145/1272996.1273005 · Cited by 2,432
Fog and IoT: An Overview of Research Opportunities
Chiang, M., & Zhang, T. (2016) · IEEE Internet of Things Journal · doi:10.1109/jiot.2016.2584538 · Cited by 2,362
An algebraic approach to network coding
Koetter, R., & Medard, M. (2003) · IEEE/ACM Transactions on Networking · doi:10.1109/tnet.2003.818197 · Cited by 2,356
Rajaraman, A., & Ullman, J. D. (2011) · Cambridge University Press eBooks · doi:10.1017/cbo9781139058452 · Cited by 2,262
Research works printed but not linked: 10
- 2017, Open MPI Open Source High Performance Computing
- 10.1109/ISIT.2003.1228459 · doi:10.1109/isit.2003.1228459
- kiamari, 2017, On heterogeneous coded distributed computing
- 2017, Apache Hadoop Distributed File System
- 2017, Amazon Elastic Compute Cloud (Amazon EC2)
- 2017, Hadoop TeraSort
- 10.1109/18.50368 · doi:10.1109/18.50368
- 10.1145/288090.288094 · doi:10.1145/288090.288094
- 10.1109/CLOUD.2013.107 · doi:10.1109/cloud.2013.107
- 10.1109/e-Science.2009.53 · doi:10.1109/e-science.2009.53
Cited by
Edge artificial intelligence for 6g: vision, enabling technologies, and applications
Letaief, K. B., Shi, Y., Lu, J., & Lu, J. (2022) · IEEE Journal on Selected Areas in Communications · doi:10.1109/jsac.2021.3126076 · Cited by 829
“To tackle the communication bottleneck for shuffling intermediate values in the edge device distributed inference process, a coded distributed computing approach [223] was adopted in [221] to improve the scalability of wireless MapReduce by inducing the coded multicasting transmission opportunities.”
MethodCommunication-efficient edge ai: algorithms and systems
Shi, Y., Yang, K., Jiang, T., Zhang, J., & Letaief, K. B. (2020) · IEEE Communications Surveys & Tutorials · doi:10.1109/comst.2020.3007787 · Cited by 488
On the Optimal Recovery Threshold of Coded Matrix Multiplication
Dutta, S., Fahim, M., Haddadpour, F., Jeong, H., Cadambe, V., & Grover, P. (2020) · IEEE Transactions on Information Theory · doi:10.1109/tit.2019.2929328 · Cited by 282
Data Shuffling in Wireless Distributed Computing via Low-Rank Optimization
Yang, K., Shi, Y., & Ding, Z. (2019) · IEEE Transactions on Signal Processing · doi:10.1109/tsp.2019.2912139 · Cited by 43
Slow and Stale Gradients Can Win the Race
Dutta, S., Wang, J., & Joshi, G. (2021) · IEEE Journal on Selected Areas in Information Theory · doi:10.1109/jsait.2021.3103770 · Cited by 40
Metadata
- Authors
- Li, S., Maddah-Ali, M. A., Yu, Q., & Avestimehr, A. S.
- Venue
- IEEE Transactions on Information Theory
- Published
- 2018-01
- Volume
- 64
- Issue
- 1
- Pages
- 109-128
- ISSN
- 0018-9448 (ISSN-L)
- 1557-9654
- OpenAlex
- W2757498728
- Cited by
- 451
- References
- 52
- FWCI
- 97.30
- Type
- journal article
- Language
- en
- Open access
- closed
- Licence
- Funders
- NSF (CCF-1408639, NETS-1419632)
- ONR (N000141612189)
- NSA (H98230-16-C-0255)
- Intel
- Defense Advanced Research Projects Agency (HR001117C0053)
About these checks
Registry, retraction, Cites and statistics results are computed, not judged, with one exception: a printed reference that no index lists is read once by a model before it counts as a citation error. Claims are extracted by a model and kept only when their quote appears verbatim in the text; each cited source is then checked, with a model’s help, for whether it says what the claim relies on. Those verdicts can be wrong — read the claim’s quote and the cited source before relying on one.
Statistics and arithmetic are recomputed, not judged.
Confidence bands are shown only for fields calibrated on our annotated test set. None is calibrated yet, so no band is shown.
What counts as a claim ›How we measure confidence ›How we check this ›
Are you an author, or do you see a problem with this page? Request a review
How to cite
Cite CoChat for the checks on this page, and the paper for its own findings.
- This page
- CoChat. (2026). Citation check: A Fundamental Tradeoff Between Computation and Communication in Distributed Computing. https://app.cochat.ai/papers/10.1109/tit.2017.2756959
- The paper
- Li, S., Maddah-Ali, M. A., Yu, Q., & Avestimehr, A. S. (2018). A Fundamental Tradeoff Between Computation and Communication in Distributed Computing. IEEE Transactions on Information Theory. https://doi.org/10.1109/tit.2017.2756959
Data sources
Bibliographic data: Semantic Scholar, OpenAlex, Crossref.
Contains information from the Semantic Scholar Academic Graph Datasets, made available under the ODC Attribution License (ODC-BY 1.0).
Semantic Scholar’s data is described in: Kinney, R., et al. (2023). The Semantic Scholar Open Data Platform. arXiv:2301.10140.
