A Fundamental Tradeoff Between Computation and Communication in Distributed Computing

By Songze Li, Mohammad Ali Maddah-Ali, Qian Yu, Amir Salman Avestimehr. 2016

504 citations recorded by the source corpus.

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 <italic>inversely proportional</italic> 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 <inline-formula> <tex-math notation="LaTeX">$r$ </tex-math></inline-formula> (i.e., evaluating each function at <inline-formula> <tex-math notation="LaTeX">$r$ </tex-math></inline-formula> <italic>carefully chosen</italic> 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 <monospace>TeraSort</monospace> benchmark to develop a novel <monospace>CodedTeraSort</monospace> algorithm, which is empirically demonstrated to speed up the overall job execution by <inline-formula> <tex-math notation="LaTeX">$1.97\times $ </tex-math></inline-formula> – <inline-formula> <tex-math notation="LaTeX">$3.39\times $ </tex-math></inline-formula>, for typical settings of interest.

Subfields: Artificial Intelligence, Computer Networks and Communications

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

In Artificial Intelligence

In Computer Networks and Communications

Citations in the corpus

Speeding Up Distributed Machine Learning Using Codes (2015, background): “In [28], Zaharia et al. propose a modification to the existing straggler detection algorithm and show that the proposed solution can effectively reduce the completion time of MapReduce tasks.”
Polynomial Codes: an Optimal Design for High-Dimensional Coded Matrix Multiplication (2017, background): “As a by-product, we can also prove that the polynomial code simultaneously achieves optimality in terms of several other performance metrics, including the computation latency [5, 10], the probability of failure given a deadline [9], and the communication load [16, 17, 18], as discussed in Section 3”
Improving Distributed Gradient Descent Using Reed-Solomon Codes (2017, methodology): “Despite the existence of a great set of tools developed in coding theory which can be used in many machine learning problems, researchers had not looked at this area until very recently [6], [1], [7], [8].”
Gradient Coding (2016, background): “We also mention Li et al. (2016a), which investigates a generalized view of the coding ideas in Lee et al. (2015), showing that their solution is a single operating point in a general scheme of trading off latency of computation to the load of communication.”
Coded Computing for Federated Learning at the Edge (2020, background): “Related Works: Coded computing is a new paradigm that has been developed for injecting computation redundancy in unorthodox encoded forms to efficiently deal with communication bottleneck and system disturbances like stragglers, outages, node failures, and adversarial computations in distributed sys”
Quantized Decentralized Consensus Optimization (2018, background): “Recently, a different line of work has proposed the use of coding theoretic techniques to alleviate the communication bottleneck in distributed computation [32]–[35].”
GASP Codes for Secure Distributed Matrix Multiplication (2018, background): “More fundamental questions about the trade-off in computation cost and communication cost in distributed computing were previously addressed in [12].”
The Capacity of Private Computation (2017, background): “Much recent effort is devoted to various computation tasks, such as search [1], [2], matrix multiplication [3], [4] and shufﬂing [3], [5] etc. Privacy is a concern when sensitive data sets are involved.”
Encoded distributed optimization (2017, background): “However, recently, distributed coded computing has received some attention from the information theory community [2], [3], [4], [5].”