A Distributed Low-Complexity Coding Solution for Large-Scale Distributed FFT

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.