Efficient composition of encoding polynomial in distributed coded computing scheme

摘要

Distributed computing is one of the powerful solutions for computational tasks that need the massive size of dataset. Lagrange coded computing (LCC), proposed by Yu et al. realizes private and secure distributed computing under the existence of stragglers, malicious workers, and colluding workers by using an encoding polynomial. Since the encoding polynomial depends on a dataset, it must be updated every arrival of new dataset. Therefore, it is necessary to employ efficient algorithm to compose the encoding polynomial. In this paper, we propose Newton coded computing (NCC) which is based on Newton interpolation to compose the encoding polynomial. Let K, L, and T be the number of data, the length of each data, and the number of colluding workers, respectively. Then, the computational complexity for composition of an encoding polynomial is improved from O (LN log~2 (K + T) log log(K + T)) for LCC to O (L (K + T) log(K + T)) for the proposed method. Furthermore, by applying the proposed method, the computation complexity for updating the encoding polynomial is improved from O (LN log~2 (K + T) log log(K + T)) for LCC to O (L) for the proposed method.