Graduate School and Research Center in Digital Sciences

Coded distributed computing with node cooperation substantially increases speedup factors

Parrinello, Emmanuele; Lampiris, Eleftherios; Elia, Petros

ISIT 2018, IEEE International Symposium on Information Theory, 17-22 June 2018, Vail, Colorado, USA

This work explores a distributed computing setting where K nodes are assigned fractions (subtasks) of a computational task in order to perform the computation in parallel. In this setting, a well-known main bottleneck has been the internode communication cost required to parallelize the task, because unlike the computational cost which could keep decreasing as K increases, the communication cost remains approximately constant, thus bounding the total speedup gains associated to having more computing nodes. This bottleneck was substantially ameliorated by the recent introduction of coded MapReduce techniques which allowed each node -- at the computational cost of having to preprocess approximately t times more subtasks -- to reduce its communication cost by approximately t times. In reality though, the associated speed up gains were severely limited by the requirement that larger t and K necessitated that the original task be divided into an extremely large number of subtasks. In this work we show how node cooperation, along with a novel assignment of tasks, can help to dramatically ameliorate this limitation. The result applies to wired as well as wireless distributed computing, and it is based on the idea of having groups of nodes compute identical parallelization (mapping) tasks and then employing a here-proposed novel D2D coded caching algorithm. 

Document Doi Arxiv Bibtex

Title:Coded distributed computing with node cooperation substantially increases speedup factors
Department:Communication systems
Eurecom ref:5464
Copyright: © 2018 IEEE. Personal use of this material is permitted. However, permission to reprint/republish this material for advertising or promotional purposes or for creating new collective works for resale or redistribution to servers or lists, or to reuse any copyrighted component of this work in other works must be obtained from the IEEE.
Bibtex: @inproceedings{EURECOM+5464, doi = {}, year = {2018}, title = {{C}oded distributed computing with node cooperation substantially increases speedup factors}, author = {{P}arrinello, {E}mmanuele and {L}ampiris, {E}leftherios and {E}lia, {P}etros}, booktitle = {{ISIT} 2018, {IEEE} {I}nternational {S}ymposium on {I}nformation {T}heory, 17-22 {J}une 2018, {V}ail, {C}olorado, {USA}}, address = {{V}ail, {UNITED} {STATES}}, month = {06}, url = {} }
See also: