Adaptive Privacy-Preserving Coded Computing with Hierarchical Task Partitioning

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 <inline-formula><math xmlns="http://www.w3.org/1998/Math/MathML" display="inline"><semantics><mrow><mn>20.3</mn><mo>%</mo></mrow></semantics></math></inline-formula> to <inline-formula><math xmlns="http://www.w3.org/1998/Math/MathML" display="inline"><semantics><mrow><mn>47.5</mn><mo>%</mo></mrow></semantics></math></inline-formula> when compared to other state-of-the-art benchmarks.