Technical Program

Paper Detail

Paper Title Cascaded Coded Distributed Computing on Heterogeneous Networks
Paper IdentifierFR2.R2.2
Authors Nicholas Woolsey, Rong-Rong Chen, Mingyue Ji, University of Utah, United States
Session Coded Computation and Networks
Location Saint Germain, Level 3
Session Time Friday, 12 July, 11:40 - 13:00
Presentation Time Friday, 12 July, 12:00 - 12:20
Manuscript  Click here to download the manuscript
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.