Treffer: New Results on the Computation-Communication Tradeoff for Heterogeneous Coded Distributed Computing.

Coded distributed computing (CDC) can alleviate the communication load in distributed computing systems by leveraging coding opportunities via redundant computation. While the optimal computation-communication tradeoff has been well studied for homogeneous systems, it remains largely unknown for heterogeneous systems where workers have different computation capabilities. This paper characterizes the upper and lower bounds of the optimal communication load as two linear programming problems for a general heterogeneous CDC system using the MapReduce framework. Our achievable scheme first designs a parametric data shuffling strategy for any given mapping strategy, and then jointly optimizes the mapping strategy and the data shuffling strategy to obtain the upper bound. The parametric data shuffling strategy allows adjusting the size of the multicast message intended for each worker set, so that it can largely decrease the number of unicast messages and hence increase the communication efficiency. Numerical results show that our achievable communication load is lower than those achieved in existing works. Our lower bound is established by unifying an improved cut-set bound and a peeling method. The obtained upper and lower bounds degenerate to the existing result in homogeneous systems, and coincide with each other when the system is approximately homogeneous or grouped homogeneous. [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.)