Efficient Construction of Encoding Polynomials in a Distributed Coded Computing Scheme

Daisuke HIBINO; Tomoharu SHIBUYA

doi:10.1587/transfun.2023TAP0011

Efficient Construction of Encoding Polynomials in a Distributed Coded Computing Scheme

Daisuke HIBINO, Tomoharu SHIBUYA

Full Text Views

1

Cite this

Summary :

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. [15], 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 construct the encoding polynomial. In this paper, we propose Newton coded computing (NCC) which is based on Newton interpolation to construct 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 construction of an encoding polynomial is improved from O(L(K+T)log ²(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 computational complexity for updating the encoding polynomial is improved from O(L(K+T)log ²(K+T)log log (K+T)) for LCC to O(L) for the proposed method.

Publication: IEICE TRANSACTIONS on Fundamentals Vol.E107-A No.3 pp.476-485

Publication Date: 2024/03/01

Publicized: 2023/08/10

Online ISSN: 1745-1337

DOI: 10.1587/transfun.2023TAP0011

Type of Manuscript: Special Section PAPER (Special Section on Information Theory and Its Applications)

Category: Cryptography and Information Security

Authors

Daisuke HIBINO
Sophia University
Tomoharu SHIBUYA
Sophia University

Keyword

distributed computing, Lagrange interpolation, Newton interpolation, polynomial evaluation, computational complexity

Cite this

Copy

Daisuke HIBINO, Tomoharu SHIBUYA, "Efficient Construction of Encoding Polynomials in a Distributed Coded Computing Scheme" in IEICE TRANSACTIONS on Fundamentals, vol. E107-A, no. 3, pp. 476-485, March 2024, doi: 10.1587/transfun.2023TAP0011.
Abstract: 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. [15], 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 construct the encoding polynomial. In this paper, we propose Newton coded computing (NCC) which is based on Newton interpolation to construct 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 construction of an encoding polynomial is improved from O(L(K+T)log ²(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 computational complexity for updating the encoding polynomial is improved from O(L(K+T)log ²(K+T)log log (K+T)) for LCC to O(L) for the proposed method.
URL: https://global.ieice.org/en_transactions/fundamentals/10.1587/transfun.2023TAP0011/_p

Copy

@ARTICLE{e107-a_3_476,
author={Daisuke HIBINO, Tomoharu SHIBUYA, },
journal={IEICE TRANSACTIONS on Fundamentals},
title={Efficient Construction of Encoding Polynomials in a Distributed Coded Computing Scheme},
year={2024},
volume={E107-A},
number={3},
pages={476-485},
abstract={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. [15], 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 construct the encoding polynomial. In this paper, we propose Newton coded computing (NCC) which is based on Newton interpolation to construct 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 construction of an encoding polynomial is improved from O(L(K+T)log ²(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 computational complexity for updating the encoding polynomial is improved from O(L(K+T)log ²(K+T)log log (K+T)) for LCC to O(L) for the proposed method.},
keywords={},
doi={10.1587/transfun.2023TAP0011},
ISSN={1745-1337},
month={March},}

Copy

TY - JOUR
TI - Efficient Construction of Encoding Polynomials in a Distributed Coded Computing Scheme
T2 - IEICE TRANSACTIONS on Fundamentals
SP - 476
EP - 485
AU - Daisuke HIBINO
AU - Tomoharu SHIBUYA
PY - 2024
DO - 10.1587/transfun.2023TAP0011
JO - IEICE TRANSACTIONS on Fundamentals
SN - 1745-1337
VL - E107-A
IS - 3
JA - IEICE TRANSACTIONS on Fundamentals
Y1 - March 2024
AB - 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. [15], 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 construct the encoding polynomial. In this paper, we propose Newton coded computing (NCC) which is based on Newton interpolation to construct 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 construction of an encoding polynomial is improved from O(L(K+T)log ²(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 computational complexity for updating the encoding polynomial is improved from O(L(K+T)log ²(K+T)log log (K+T)) for LCC to O(L) for the proposed method.
ER -