提出通用编码计算框架，应对恶意服务器威胁。
General Coded Computing: Adversarial Settings
- 设计新编码方案，支持复杂计算任务的容错
- 在最多 $\mathcal{O}(N^a)$ 个恶意服务器下，误差随 $N^{\frac{6}{5}(a-1)}$ 衰减
- 首次实现通用计算中对抗鲁棒性的最优容忍能力
传统编码计算框架主要针对矩阵乘法、多项式求值等结构化计算，可利用代数编码理论提升系统在慢节点和恶意服务器下的可靠性。本文建立通用编码计算的基础，将编码计算拓展至广泛计算任务，并重点解决恶意服务器挑战。在 $N$ 个服务器系统中，若存在 $\mathcal{O}(N^a)$（$a \in [0,1)$）个恶意服务器，所提方案在所有恶意策略下平均近似误差的上界以 $N^{\frac{6}{5}(a-1)}$ 的速率衰减，且对计算任务假设极小。此外，在通用框架内，该方案实现了对抗鲁棒性的最优容忍度——可容忍的最大恶意服务器数达到理论上限。实验验证了该方法在深度神经网络推理等多种计算中的有效性，标志着通用可靠编码计算的重要进展。
原文摘要 · Abstract (English)
Conventional coded computing frameworks are predominantly tailored for structured computations, such as matrix multiplication and polynomial evaluation. Such tasks allow the reuse of tools and techniques from algebraic coding theory to improve the reliability of distributed systems in the presence of stragglers and adversarial servers. This paper lays the foundation for general coded computing, which extends the applicability of coded computing to handle a wide class of computations. In addition, it particularly addresses the challenging problem of managing adversarial servers. We demonstrate that, in the proposed scheme, for a system with $N$ servers, where $\mathcal{O}(N^a)$, $a \in [0,1)$, are adversarial, the supremum of the average approximation error over all adversarial strategies decays at a rate of $N^{\frac{6}{5}(a-1)}$, under minimal assumptions on the computing tasks. Furthermore, we show that within a general framework, the proposed scheme achieves optimal adversarial robustness, in terms of maximum number of adversarial servers it can tolerate. This marks a significant step toward practical and reliable general coded computing. Implementation results further validate the effectiveness of the proposed method in handling various computations, including inference in deep neural networks.
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品；中文卡片由大模型生成，请以原文为准。