Efficient and Robust Distributed Matrix Computations via Convolutional Coding
Efficient and Robust Distributed Matrix Computations via Convolutional Coding
复制标题
DOI：
10.1109/tit.2021.3095909
复制
发表时间：
2019-07
影响因子：
2.5
通讯作者：
A. Das;A. Ramamoorthy;Namrata Vaswani
中科院分区：
文献类型：
--
作者：
A. Das;A. Ramamoorthy;Namrata Vaswani
分布式矩阵计算 - 矩阵 - 矩阵或矩阵矢量乘法 - 被众所周知遭受斗争的问题（慢速或失败的工人节点）。它的散曲弹性或（ii）遭受数值问题，即，由于相应的解码矩阵的高条件数量，解码结果中存在圆形错误。解决这些局限性的方法是最佳的。仅添加/减去操作的快速剥离解码器。通过在所有可能的解码材料上，通过与大块Toeplitz物品的属性绘制所有可能的解码材料，可以通过在所有可能的解码材料上得出可计算的上限，从而在理论上量化其数值鲁棒性。在AWS云平台上完成。
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.