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.

In distributed computing, a number of available helper nodes assist in completing a task for the master node. In such setups, the failure or straggling of even a single helper node can significantly increase the processing time. Therefore, coded distributed computing has been the subject of many recent studies. A problem that arises in some setups is that the master's decoding complexity may exceed the complexity of self-computation, rending distributed computing useless. One such case is distributed large-scale FFT, where many helper nodes are required. In this work, we propose a novel distributed coded FFT, where the master's load is significantly lower than the existing work. The gain is obtained by (1) using a novel distributed FFT structure which allows for reliable distributed coding at the Shuffle stage, and (2) using Raptor codes which enjoy a linear complexity at the cost of a small number of extra helper nodes. Numerical results are provided to support the benefits of our proposed solution and to optimize design parameters.