The DOI matches its Crossref record; 44 of the 44 references it cites were found in a registry or an index.
“Short-Dot”: Computing Large Linear Transforms Distributedly Using Coded Short Dot Products
Open accessAbstract
We consider the problem of computing a matrix-vector product Ax using a set of P parallel or distributed processing nodes prone to “straggling,” i.e., unpredictable delays. Every processing node can access only a fraction (s/N) of the N-length vector x, and all processing nodes compute an equal number of dot products. We propose a novel error correcting code-that we call “Short-Dot”-that introduces redundant, shorter dot products such that only a subset of the nodes' outputs are sufficient to compute Ax. To address the problem of straggling in computing matrix-vector products, prior work uses replication or erasure coding to encode parts of the matrix A, but the length of the dot products computed at each processing node is still N. The key novelty in our work is that instead of computing the long dot products as required in the original matrix-vector product, we construct a larger number of redundant and short dot products that only require a fraction of x to be accessed during the computation. Short-Dot is thus useful in a communication-constrained scenario as it allows for only a fraction of x to be accessed by each processing node. Further, we show that in the particular regime where the number of available processing nodes is greater than the total number of dot products, Short-Dot has lower expected computation time under straggling under an exponential model compared to existing strategies, e.g. replication, in a scaling sense. We also derive fundamental limits on the trade-off between the length of the dot products and the recovery threshold, i.e., the required number of processing nodes, showing that Short-Dot is near-optimal.
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
Decoding by Linear Programming
Candes, E. J., & Tao, T. (2005) · IEEE Transactions on Information Theory · doi:10.1109/tit.2005.858979 · Cited by 7,121
The Hadoop Distributed File System
Shvachko, K., Kuang, H., Radia, S., & Chansler, R. (2010) · 2010 IEEE 26th Symposium on Mass Storage Systems and Technologies (MSST) · doi:10.1109/msst.2010.5496972 · Cited by 4,834
Gaussian elimination is not optimal
Strassen, V. (1969) · Numerische Mathematik · doi:10.1007/bf02165411 · Cited by 2,509
Dean, J., & Barroso, L. A. (2013) · Communications of the ACM · doi:10.1145/2408776.2408794 · Cited by 1,852 · cited 1×
“A common problem in distributed systems is “straggling” [10] where a few slow or faulty processing nodes (stragglers) can delay the entire computation.”
BackgroundAlgorithm-Based Fault Tolerance for Matrix Operations
Huang, K.-H., & Abraham, J. A. (1984) · IEEE Transactions on Computers · doi:10.1109/tc.1984.1676475 · Cited by 1,283
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
Channel Codes: Classical and Modern
Ryan, W., & Lin, S. (2009) · Cambridge University Press eBooks · doi:10.1017/cbo9780511803253 · Cited by 778
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
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
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
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
On the Delay-Storage Trade-Off in Content Download from Coded Distributed Storage Systems
Joshi, G., Liu, Y., & Soljanin, E. (2014) · IEEE Journal on Selected Areas in Communications · doi:10.1109/jsac.2014.140518 · Cited by 186
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
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
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
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 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
A Unified Coded Deep Neural Network Training Strategy based on Generalized PolyDot codes
Dutta, S., Bai, Z., Jeong, H., Low, T. M., & Grover, P. (2018) · IEEE International Symposium on Information Theory (ISIT) · doi:10.1109/isit.2018.8437852 · Cited by 103
Self-citationCodes can reduce queueing delay in data centers
Huang, L., Pawar, S., Zhang, H., & Ramchandran, K. (2012) · IEEE International Symposium on Information Theory (ISIT) · doi:10.1109/isit.2012.6284026 · Cited by 99
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
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
Self-citationYu, Q., Maddah-Ali, M. A., & Avestimehr, A. S. (2017) · Allerton Conference on Communication, Control, and Computing · doi:10.1109/allerton.2017.8262778 · Cited by 65
The MDS Queue: Analysing the Latency Performance of Erasure Codes
Lee, K., Shah, N. B., Huang, L., & Ramchandran, K. (2017) · IEEE Transactions on Information Theory · doi:10.1109/tit.2017.2674671 · Cited by 63
Straggler-Proofing Massive-Scale Distributed Matrix Multiplication with D-Dimensional Product Codes
Baharav, T. Z., Lee, K., Öçal, O., & Ramchandran, K. (2018) · IEEE International Symposium on Information Theory (ISIT) · doi:10.1109/isit.2018.8437549 · Cited by 62
Encoded distributed optimization
Karakus, C., Sun, Y., & Diggavi, S. N. (2017) · IEEE International Symposium on Information Theory (ISIT) · doi:10.1109/isit.2017.8007058 · Cited by 55
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
Energy-Aware Sensor Selection in Field Reconstruction
Liu, S., Vempaty, A., Fardad, M., Maşazade, E., & Varshney, P. K. (2014) · IEEE Signal Processing Letters · doi:10.1109/lsp.2014.2342198 · Cited by 44
Supercomputing's monster in the closet
Geist, A. (2016) · IEEE Spectrum · doi:10.1109/mspec.2016.7420396 · Cited by 44
Latency 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
Effective 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
Efficient task replication for fast response times in parallel computation
Wang, D., Joshi, G., & Wornell, G. W. (2014) · ACM SIGMETRICS Performance Evaluation Review · doi:10.1145/2637364.2592042 · Cited by 40
Straggler Mitigation by Delayed Relaunch of Tasks
Aktaş, M. F., Peng, P., & Soljanin, E. (2018) · ACM SIGMETRICS Performance Evaluation Review · doi:10.1145/3199524.3199564 · Cited by 39
Fault- Tolerant Dot-Product Engines
Roth, R. M. (2018) · IEEE Transactions on Information Theory · doi:10.1109/isit.2018.8437919 · Cited by 37
Fast and Efficient Distributed Matrix-vector Multiplication Using Rateless Fountain Codes
Mallick, A., Chaudhari, M., & Joshi, G. (2019) · IEEE International Conference on Acoustics Speech and Signal Processing · doi:10.1109/icassp.2019.8682347 · Cited by 35
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
Distributed Solution of Large-Scale Linear Systems Via Accelerated Projection-Based Consensus
Azizan, N., Lahouti, F., Avestimehr, S., & Hassibi, B. (2018) · IEEE Transactions on Signal Processing · doi:10.1109/tsp.2019.2917855 · Cited by 31
Communication costs of Strassen's matrix multiplication
Ballard, G., Demmel, J. W., Holtz, O., & Schwartz, O. (2014) · Communications of the ACM · doi:10.1145/2556647.2556660 · Cited by 20
Masterless Coded Computing: A Fully-Distributed Coded FFT Algorithm
Jeong, H., Low, T. M., & Grover, P. (2018) · Allerton Conference on Communication, Control, and Computing · doi:10.1109/allerton.2018.8636047 · Cited by 18
Self-citationFault-tolerant distributed logistic regression using unreliable components
Yang, Y. L., Grover, P., & Kar, S. (2016) · Allerton Conference on Communication, Control, and Computing · doi:10.1109/allerton.2016.7852335 · Cited by 17
Self-citationCross-Iteration Coded Computing
Haddadpour, F., Yang, Y. L., Cadambe, V. R., & Grover, P. (2018) · Allerton Conference on Communication, Control, and Computing · doi:10.1109/allerton.2018.8635933 · Cited by 17
Self-citationEnergy-efficient dot product computation using a switched analog circuit architecture
Nahlus, I., Kim, E. P., Shanbhag, N. R., & Blaauw, D. T. (2014) · International Symposium on Low Power Electronics and Design (ISLPED) · doi:10.1145/2627369.2627664 · Cited by 13
Coding for a Single Sparse Inverse Problem
Yang, Y. L., Grover, P., & Kar, S. (2018) · IEEE International Symposium on Information Theory (ISIT) · doi:10.1109/isit.2018.8437459 · Cited by 13
Self-citationOn the arithmetic operational complexity for solving Vandermonde linear equations
Li, L. (2000) · Japan Journal of Industrial and Applied Mathematics · doi:10.1007/bf03167332 · Cited by 12
Cited by
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
FedPAQ: A Communication-Efficient Federated Learning Method with Periodic Averaging and Quantization
Reisizadeh, A., Mokhtari, A., Hassani, H., Jadbabaie, A., & Pedarsani, R. (2019) · arXiv · doi:10.48550/arxiv.1909.13014 · Cited by 587
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
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
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
Metadata
- Authors
- Dutta, S., Cadambe, V., & Grover, P.
- Venue
- IEEE Transactions on Information Theory
- Published
- 2019-10
- Volume
- 65
- Issue
- 10
- Pages
- 6171-6193
- ISSN
- 0018-9448 (ISSN-L)
- 1557-9654
- OpenAlex
- W2556205507
- Cited by
- 313
- References
- 44
- FWCI
- 26.99
- Type
- journal article
- 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.