We present a novel distributed computing framework that is robust to slow
compute nodes, and is capable of both approximate and exact computation of
linear operations. The proposed mechanism integrates the concepts of randomized
sketching and polar codes in the context of coded computation. We propose a
sequential decoding algorithm designed to handle real valued data while
maintaining low computational complexity for recovery. Additionally, we provide
an anytime estimator that can generate provably accurate estimates even when
the set of available node outputs is not decodable. We demonstrate the
potential applications of this framework in various contexts, such as
large-scale matrix multiplication and black-box optimization. We present the
implementation of these methods on a serverless cloud computing system and
provide numerical results to demonstrate their scalability in practice,
including ImageNet scale computations.

提出一种强大的分布式计算框架，通过随机化草图和极化码的概念，能够进行近似和精确的线性操作计算，并在实践中展示了其可扩展性。

随机极化码用于随时分布式机器学习

Randomized Polar Codes for Anytime Distributed Machine Learning

In a large-scale and distributed matrix multiplication problem
$C=A^{\intercal}B$, where $C\in\mathbb{R}^{r\times t}$, the coded computation
plays an important role to effectively deal with "stragglers" (distributed
computations that may get delayed due to few slow or faulty processors).
However, existing coded schemes could destroy the significant sparsity that
exists in large-scale machine learning problems, and could result in much
higher computation overhead, i.e., $O(rt)$ decoding time. In this paper, we
develop a new coded computation strategy, we call \emph{sparse code}, which
achieves near \emph{optimal recovery threshold}, \emph{low computation
overhead}, and \emph{linear decoding time} $O(nnz(C))$. We implement our scheme
and demonstrate the advantage of the approach over both uncoded and current
fastest coded strategies.

本文提出了一种名为 “sparse code” 的新的编码计算策略，旨在在大规模分布式矩阵乘法问题中处理分布式计算过程中的延迟问题和极高的计算损耗，实验结果证明了该策略比传统编码策略和未编码情况下的方法效果更好。

编码稀疏矩阵乘法

Coded Sparse Matrix Multiplication

We provide novel coded computation strategies for distributed matrix-matrix
products that outperform the recent "Polynomial code" constructions in recovery
threshold, i.e., the required number of successful workers. When $m$-th
fraction of each matrix can be stored in each worker node, Polynomial codes
require $m^2$ successful workers, while our MatDot codes only require $2m-1$
successful workers, albeit at a higher communication cost from each worker to
the fusion node. We also provide a systematic construction of MatDot codes.
Further, we propose "PolyDot" coding that interpolates between Polynomial codes
and MatDot codes to trade off communication cost and recovery threshold.
Finally, we demonstrate a coding technique for multiplying $n$ matrices ($n
\geq 3$) by applying MatDot and PolyDot coding ideas.

本文提出新的编码计算策略以用于分布式矩阵乘法，比最近的多项式编码中的恢复阈值更高，我们的 MatDot 编码只需要 2m-1 个成功的工作节点，而不是 m² 个，尽管会带来更高的通信代价。此外，我们还提出了 PolyDot 编码来权衡通信代价和恢复阈值，并通过应用 MatDot 和 PolyDot 编码思想，演示了一种用于矩阵乘法的编码技术。

编码矩阵乘法的最优恢复阈值

On the Optimal Recovery Threshold of Coded Matrix Multiplication

Building on the previous work of Lee et al. and Ferdinand et al. on coded
computation, we propose a sequential approximation framework for solving
optimization problems in a distributed manner. In a distributed computation
system, latency caused by individual processors ("stragglers") usually causes a
significant delay in the overall process. The proposed method is powered by a
sequential computation scheme, which is designed specifically for systems with
stragglers. This scheme has the desirable property that the user is guaranteed
to receive useful (approximate) computation results whenever a processor
finishes its subtask, even in the presence of uncertain latency. In this paper,
we give a coding theorem for sequentially computing matrix-vector
multiplications, and the optimality of this coding scheme is also established.
As an application of the results, we demonstrate solving optimization problems
using a sequential approximation approach, which accelerates the algorithm in a
distributed system with stragglers.

该研究提出了一种基于连续逼近的分布式计算框架，以解决优化问题，特别是针对最终价值计算过程中计算时间不相同（由于处理器延迟或者出错）的情况，其中矩阵 - 向量乘法的编码定理和优化方案也被探讨。