Mapping Heterogeneity Does Not Affect Wireless Coded MapReduce
Eleftherios Lampiris, Daniel Jimenez Zorrilla, Petros Elia · 2019
The work considers a Coded MapReduce setting where computing nodes of different processing capabilities coexist. Motivated by scenarios where the mapping phase is performed by nodes of heterogeneous computing capabilities, we explore the setting with K1nodes that can each map a fraction γ1∈ [1/K,1] of the dataset, and K2nodes that can each map a smaller fraction γ21. For the standard wireless (single-antenna) device-to-device channel or its equivalent wired network with network-coding capabilities at the nodes, we propose a solution of assigning data to the nodes and a method of communicating intermediate values during the shuffling phase, that can be applied to any MapReduce problem and which entirely removes the affects of heterogeneity. The surprising outcome of this work is that the shuffling-phase delay is reduced by a factor of K1γ1+K2γ2, matching the performance of the corresponding homogeneous setting, thus revealing for the first time that heterogeneity during the mapping phase does not inherently deteriorate the overall performance.