General Coded Computing: Adversarial Settings

Conventional coded computing frameworks are predominantly designed for structured computations, such as matrix multiplication and polynomial evaluation. These tasks enable the reuse of tools and techniques from algebraic coding theory to enhance the reliability of distributed systems in the presence of stragglers and adversarial servers. In this paper, we lay the foundation for General Coded Computing, a reliable and highly efficient coded computing framework that extends the applicability of coded computing to a broad class of computations under minimal structural assumptions. Additionally, we address, for the first time, the challenging problem of adversarial servers within this setting. Under the proposed scheme, we show that for a system with N servers, where O(N^a) servers are adversarial for some a ∈[0,1), the supremum of the average computation error across all adversarial strategies decays at a rate of at least N^6/5(a-1), under minimal assumptions on the computing tasks. Moreover, we demonstrate that the proposed scheme achieves optimal adversarial robustness in terms of maximum number of adversarial servers it can tolerate. This development marks a significant step toward practical and reliable coded computing for general computation. Experimental results validate the effectiveness of the proposed method across a variety of computations, including inference in deep neural networks.