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.
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
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
Maddah-Ali, M. A., & Niesen, U. (2014) · IEEE Transactions on Information Theory · doi:10.1109/tit.2014.2306938 · Cited by 1,726 · cited 2×
“The idea of efficiently creating and exploiting coded multicasting was initially proposed in the context of cache networks in [20], [21], and extended in [22], [23], where caches prefetch part of the content in a way to enable coding during the content delivery, minimizing the network traffic.”
BackgroundMethodSelf-citation(2005) · Complexity Theory · doi:10.1007/3-540-27477-4_15 · Cited by 1,629
Improving MapReduce performance in heterogeneous environments
Zaharia, M., Konwinski, A., Joseph, A. D., Katz, R. H., & Stoica, I. G. (2008) · doi:10.5555/1855741.1855744 · Cited by 1,588
Map-Reduce for Machine Learning on Multicore
Chu, C.-T., Kim, S. K., Lin, Y.-A., Yu, Y., Bradski, G., Ng, A. Y., & Olukotun, K. (2007) · Advances in Neural Information Processing Systems 19 · doi:10.7551/mitpress/7503.003.0040 · Cited by 1,229
Some complexity questions related to distributive computing(Preliminary Report)
Yao, A. C.-C. (1979) · Proceedings of the eleventh annual ACM symposium on Theory of computing - STOC '79 · doi:10.1145/800135.804414 · Cited by 1,042
HadoopDB: an architectural hybrid of MapReduce and DBMS technologies for analytical workloads
Abouzeid, A., Bajda-Pawlikowski, K., Abadi, D., Silberschatz, A., & Rasin, A. (2009) · Proceedings of the VLDB Endowment · doi:10.14778/1687627.1687731 · Cited by 857
Speeding Up Distributed Machine Learning Using Codes
Lee, K., Lam, M., Pedarsani, R., Papailiopoulos, D., & Ramchandran, K. (2018) · IEEE Transactions on Information Theory · doi:10.1109/tit.2017.2736066 · Cited by 829
Computation Over Multiple-Access Channels
Nazer, B., & Gastpar, M. (2007) · IEEE Transactions on Information Theory · doi:10.1109/tit.2007.904785 · Cited by 753
Decentralized Coded Caching Attains Order-Optimal Memory-Rate Tradeoff
Maddah-Ali, M. A., & Niesen, U. (2015) · IEEE/ACM Transactions on Networking · doi:10.1109/tnet.2014.2317316 · Cited by 626
Self-citationFundamental Limits of Caching in Wireless D2D Networks
Ji, M., Caire, G., & Molisch, A. F. (2016) · IEEE Transactions on Information Theory · doi:10.1109/tit.2015.2504556 · Cited by 596
Dryad: distributed data-parallel programs from sequential building blocks
Isard, M., Budiu, M., Yu, Y., Birrell, A., & Fetterly, D. (2007) · ACM SIGOPS Operating Systems Review · doi:10.1145/1272998.1273005 · Cited by 556
Managing data transfers in computer clusters with orchestra
Chowdhury, M., Zaharia, M., Ma, J., Jordan, M. I., & Stoica, I. (2011) · Proceedings of the ACM SIGCOMM 2011 conference · doi:10.1145/2018436.2018448 · Cited by 543
Index Coding With Side Information
Bar-Yossef, Z., Birk, Y., Jayram, T. S., & Kol, T. (2011) · IEEE Transactions on Information Theory · doi:10.1109/tit.2010.2103753 · Cited by 498
Gradient Coding: Avoiding Stragglers in Distributed Learning
Tandon, R., Lei, Q., Dimakis, A. G., & Karampatziakis, N. (2017) · International Conference on Machine Learning · Cited by 431
How to encode the modulo-two sum of binary sources (Corresp.)
Korner, J., & Marton, K. (1979) · IEEE Transactions on Information Theory · doi:10.1109/tit.1979.1056022 · Cited by 355
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-citationBirk, Y., & Kol, T. (2006) · IEEE Transactions on Information Theory · doi:10.1109/tit.2006.874540 · Cited by 324
“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
Orlitsky, A., & Roche, J. R. (2001) · IEEE Transactions on Information Theory · doi:10.1109/18.915643 · Cited by 307
Managing data transfers in computer clusters with orchestra
Chowdhury, M., Zaharia, M., Ma, J., Jordan, M. I., & Stoica, I. (2011) · ACM SIGCOMM Computer Communication Review · doi:10.1145/2043164.2018448 · Cited by 305
Coded 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
High-dimensional coded matrix multiplication
Lee, K., Suh, C., & Ramchandran, K. (2017) · 2017 IEEE International Symposium on Information Theory (ISIT) · doi:10.1109/isit.2017.8006963 · Cited by 230
Tarazu: optimizing MapReduce on heterogeneous clusters
Ahmad, F., Chakradhar, S. T., Raghunathan, A., & Vijaykumar, T. N. (2012) · Proceedings of the seventeenth international conference on Architectural Support for Programming Languages and Operating Systems · doi:10.1145/2150976.2150984 · Cited by 224
Apache Tez: A Unifying Framework for Modeling and Building Data Processing Applications
Saha, B., Shah, H., Seth, S., Vijayaraghavan, G., Murthy, A., & Curino, C. (2015) · Proceedings of the 2015 ACM SIGMOD International Conference on Management of Data · doi:10.1145/2723372.2742790 · Cited by 193
A Unified Coding Framework for Distributed Computing with Straggling Servers
Li, S., Maddah-Ali, M. A., & Avestimehr, A. S. (2016) · 2016 IEEE Globecom Workshops (GC Wkshps) · doi:10.1109/glocomw.2016.7848828 · Cited by 175
Self-citationCoding for Distributed Fog Computing
Li, S., Maddah-Ali, M. A., & Avestimehr, A. S. (2017) · IEEE Communications Magazine · doi:10.1109/mcom.2017.1600894 · Cited by 138
Self-citationSpeeding up distributed machine learning using codes
Lee, K., Lam, M., Pedarsani, R., Papailiopoulos, D., & Ramchandran, K. (2016) · IEEE International Symposium on Information Theory (ISIT) · doi:10.1109/isit.2016.7541478 · Cited by 138
A Scalable Framework for Wireless Distributed Computing
Li, S., Yu, Q., Maddah-Ali, M. A., & Avestimehr, A. S. (2017) · IEEE/ACM Transactions on Networking · doi:10.1109/tnet.2017.2702605 · Cited by 134
Self-citationLi, S., Maddah-Ali, M. A., & Avestimehr, A. S. (2015) · Allerton Conference on Communication, Control, and Computing · doi:10.1109/allerton.2015.7447112 · Cited by 127
Self-citationiShuffle: Improving Hadoop Performance with Shuffle-on-Write
Guo, Y., Rao, J., Cheng, D., & Zhou, X. (2016) · IEEE Transactions on Parallel and Distributed Systems · doi:10.1109/tpds.2016.2587645 · Cited by 122
Li, S., Maddah-Ali, M. A., & Avestimehr, A. S. (2015) · Cited by 93
Self-citationKaramchandani, N., Niesen, U., Maddah-Ali, M. A., & Diggavi, S. N. (2014) · IEEE International Symposium on Information Theory (ISIT) · doi:10.1109/isit.2014.6875212 · Cited by 79
Self-citationAhmad, F., Chakradhar, S., Raghunathan, A., & Vijaykumar, T. N. (2012) · ACM SIGARCH Computer Architecture News · doi:10.1145/2189750.2150984 · Cited by 68
Fundamental tradeoff between computation and communication in distributed computing
Li, S., Maddah-Ali, M. A., & Avestimehr, A. S. (2016) · IEEE International Symposium on Information Theory (ISIT) · doi:10.1109/isit.2016.7541612 · Cited by 63
Self-citationCommunicating the Sum of Sources Over a Network
Ramamoorthy, A., & Langberg, M. (2013) · IEEE Journal on Selected Areas in Communications · doi:10.1109/jsac.2013.130404 · Cited by 59
iShuffle: Improving Hadoop Performance with Shuffle-on-Write
Guo, Y., Rao, J., & Zhou, X. (2013) · International Conference on Autonomic Computing · Cited by 54
How to optimally allocate resources for coded distributed computing?
Yu, Q., Li, S., Maddah-Ali, M. A., & Avestimehr, A. S. (2017) · International Conference on Communications · doi:10.1109/icc.2017.7996730 · Cited by 54
Self-citationCoded Distributed Computing: Straggling Servers and Multistage Dataflows
Li, S., Maddah-Ali, M. A., & Avestimehr, A. S. (2016) · Allerton Conference on Communication, Control, and Computing · doi:10.1109/allerton.2016.7852225 · Cited by 43
Self-citationLi, S., Supittayapornpong, S., Maddah-Ali, M. A., & Avestimehr, S. (2017) · IEEE International Symposium on Parallel & Distributed Processing, Workshops and Phd Forum · doi:10.1109/ipdpsw.2017.33 · Cited by 38
Self-citationLi, S., Supittayapornpong, S., Maddah-Ali, M. A., & Avestimehr, S. (2017) · Cited by 31
Self-citationCommunication-aware computing for edge processing
Li, S., Maddah-Ali, M. A., & Avestimehr, A. S. (2017) · IEEE International Symposium on Information Theory (ISIT) · doi:10.1109/isit.2017.8007057 · Cited by 29
Self-citationArchitectures for coded mobile edge computing
Li, S., Maddah-Ali, M. A., & Avestimehr, A. S. (2017) · IEEE Fog World Congress (FWC) · doi:10.1109/fwc.2017.8368530 · Cited by 6
Self-citation
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
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
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
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.