Coded Fourier Transform

Abstract

We consider the problem of computing the Fourier transform of high-dimensional vectors, distributedly over a cluster of machines consisting of a master node and multiple worker nodes, where the worker nodes can only store and process a fraction of the inputs. We show that by exploiting the algebraic structure of the Fourier transform operation and leveraging concepts from coding theory, one can efficiently deal with the straggler effects. In particular, we propose a computation strategy, named as coded FFT, which achieves the optimal recovery threshold, defined as the minimum number of workers that the master node needs to wait for in order to compute the output. This is the first code that achieves the optimum robustness in terms of tolerating stragglers or failures for computing Fourier transforms. Furthermore, the reconstruction process for coded FFT can be mapped to MDS decoding, which can be solved efficiently. Moreover, we extend coded FFT to settings including computing general $n$-dimensional Fourier transforms, and provide the optimal computing strategy for those settings.

References in corpus (5)

• Speeding Up Distributed Machine Learning Using Codes
• Polynomial Codes: an Optimal Design for High-Dimensional Coded Matrix Multiplication
• Efficient erasure decoding of Reed-Solomon codes
• A Unified Coding Framework for Distributed Computing with Straggling Servers
• How to Optimally Allocate Resources for Coded Distributed Computing?

Cited by in corpus (5)

• Straggler-aware Distributed Learning: Communication Computation Latency Trade-off
• Cross Subspace Alignment Codes for Coded Distributed Batch Computation
• Coded FFT and Its Communication Overhead
• Coded Distributed Computing over Packet Erasure Channels
• Optimum Transmission Delay for Function Computation in NFV-based Networks: the role of Network Coding and Redundant Computing