Verifiable coded computation of multiple functions
We consider the problem of evaluating distinct multivariate polynomials over several massive datasets in a distributed computing system with a single master node and multiple worker nodes. We focus on the general case when each multivariate polynomial is evaluated over its corresponding dataset and...
Saved in:
Main Authors: | , , |
---|---|
Other Authors: | |
Format: | Article |
Language: | English |
Published: |
2024
|
Subjects: | |
Online Access: | https://hdl.handle.net/10356/180653 |
Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
Institution: | Nanyang Technological University |
Language: | English |
id |
sg-ntu-dr.10356-180653 |
---|---|
record_format |
dspace |
spelling |
sg-ntu-dr.10356-1806532024-10-21T15:35:05Z Verifiable coded computation of multiple functions Kim, Wilton Kruglik, Stanislav Kiah, Han Mao School of Physical and Mathematical Sciences Computer and Information Science Distributed computing Communication efficiency Verifiability Privacy We consider the problem of evaluating distinct multivariate polynomials over several massive datasets in a distributed computing system with a single master node and multiple worker nodes. We focus on the general case when each multivariate polynomial is evaluated over its corresponding dataset and propose a generalization of the Lagrange Coded Computing framework (Yu et al. 2019) to perform all computations simultaneously while providing robustness against stragglers who do not respond in time, adversarial workers who respond with wrong computation and information-theoretic security of dataset against colluding workers. Our scheme introduces a small computation overhead which results in a reduction in download cost and also offers comparable resistance to stragglers over existing solutions. On top of it, we also propose two verification schemes to detect the presence of adversaries, which leads to incorrect results, without involving additional nodes. Ministry of Education (MOE) National Research Foundation (NRF) Submitted/Accepted version This research is supported by the National Research Foundation, Singapore under its Strategic Capability Research Centres Funding Initiative, Singapore Ministry of Education Academic Research Fund Tier 2 Grants MOE2019-T2-2-083, MOE-T2EP20121-0007 and Academic Research Fund Tier 1 Grant RG19/23. 2024-10-17T00:59:01Z 2024-10-17T00:59:01Z 2024 Journal Article Kim, W., Kruglik, S. & Kiah, H. M. (2024). Verifiable coded computation of multiple functions. IEEE Transactions On Information Forensics and Security, 19, 8009-8022. https://dx.doi.org/10.1109/TIFS.2024.3450288 1556-6013 https://hdl.handle.net/10356/180653 10.1109/TIFS.2024.3450288 19 8009 8022 en MOE2019-T2-2-083 MOE-T2EP20121-0007 RG19/23 IEEE Transactions on Information Forensics and Security © 2024 IEEE. All rights reserved. This article may be downloaded for personal use only. Any other use requires prior permission of the copyright holder. The Version of Record is available online at http://doi.org/10.1109/TIFS.2024.3450288. application/pdf |
institution |
Nanyang Technological University |
building |
NTU Library |
continent |
Asia |
country |
Singapore Singapore |
content_provider |
NTU Library |
collection |
DR-NTU |
language |
English |
topic |
Computer and Information Science Distributed computing Communication efficiency Verifiability Privacy |
spellingShingle |
Computer and Information Science Distributed computing Communication efficiency Verifiability Privacy Kim, Wilton Kruglik, Stanislav Kiah, Han Mao Verifiable coded computation of multiple functions |
description |
We consider the problem of evaluating distinct multivariate polynomials over several massive datasets in a distributed computing system with a single master node and multiple worker nodes. We focus on the general case when each multivariate polynomial is evaluated over its corresponding dataset and propose a generalization of the Lagrange Coded Computing framework (Yu et al. 2019) to perform all computations simultaneously while providing robustness against stragglers who do not respond in time, adversarial workers who respond with wrong computation and information-theoretic security of dataset against colluding workers. Our scheme introduces a small computation overhead which results in a reduction in download cost and also
offers comparable resistance to stragglers over existing solutions. On top of it, we also propose two verification schemes to detect the presence of adversaries, which leads to incorrect results, without involving additional nodes. |
author2 |
School of Physical and Mathematical Sciences |
author_facet |
School of Physical and Mathematical Sciences Kim, Wilton Kruglik, Stanislav Kiah, Han Mao |
format |
Article |
author |
Kim, Wilton Kruglik, Stanislav Kiah, Han Mao |
author_sort |
Kim, Wilton |
title |
Verifiable coded computation of multiple functions |
title_short |
Verifiable coded computation of multiple functions |
title_full |
Verifiable coded computation of multiple functions |
title_fullStr |
Verifiable coded computation of multiple functions |
title_full_unstemmed |
Verifiable coded computation of multiple functions |
title_sort |
verifiable coded computation of multiple functions |
publishDate |
2024 |
url |
https://hdl.handle.net/10356/180653 |
_version_ |
1814777782346973184 |