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.
Original language | English (US) |
---|---|
Title of host publication | 55th Annual Allerton Conference on Communication, Control, and Computing, Allerton 2017 |
Publisher | Institute of Electrical and Electronics Engineers Inc. |
Pages | 494-501 |
Number of pages | 8 |
ISBN (Electronic) | 9781538632666 |
DOIs | |
State | Published - Jul 1 2017 |
Externally published | Yes |
Event | 55th Annual Allerton Conference on Communication, Control, and Computing, Allerton 2017 - Monticello, United States Duration: Oct 3 2017 → Oct 6 2017 |
Publication series
Name | 55th Annual Allerton Conference on Communication, Control, and Computing, Allerton 2017 |
---|---|
Volume | 2018-January |
Other
Other | 55th Annual Allerton Conference on Communication, Control, and Computing, Allerton 2017 |
---|---|
Country/Territory | United States |
City | Monticello |
Period | 10/3/17 → 10/6/17 |
Bibliographical note
Funding Information:This work is in part supported by NSF grant CIF 1703575, ONR award N000141612189, and a research gift from Intel. This material is based upon work supported by Defense Advanced Research Projects Agency (DARPA) under Contract No. HR001117C0053. The views, opinions, and/or findings expressed are those of the author(s) and should not be interpreted as representing the official views or policies of the Department of Defense or the U.S. Government.
Publisher Copyright:
© 2017 IEEE.