Distributed Decoding for Coded Distributed Computing

In distributed computing, when a large number of helper nodes assist a master node to finish a large task, the main challenge is when some of these helpers straggle. Several coded distributed computing schemes exist that resolve the straggling problem. In these solutions, however, the decoding remains a responsibility of the master node. The complexity of decoding can be significant and increase the execution time considerably. In this work, we propose a multilayer coding strategy that allows some helpers to assist with the decoding. With this multilayer structure, the original decoding is performed by some decoding helpers, and the master only minimally participates in decoding to make every layer reliable. The optimization problem to minimize the overall completion time is also studied and shown to have a simple solution in almost all practical scenarios.

Automated summary

In this work, a multilayer coding strategy is proposed to allow some helpers to assist with decoding in distributed computing, solving the straggling issue. By decoding at different layers, it simplifies the decoding burden on the master node and minimizes the overall completion time.