The DOI matches its Crossref record; 53 of the 53 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.
Free: it reads the open-access text and checks the first 5 claims that cite a source we can check. Create a free account to check every claim.
Integrity signals
Registry
Cites
Statistics
Verification
Claims the paper makes
The claims and statistics of this paper haven’t been checked yet.
Free: it reads the open-access text and checks the first 5 claims that cite a source we can check. Create a free account to check every claim.
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
MapReduce: simplified data processing on large clusters
Dean, J., & Ghemawat, S. (2008) · Communications of the ACM · doi:10.1145/1327452.1327492 · Cited by 18,476
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
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.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
Polynomial Codes: an Optimal Design for High-Dimensional Coded Matrix Multiplication
Yu, Q., Maddah-Ali, M. A., & Avestimehr, A. S. (2017) · arXiv (Cornell University) · doi:10.48550/arxiv.1705.10464 · Cited by 350
Self-citationMa, Z., Xiao, M., Xiao, Y., Pang, Z., Poor, H. V., & Vucetic, B. (2019) · IEEE Internet of Things Journal · doi:10.1109/jiot.2019.2907245 · Cited by 315
“Short-Dot”: Computing Large Linear Transforms Distributedly Using Coded Short Dot Products
Dutta, S., Cadambe, V., & Grover, P. (2019) · IEEE Transactions on Information Theory · doi:10.1109/tit.2019.2927558 · Cited by 313
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
The Exact Rate-Memory Tradeoff for Caching With Uncoded Prefetching
Yu, Q., Maddah-Ali, M. A., & Avestimehr, A. S. (2018) · IEEE Transactions on Information Theory · doi:10.1109/tit.2017.2785237 · Cited by 278
Self-citationCoded computation over heterogeneous clusters
Reisizadeh, A., Prakash, S., Pedarsani, R., & Avestimehr, S. (2017) · 2017 IEEE International Symposium on Information Theory (ISIT) · doi:10.1109/isit.2017.8006961 · Cited by 268
The Role of Caching in Future Communication Systems and Networks
Paschos, G. S., Iosifidis, G., Tao, M., Towsley, D., & Caire, G. (2018) · IEEE Journal on Selected Areas in Communications · doi:10.1109/jsac.2018.2844939 · Cited by 259
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
Multi-Level Over-the-Air Aggregation of Mobile Edge Computing Over D2D Wireless Networks
Wang, F., & Lau, V. K. N. (2022) · IEEE Transactions on Wireless Communications · doi:10.1109/twc.2022.3165658 · Cited by 21
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
- 53
- 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
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.