EUVIMEDEUVIMED entdecken
Open Access · CC BY 4.0

Adaptive Privacy-Preserving Coded Computing with Hierarchical Task Partitioning

Qicheng Zeng iD, Zhaojun Nan iD, Sheng Zhou

Entropy · 21.10.2024 · 26 (10) · 881

DOI: 10.3390/e26100881 ↗

Kurz gefasst

Fachartikel in der Zeitschrift Entropy, online erschienen am 21.10.2024. Verfasst von Qicheng Zeng und 2 weiteren Autor:innen. Beteiligte Einrichtung: Department of Electronic Engineering, Tsinghua University, Beijing 100084, China. Die Arbeit wurde bisher 1-mal zitiert (Crossref) und nennt 47 Literaturangaben. Der Volltext ist frei zugänglich (Open Access, CC BY 4.0). Gefördert von: National Natural Science Foundation of China, China Postdoctoral Science Foundation, Fundamental Research Funds for the Central Universities.

AbstractSchlagwörterBibliografische AngabenZitierenVerwandte Studien

Abstract (Originalsprache)

Coded computing is recognized as a promising solution to address the privacy leakage problem and the straggling effect in distributed computing. This technique leverages coding theory to recover computation tasks using results from a subset of workers. In this paper, we propose the adaptive privacy-preserving coded computing (APCC) strategy, designed to be applicable to various types of computation tasks, including polynomial and non-polynomial functions, and to adaptively provide accurate or approximated results. We prove the optimality of APCC in terms of encoding rate, defined as the ratio between the computation loads of tasks before and after encoding, based on the optimal recovery threshold of Lagrange Coded Computing. We demonstrate that APCC guarantees information-theoretical data privacy preservation. Mitigation of the straggling effect in APCC is achieved through hierarchical task partitioning and task cancellation, which further reduces computation delays by enabling straggling workers to return partial results of assigned tasks, compared to conventional coded computing strategies. The hierarchical task partitioning problems are formulated as mixed-integer nonlinear programming (MINLP) problems with the objective of minimizing task completion delay. We propose a low-complexity maximum value descent (MVD) algorithm to optimally solve these problems. The simulation results show that APCC can reduce the task completion delay by a range of 20.3% to 47.5% when compared to other state-of-the-art benchmarks.

Schlagwörter

Stichwörter der Autor:innen

MINLPcoded computinghierarchical task partitioningprivacy preservationtask cancellation

Autor:innen und Institutionen

  • Department of Electronic Engineering, Tsinghua University, Beijing 100084, China.

ORCID-Profile: Qicheng Zeng, Zhaojun Nan

Förderung

  • National Natural Science Foundation of China
  • China Postdoctoral Science Foundation
  • Fundamental Research Funds for the Central Universities

Zitieren

APA

Zeng, Q., Nan, Z., & Zhou, S. (2024). Adaptive Privacy-Preserving Coded Computing with Hierarchical Task Partitioning. Entropy, 26(10), 881. https://doi.org/10.3390/e26100881

Vancouver

Zeng Q, Nan Z, Zhou S. Adaptive Privacy-Preserving Coded Computing with Hierarchical Task Partitioning. Entropy. 2024;26(10):881. doi:10.3390/e26100881

BibTeX
@article{Zeng2024,
  author = {Zeng, Qicheng and Nan, Zhaojun and Zhou, Sheng},
  title = {Adaptive Privacy-Preserving Coded Computing with Hierarchical Task Partitioning},
  journal = {Entropy},
  year = {2024},
  volume = {26},
  number = {10},
  pages = {881},
  doi = {10.3390/e26100881}
}
Kostenlos starten →