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 倍。