期刊
IEEE TRANSACTIONS ON INFORMATION THEORY
卷 67, 期 9, 页码 6266-6282出版社
IEEE-INST ELECTRICAL ELECTRONICS ENGINEERS INC
DOI: 10.1109/TIT.2021.3095909
关键词
Decoding; Encoding; Convolutional codes; Numerical stability; Complexity theory; Resilience; Matrix decomposition; Distributed computing; straggler; convolutional coding; Toeplitz matrix; Vandermonde matrix
资金
- National Science Foundation (NSF) [CCF-1718470, CCF-1910840]
In distributed matrix computations, the problem of stragglers can be addressed by a convolutional coding approach that offers optimal straggler resilience and numerical robustness. Another approach with slightly higher decoding complexity allows operation close to the storage capacity lower bound while its numerical robustness can be quantified theoretically. Extensive experiments on the AWS cloud platform support these claims.
Distributed matrix computations - matrix-matrix or matrix-vector multiplications - are well-recognized to suffer from the problem of stragglers (slow or failed worker nodes). Much of prior work in this area is (i) either sub-optimal in terms of its straggler resilience, or (ii) suffers from numerical problems, i.e., there is a blow-up of round-off errors in the decoded result owing to the high condition numbers of the corresponding decoding matrices. Our work presents a convolutional coding approach to this problem that removes these limitations. It is optimal in terms of its straggler resilience, and has excellent numerical robustness as long as the workers' storage capacity is slightly higher than the fundamental lower bound. Moreover, it can be decoded using a fast peeling decoder that only involves add/subtract operations. Our second approach has marginally higher decoding complexity than the first one, but allows us to operate arbitrarily close to the storage capacity lower bound. Its numerical robustness can be theoretically quantified by deriving a computable upper bound on the worst case condition number over all possible decoding matrices by drawing connections with the properties of large block Toeplitz matrices. All above claims are backed up by extensive experiments done on the AWS cloud platform.
作者
我是这篇论文的作者
点击您的名字以认领此论文并将其添加到您的个人资料中。
推荐
暂无数据