This paper develops coding techniques to reduce the running time of
distributed learning tasks. It characterizes the fundamental tradeoff to
compute gradients (and more generally vector summations) in terms of three
parameters: computation load, straggler tolerance and communication cost. It
further gives an explicit coding scheme that achieves the optimal tradeoff
based on recursive polynomial constructions, coding both across data subsets
and vector components. As a result, the proposed scheme allows to minimize the
running time for gradient computations. Implementations are made on Amazon EC2
clusters using Python with mpi4py package. Results show that the proposed
scheme maintains the same generalization error while reducing the running time
by $32\%$ compared to uncoded schemes and $23\%$ compared to prior coded
schemes focusing only on stragglers (Tandon et al., ICML 2017).

该论文提出了一种编码技术，以减少分布式学习任务的运行时间，并基于递归多项式结构提出了一种编码方案，优化了梯度计算的运行时间，同时保持相同泛化误差。

通信计算高效的梯度编码

Communication-Computation Efficient Gradient Coding

How can we optimally trade extra computing power to reduce the communication
load in distributed computing? We answer this question by characterizing a
fundamental tradeoff between computation and communication in distributed
computing, i.e., the two are inversely proportional to each other.
More specifically, a general distributed computing framework, motivated by
commonly used structures like MapReduce, is considered, where the overall
computation is decomposed into computing a set of "Map" and "Reduce" functions
distributedly across multiple computing nodes. A coded scheme, named "Coded
Distributed Computing" (CDC), is proposed to demonstrate that increasing the
computation load of the Map functions by a factor of $r$ (i.e., evaluating each
function at $r$ carefully chosen nodes) can create novel coding opportunities
that reduce the communication load by the same factor.
An information-theoretic lower bound on the communication load is also
provided, which matches the communication load achieved by the CDC scheme. As a
result, the optimal computation-communication tradeoff in distributed computing
is exactly characterized.
Finally, the coding techniques of CDC is applied to the Hadoop TeraSort
benchmark to develop a novel CodedTeraSort algorithm, which is empirically
demonstrated to speed up the overall job execution by $1.97\times$ -
$3.39\times$, for typical settings of interest.

本论文研究的问题是如何在分布式计算中，通过优化计算负载来降低通信负载，通过研究分布式计算中计算和通信之间的权衡关系，提出一种编码方案，命名为 “编码分布式计算”（CDC），该方案通过增加 Map 函数的计算负载来减少通信负载，实现了计算和通信的最优权衡。同时，将 CDC 的编码技术应用于 Hadoop TeraSort 基准测试中，开发出一种新的编码 TeraSort 算法，对实验中最常用的设置进行了验证，整个作业执行速度提高了 1.97 至 3.39 倍。