2018/05/24 by Haewon Jeong, Jeong, Haewon, Tze Meng Low +3
Computer Science · #Advanced Data Storage Technologies #Distributed #Error Correcting Code Techniques #FOS: Computer and information sciences #Information Theory (cs.IT) #Parallel #Parallel Computing and Optimization Techniques #and Cluster Computing (cs.DC)
paper · pdf · doi:10.48550/arxiv.1805.09891
openalex publication_date 2018/05/24 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
We propose a coded computing strategy and examine communication costs of coded computing algorithms to make distributed Fast Fourier Transform (FFT) resilient to errors during the computation. We apply maximum distance separable (MDS) codes to a widely used "Transpose" algorithm for parallel FFT. In the uncoded distributed FFT algorithm, the most expensive step is a single "all-to-all" communication. We compare this with communication overhead of coding in our coded FFT algorithm. We show that by using a systematic MDS code, the communication overhead of coding is negligible in comparison with the communication costs inherent in an uncoded FFT implementation if the number of parity nodes is at most o(log K), where K is the number of systematic nodes.