Factored LT and Factored Raptor Codes for Large-Scale Distributed Matrix Multiplication
Factored LT and Factored Raptor Codes for Large-Scale Distributed Matrix Multiplication
复制标题
DOI：
10.1109/isit44484.2020.9174314
复制
发表时间：
2020-06
期刊：
影响因子：
--
通讯作者：
Asit Kumar Pradhan;A. Heidarzadeh;Krishna R. Narayanan
中科院分区：
文献类型：
--
作者：
Asit Kumar Pradhan;A. Heidarzadeh;Krishna R. Narayanan
我们提出了两种编码方案的分散矩阵乘法的存在下的离散。这些编码方案是LT码和Raptor码对分布式矩阵乘法的适应，并且被称为因子化LT（FLT）码和因子化Raptor（FR）码。从经验上讲，我们表明，FLT码有一个接近最佳的恢复阈值时，工人节点的数量是非常大的，FR码有一个很好的恢复阈值，而工人节点的数量是适度的大。与乘积码相比，FLT和FR码具有更好的恢复阈值，并且与多项式码相比，预期它们具有更好的数值稳定性，同时它们也可以用低复杂度的解码算法来解码。
We propose two coding schemes for distributed matrix multiplication in the presence of stragglers. These coding schemes are adaptations of LT codes and Raptor codes to distributed matrix multiplication and are termed Factored LT (FLT) codes and Factored Raptor (FR) codes. Empirically, we show that FLT codes have a near-optimal recovery threshold when the number of worker nodes is very large, and that FR codes have an excellent recovery threshold while the number of worker nodes is moderately large. FLT and FR codes have better recovery thresholds when compared to Product codes and they are expected to have better numerical stability when compared to Polynomial codes, while they can also be decoded with a low-complexity decoding algorithm.