Universal Coded Distributed Computing For MapReduce Frameworks

Coded distributed computing (CDC) can trade extra computing power to reduce the communication load for the MapReduce-type systems. The optimal computation-communication tradeoff has been well studied for homogeneous systems, and some results have also been obtained under the heterogeneous condition in recent studies. However, the previous works allow the file placement and Reduce function assignment free to design for the scheme. In this paper, we consider the general heterogeneous MapReduce system, where the file placement and Reduce function assignment are arbitrary but prefixed among all nodes (i.e., can not be designed by the scheme), and the storage and the computational capabilities for different nodes are not necessarily equal. We propose two {universal} CDC schemes and establish upper bounds of the optimal communication load. The first achievable scheme, namely One-Shot Coded Transmission (OSCT), encodes the intermediate values (IVs) into message blocks with different sizes to exploit the multicasting gain, and each message block can be decoded independently by the intended nodes. The second scheme, namely Few-Shot Coded Transmission (FSCT), splits IVs into smaller pieces and each node jointly decodes multiple message blocks to obtain its desired IVs. We prove that our OSCT and FSCT are optimal in many cases, and give sufficient conditions for the optimality of OSCT and FSCT, respectively.