We consider the problem of coded distributed computing using polar codes. The average execution time of a coded computing system is related to the error probability for transmission over the binary erasure channel in recent work by Soleymani, Jamali and Mahdavifar, where the performance of binary linear codes is investigated. In this paper, we focus on polar codes and unveil a connection between the average execution time and the scaling exponent $\mu$ of the family of codes. The scaling exponent has emerged as a central object in the finite-length characterization of polar codes, and it captures the speed of convergence to capacity. In particular, we show that (i) the gap between the normalized average execution time of polar codes and that of optimal MDS codes is $O(n^{-1/\mu})$, and (ii) this upper bound can be improved to roughly $O(n^{-1/2})$ by considering polar codes with large kernels. We conjecture that these bounds could be improved to $O(n^{-2/\mu})$ and $O(n^{-1})$, respectively, and provide a heuristic argument as well as numerical evidence supporting this view.
翻译:我们考虑使用极地代码进行编码分布式计算的问题。 编码计算系统的平均执行时间与Soleymani、 Jamali 和 Mahdavifar最近调查二进制线性代码的性能的测试工作在二进制消化频道上传输的误差概率有关。 在本文中, 我们关注极地代码, 并揭开平均执行时间与代码家庭缩放速率( $$ mu$) 之间的联系。 缩放速率在极地代码的有限长度定性中已经成为一个核心对象, 并捕捉到与能力趋同的速度。 特别是, 我们显示 (一) 极地代码的正常平均执行时间与最佳MDS代码之间的差额是$( ⁇ -1/\\ mu} $, 以及 (二) 通过考虑极地代码与大内核的比值, 这个上限可以改进到大约$ O( ⁇ -1/2} 。 我们推测这些约束可以改进为$( ⁇ 2/\ mu} 和 $O ( n%-1} 和 $ O( -1} ) 提供数字论证。