2017 · 65 citations · 26 references
ComputingComputer EngineeringComputer ScienceDistributed SystemsFault ToleranceFault-tolerant ComputingCoding TheoryDigital Signal ProcessingDistributed ComputingDistributed Data ProcessingError-correcting CodesSignal ProcessingDiscrete Fourier TransformDistributed Fourier TransformFast Fourier TransformFourier TransformMds CodesOptimal Threshold SelectionRobustnessStraggler Mitigation
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.
26
An algorithm for the machine calculation of complex Fourier series
J.W. Cooley, John W. Tukey · Mathematics of Computation · 1965 · 12.2K citations
The Design and Implementation of FFTW3
Matteo Frigo, Steven G. Johnson · Proceedings of the IEEE · 2005 · 5.2K citations
Luiz André Barroso · Communications of the ACM · 2013 · 1.7K citations
Improving MapReduce performance in heterogeneous environments
Matei Zaharia, Andy Konwinski, Anthony D. Joseph et al. · UC Berkeley · 2008 · 1.6K citations
Speeding Up Distributed Machine Learning Using Codes
Kangwook Lee, Maximilian Lam, Ramtin Pedarsani et al. · IEEE Transactions on Information Theory · 2017 · 866 citations · Full text