Back to Search
Start Over
A Fundamental Tradeoff Between Computation and Communication in Distributed Computing.
- Source :
-
IEEE Transactions on Information Theory . Jan2018, Vol. 64 Issue 1, p109-128. 20p. - Publication Year :
- 2018
-
Abstract
- 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 <monospace>TeraSort</monospace> benchmark to develop a novel <monospace>CodedTeraSort</monospace> algorithm, which is empirically demonstrated to speed up the overall job execution by $1.97\times $ – $3.39\times $ , for typical settings of interest. [ABSTRACT FROM PUBLISHER]
Details
- Language :
- English
- ISSN :
- 00189448
- Volume :
- 64
- Issue :
- 1
- Database :
- Academic Search Index
- Journal :
- IEEE Transactions on Information Theory
- Publication Type :
- Academic Journal
- Accession number :
- 126963959
- Full Text :
- https://doi.org/10.1109/TIT.2017.2756959