A New Combinatorial Coded Design for Heterogeneous Distributed Computing.
Saved in:
| Title: | A New Combinatorial Coded Design for Heterogeneous Distributed Computing. |
|---|---|
| Authors: | Woolsey, Nicholas1 nicholas.woolsey@utah.edu, Chen, Rong-Rong1 rchen@ece.utah.edu, Ji, Mingyue1 mingyue.ji@utah.edu |
| Source: | IEEE Transactions on Communications. Sep2021, Vol. 69 Issue 9, p5672-5685. 14p. |
| Subjects: | Heterogeneous distributed computing, Grid computing, Distributed computing |
| Abstract: | Coded Distributed Computing (CDC) introduced by Li et al. in 2015 offers an efficient approach to trade computing power to reduce the communication load in general distributed computing frameworks such as MapReduce and Spark. In particular, increasing the computation load in the Map phase by a factor of $r$ can create coded multicasting opportunities to reduce the communication load in the Shuffle phase by the same factor. However, the CDC scheme is designed for the homogeneous settings, where each node maps the same number of files and is assigned the same number of reduce functions. It requires an exponentially large number of input files (data batches), reduce functions and multicasting groups relative to the number of nodes to achieve the promised gain. We address the CDC limitations by proposing a novel CDC approach based on a combinatorial design, which accommodates heterogeneous networks and maintains a multiplicative computation-communication trade-off. In addition, the proposed approach requires an exponentially less number of input files compared to the original CDC scheme proposed by Li et al. Finally, we derive a new information theoretic converse for general heterogeneous CDC and show that the communication load of the proposed design is optimal within a constant factor. [ABSTRACT FROM AUTHOR] |
| Copyright of IEEE Transactions on Communications is the property of IEEE and its content may not be copied or emailed to multiple sites without the copyright holder's express written permission. Additionally, content may not be used with any artificial intelligence tools or machine learning technologies. However, users may print, download, or email articles for individual use. This abstract may be abridged. No warranty is given about the accuracy of the copy. Users should refer to the original published version of the material for the full abstract. (Copyright applies to all Abstracts.) | |
| Database: | Engineering Source |
Be the first to leave a comment!
