[2502.00645] General Coded Computing in a Probabilistic Straggler Regime

Computer Science > Distributed, Parallel, and Cluster Computing arXiv:2502.00645 (cs) [Submitted on 2 Feb 2025 (v1), last revised 24 Mar 2026 (this version, v3)] Title:General Coded Computing in a Probabilistic Straggler Regime Authors:Parsa Moradi, Mohammad Ali Maddah-Ali View a PDF of the paper titled General Coded Computing in a Probabilistic Straggler Regime, by Parsa Moradi and 1 other authors View PDF HTML (experimental) Abstract:Coded computing has demonstrated promising results in addressing straggler resiliency in distributed computing systems. However, most coded computing schemes are designed for exact computation, requiring the number of responding servers to exceed a certain recovery threshold. Additionally, these schemes are tailored for highly structured functions. Recently, new coded computing schemes for general computing functions, where exact computation is replaced with approximate computation, have emerged. In these schemes, the availability of additional results corresponds to more accurate estimation of computational tasks. This flexibility introduces new questions that need to be addressed. This paper addresses the practically important scenario in the context of general coded computing, where each server may become a straggler with a probability $p$, independently from others. We theoretically analyze the approximation error of two existing general coded computing schemes: Berrut Approximate Coded Computing (BACC) and Learning Theoretic Coded Compu...