The search functionality is under construction.

The search functionality is under construction.

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 ^{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 computational complexity for updating the encoding polynomial is improved from *O*(*L*(*K*+*T*)log ^{2}(*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

Daisuke HIBINO

Sophia University

Tomoharu SHIBUYA

Sophia University

The copyright of the original papers published on this site belongs to IEICE. Unauthorized use of the original or translated papers is prohibited. See IEICE Provisions on Copyright for details.

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 ^{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 computational complexity for updating the encoding polynomial is improved from *O*(*L*(*K*+*T*)log ^{2}(*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 ^{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 computational complexity for updating the encoding polynomial is improved from *O*(*L*(*K*+*T*)log ^{2}(*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 ^{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 computational complexity for updating the encoding polynomial is improved from *O*(*L*(*K*+*T*)log ^{2}(*K*+*T*)log log (*K*+*T*)) for LCC to *O*(*L*) for the proposed method.

ER -