  Distributed computing is known as an emerging and efficient technique to
support various intelligent services, such as large-scale machine learning.
However, privacy leakage and random delays from straggling servers pose
significant challenges. To address these issues, coded computing, a promising
solution that combines coding theory with distributed computing, recovers
computation tasks with results from a subset of workers. In this paper, we
propose the adaptive privacy-preserving coded computing (APCC) strategy, which
can adaptively provide accurate or approximated results according to the form
of computation functions, so as to suit diverse types of computation tasks. We
prove that APCC achieves complete data privacy preservation and demonstrate its
optimality in terms of encoding rate, defined as the ratio between the
computation loads of tasks before and after encoding. To further alleviate the
straggling effect and reduce delay, we integrate hierarchical task partitioning
and task cancellation into the coding design of APCC. The corresponding
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. Simulation results show that APCC can reduce task
completion delay by a range of 20.3% to 47.5% when compared to other
state-of-the-art benchmarks.
