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/jsait.2021.3103822
复制
发表时间：
2019-07
期刊：
影响因子：
--
通讯作者：
Asit Kumar Pradhan;A. Heidarzadeh;K. Narayanan
中科院分区：
文献类型：
--
作者：
Asit Kumar Pradhan;A. Heidarzadeh;K. Narayanan
我们提出了两种编码方案的分散矩阵乘法的存在下的离散。这些编码方案是吕比变换（LT）码和Raptor码对分布式矩阵乘法的适应，并且被称为因子LT（FLT）码和因子Raptor（FRT）码。我们证明了随机抽样码的坦纳图中的所有节点具有高概率的树状邻域。这确保了密度演化分析给出了FLT码的平均恢复阈值的合理估计。当输出度分布为孤立子时，所提出的FLT码的恢复门限是渐近最优的。经验上，我们表明，FRT代码有一个很好的恢复阈值，而工人节点的数量是适度大。此外，利用Azuma-Hoeffding不等式，我们推导出的浓度结果表明，一个随机选择的FLT码的恢复阈值是接近的系综平均值。与乘积码相比，FLT和FRT码具有更好的恢复阈值，并且与多项式码相比，预期它们具有更好的数值稳定性，同时它们也可以用低复杂度的解码算法解码。最后，建议的代码更好地匹配稀疏矩阵矩阵乘法的实际重要情况下，相比许多以前的计划。
We propose two coding schemes for distributed matrix multiplication in the presence of stragglers. These coding schemes are adaptations of Luby Transform (LT) codes and Raptor codes to distributed matrix multiplication and are termed Factored LT (FLT) codes and Factored Raptor (FRT) codes. We show that all nodes in the Tanner graph of a randomly sampled code have a tree-like neighborhood with high probability. This ensures that the density evolution analysis gives a reasonable estimate of the average recovery threshold of FLT codes. The recovery threshold of the proposed FLT codes is asymptotically optimal when the output degree distribution is Soliton. Empirically, we show that FRT codes have an excellent recovery threshold while the number of worker nodes is moderately large. In addition, using Azuma–Hoeffding inequality, we derive concentration results to show that the recovery threshold of a randomly chosen FLT code is close to the ensemble average. FLT and FRT 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. Finally, the proposed codes are better matched to the practically important case of sparse matrix-matrix multiplication as compared to many previous schemes.