Title: Cascaded Coded Distributed Computing on Heterogeneous Networks,
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. For the more
general cascaded CDC, Map computations are repeated at $r$ nodes to
significantly reduce the communication load among nodes tasked with computing
$Q$ Reduce functions $s$ times. While an achievable cascaded CDC scheme was
proposed, it only operates on homogeneous networks, where the storage,
computation load and communication load of each computing node is the same. In
this paper, we address this limitation by proposing a novel combinatorial
design which operates on heterogeneous networks where nodes have varying
storage and computing capabilities. We provide an analytical characterization
of the computation-communication trade-off and show that it is optimal within a
constant factor and could outperform the state-of-the-art homogeneous schemes.