Slow running or straggler tasks can significantly reduce computation speed in
distributed computation. Recently, coding-theory-inspired approaches have been
applied to mitigate the effect of straggling, through embedding redundancy in
certain linear computational steps of the optimization algorithm, thus
completing the computation without waiting for the stragglers. In this paper,
we propose an alternate approach where we embed the redundancy directly in the
data itself, and allow the computation to proceed completely oblivious to
encoding. We propose several encoding schemes, and demonstrate that popular
batch algorithms, such as gradient descent and L-BFGS, applied in a
coding-oblivious manner, deterministically achieve sample path linear
convergence to an approximate solution of the original problem, using an
arbitrarily varying subset of the nodes at each iteration. Moreover, this
approximation can be controlled by the amount of redundancy and the number of
nodes used in each iteration. We provide experimental results demonstrating the
advantage of the approach over uncoded and data replication strategies.

本文提出了一种直接在数据中嵌入冗余来处理缓慢任务的新方法，通过一些编码技巧将复制数据的策略转换到线性计算过程中，从而利用节点的任意变化在没有等待慢节点的情况下完成散列计算，并通过实验结果表明此方法的优势。