Adaptive Privacy-Preserving Coded Computing with Hierarchical Task Partitioning.

Area of Science:

• Computer Science
• Information Theory
• Distributed Systems

Background:

• Coded computing addresses privacy leakage and straggling in distributed systems using coding theory.
• Existing methods struggle with diverse computation types and adaptive result accuracy.

Purpose of the Study:

• Propose Adaptive Privacy-Preserving Coded Computing (APCC) for versatile computation tasks.
• Ensure information-theoretical data privacy and mitigate the straggling effect.
• Adaptively provide accurate or approximated computation results.

Main Methods:

• APCC leverages coding theory for optimal task recovery and encoding rate.
• Hierarchical task partitioning and cancellation mitigate straggling effects.
• Mixed-integer nonlinear programming (MINLP) and a Maximum Value Descent (MVD) algorithm solve optimization problems.

Main Results:

• APCC guarantees information-theoretical data privacy.
• Hierarchical partitioning reduces computation delays by 20.3% to 47.5% compared to benchmarks.
• The MVD algorithm efficiently solves complex optimization problems.

Conclusions:

• APCC offers an optimal and adaptive solution for privacy-preserving coded computing.
• The strategy effectively reduces task completion delays in distributed environments.
• APCC demonstrates significant improvements over existing state-of-the-art methods.