The DOI matches its Crossref record; 42 of the 42 references it cites were found in a registry or an index.
Coded computation over heterogeneous clusters
Open accessAbstract
In large-scale distributed computing clusters, such as Amazon EC2, there are several types of “system noise” that can result in major degradation of performance: system failures, bottlenecks due to limited communication bandwidth, latency due to straggler nodes, and so on. There have been recent results that demonstrate the impact of coding for efficient utilization of computation and storage redundancy to alleviate the effect of stragglers and communication bottlenecks in homogeneous clusters. In this paper, we focus on general heterogeneous distributed computing clusters consist of a variety of computing machines with different capabilities. We propose a coding framework for speeding up distributed computing in heterogeneous clusters by trading redundancy for reducing the latency of computation. In particular, we propose heterogeneous coded matrix multiplication (HCMM) algorithm for performing distributed matrix multiplication over heterogeneous clusters that are provably asymptotically optimal for a broad class of processing time distributions. Moreover, we show that HCMM is unboundedly faster than any uncoded scheme that partitions the total workload among the workers. To demonstrate how the proposed HCMM scheme can be applied in practice, we provide results from numerical studies and Amazon EC2 experiments comparing HCMM with three benchmark load allocation schemes-uniform uncoded, load-balanced uncoded, and uniform coded. In particular, in our numerical studies, HCMM achieves speedups of up to 73%, 56%, and 42%, respectively, over the three benchmark schemes mentioned earlier. Furthermore, we carry out experiments over Amazon EC2 clusters and demonstrate how HCMM can be combined with rateless codes with nearly linear decoding complexity. In particular, we show that HCMM combined with the Luby transform codes can significantly reduce the overall execution time. HCMM is found to be up to 61%, 46%, and 36% faster than the aforementioned three benchmark schemes, respectively. Additionally, we provide a generalization to the problem of optimal load allocation in heterogeneous settings, where we take into account the monetary costs associated with distributed computing clusters. We argue that HCMM is asymptotically optimal for budget-constrained scenarios as well. In particular, we characterize the minimum possible expected cost associated with a computation task over a given cluster of machines. Furthermore, we develop a heuristic algorithm for (HCMM) load allocation for the distributed implementation of budget-limited computation tasks.
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
Information theory, inference, and learning algorithms
(2004) · Choice Reviews Online · doi:10.5860/choice.41-5949 · Cited by 6,362
Fog 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
(2010) · Cited by 4,411
Dean, J., & Barroso, L. A. (2013) · Communications of the ACM · doi:10.1145/2408776.2408794 · Cited by 1,852
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
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
Self-citationThe cost of doing science on the cloud: the Montage example
Deelman, E., Singh, G., Livny, M., Berriman, G. B., & Good, J. (2008) · doi:10.5555/1413370.1413421 · Cited by 580
The cost of doing science on the cloud: The Montage example
Deelman, E., Singh, G., Livny, M., Berriman, B., & Good, J. (2008) · 2008 SC - International Conference for High Performance Computing, Networking, Storage and Analysis · doi:10.1109/sc.2008.5217932 · Cited by 483
A Fundamental Tradeoff Between Computation and Communication in Distributed Computing
Li, S., Maddah-Ali, M. A., Yu, Q., & Avestimehr, A. S. (2018) · IEEE Transactions on Information Theory · doi:10.1109/tit.2017.2756959 · Cited by 451
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
Dalcín, L., Paz, R., & Storti, M. (2005) · Journal of Parallel and Distributed Computing · doi:10.1016/j.jpdc.2005.03.010 · Cited by 408
Cost-benefit analysis of Cloud Computing versus desktop grids
Kondo, D., Javadi, B., Malecot, P., Cappello, F., & Anderson, D. P. (2009) · 2009 IEEE International Symposium on Parallel & Distributed Processing · doi:10.1109/ipdps.2009.5160911 · Cited by 351
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
“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
Non-asymptotic Theory of Random Matrices: Extreme Singular Values
Rudelson, M., & Vershynin, R. (2011) · Proceedings of the International Congress of Mathematicians 2010 (ICM 2010) · doi:10.1142/9789814324359_0111 · Cited by 296
Low Latency Geo-distributed Data Analytics
Pu, Q., Ananthanarayanan, G., Bodik, P., Kandula, S., Akella, A., Bahl, P., & Stoica, I. (2015) · Proceedings of the 2015 ACM Conference on Special Interest Group on Data Communication · doi:10.1145/2785956.2787505 · Cited by 246
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
Low Latency Geo-distributed Data Analytics
Pu, Q., Ananthanarayanan, G., Bodik, P., Kandula, S., Akella, A., Bahl, P., & Stoica, I. (2015) · ACM SIGCOMM Computer Communication Review · doi:10.1145/2829988.2787505 · Cited by 177
Cost-efficient task scheduling for executing large programs in the cloud
Su, S., Li, J., Huang, Q., et al. (2013) · Parallel Computing · doi:10.1016/j.parco.2013.03.002 · Cited by 167
Coding 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
Coded convolution for parallel and distributed computing within a deadline
Dutta, S., Cadambe, V. R., & Grover, P. (2017) · IEEE International Symposium on Information Theory (ISIT) · doi:10.1109/isit.2017.8006960 · Cited by 134
Li, 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
Using Straggler Replication to Reduce Latency in Large-scale Parallel Computing
Wang, D., Joshi, G., & Wornell, G. W. (2015) · ACM SIGMETRICS Performance Evaluation Review · doi:10.1145/2847220.2847223 · Cited by 126
Straggler Mitigation in Distributed Optimization Through Data EncodingPreprint
Karakus, C., Sun, Y., Diggavi, S. N., & Yin, W. (2017) · arXiv (Cornell University) · doi:10.48550/arxiv.1711.04969 · Cited by 118
Rateless Codes for Near-Perfect Load Balancing in Distributed Matrix-Vector Multiplication
Mallick, A., Chaudhari, M., Sheth, U., Palanikumar, G., & Joshi, G. (2019) · Proceedings of the ACM on Measurement and Analysis of Computing Systems · doi:10.1145/3366706 · Cited by 115
Straggler Mitigation in Distributed Matrix Multiplication: Fundamental Limits and Optimal Coding
Yu, Q., Maddah-Ali, M. A., & Avestimehr, A. S. (2018) · IEEE International Symposium on Information Theory (ISIT) · doi:10.1109/isit.2018.8437563 · Cited by 108
Block-Diagonal and LT Codes for Distributed Computing With Straggling Servers
Severinson, A., Amat, A. G. I., & Rosnes, E. (2018) · IEEE Transactions on Communications · doi:10.1109/tcomm.2018.2877391 · Cited by 97
Li, S., Maddah-Ali, M. A., & Avestimehr, A. S. (2015) · Cited by 93
On the optimal recovery threshold of coded matrix multiplication
Fahim, M., Jeong, H., Haddadpour, F., Dutta, S., Cadambe, V. R., & Grover, P. (2017) · Allerton Conference on Communication, Control, and Computing · doi:10.1109/allerton.2017.8262882 · Cited by 81
TOFEC: Achieving optimal throughput-delay trade-off of cloud storage using erasure codes
Liang, G., & Kozat, U. C. (2014) · doi:10.1109/infocom.2014.6848010 · Cited by 75
Anytime coding for distributed computation
Ferdinand, N. S., & Draper, S. C. (2016) · Allerton Conference on Communication, Control, and Computing · doi:10.1109/allerton.2016.7852337 · Cited by 53
Communication vs distributed computation: An alternative trade-off curve
Ezzeldin, Y. H., Karmoose, M., & Fragouli, C. (2017) · IEEE Information Theory Workshop (ITW) · doi:10.1109/itw.2017.8278011 · Cited by 46
Coded computation for multicore setups
Lee, K., Pedarsani, R., Papailiopoulos, D., & Ramchandran, K. (2017) · IEEE International Symposium on Information Theory (ISIT) · doi:10.1109/isit.2017.8006962 · Cited by 45
Self-citationLatency analysis of coded computation schemes over wireless networks
Reisizadeh, A., & Pedarsani, R. (2017) · Allerton Conference on Communication, Control, and Computing · doi:10.1109/allerton.2017.8262881 · Cited by 43
Self-citationEffective Straggler Mitigation: Which Clones Should Attack and When?
Aktas, M. F., Peng, P., & Soljanin, E. (2017) · ACM SIGMETRICS Performance Evaluation Review · doi:10.1145/3152042.3152047 · Cited by 43
Li, 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-citationFundamental Limits of Coded Linear TransformPreprint
Wang, S., Liu, J., Shroff, N. B., & Yang, P. (2018) · arXiv (Cornell University) · doi:10.48550/arxiv.1804.09791 · Cited by 36
Information Theoretic Limits of Data Shuffling for Distributed Learning
Attia, M. A., & Tandon, R. (2016) · Globecom · doi:10.1109/glocom.2016.7841903 · Cited by 34
Matrix sparsification for coded matrix multiplication
Suh, G., Lee, K., & Suh, C. (2017) · Allerton Conference on Communication, Control, and Computing · doi:10.1109/allerton.2017.8262883 · Cited by 33
Li, S., Supittayapornpong, S., Maddah-Ali, M. A., & Avestimehr, S. (2017) · Cited by 31
Self-citationA pliable index coding approach to data shuffling
Song, L., Fragouli, C., & Zhao, T. (2017) · IEEE International Symposium on Information Theory (ISIT) · doi:10.1109/isit.2017.8006991 · Cited by 25
Cited by
A survey on federated learning
Zhang, C., Xie, Y., Bai, H., Yu, B., Li, W., & Gao, Y. (2021) · Knowledge-Based Systems · doi:10.1016/j.knosys.2021.106775 · Cited by 1,899
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
Self-citationA Fundamental Tradeoff Between Computation and Communication in Distributed Computing
Li, S., Maddah-Ali, M. A., Yu, Q., & Avestimehr, A. S. (2018) · IEEE Transactions on Information Theory · doi:10.1109/tit.2017.2756959 · Cited by 451
Joint Device Scheduling and Resource Allocation for Latency Constrained Wireless Federated Learning
Shi, W., Zhou, S., Niu, Z., Jiang, M., & Geng, L. (2021) · IEEE Transactions on Wireless Communications · doi:10.1109/twc.2020.3025446 · Cited by 381
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
Metadata
- Authors
- Reisizadeh, A., Prakash, S., Pedarsani, R., & Avestimehr, S.
- Venue
- 2017 IEEE International Symposium on Information Theory (ISIT)
- Publisher
- IEEE
- Published
- 2017-06
- Volume
- 65
- Issue
- 7
- Pages
- 2408-2412
- OpenAlex
- W2582482048
- Cited by
- 268
- References
- 42
- FWCI
- 20.12
- Type
- conference paper
- Language
- en
- Open access
- green
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.