# General Coded Computing in a Probabilistic Straggler Regime

arXiv: https://arxiv.org/abs/2502.00645 · HTML: https://mlsanity.com/paper/2502.00645/

## Key facts

- Cited by 2 papers in the map (data through 14 Oct 2026).
- Builds on 9 of its 24 references that are in the map.
- First posted on arXiv 2 Feb 2025.

## Builds on (most cited first, 9 of 9)

- [Lagrange Coded Computing: Optimal Design for Resiliency, Security and Privacy](https://mlsanity.com/paper/1806.00939/) (2018)
- [Polynomial Codes: an Optimal Design for High-Dimensional Coded Matrix Multiplication](https://mlsanity.com/paper/1705.10464/) (2017)
- [On the Optimal Recovery Threshold of Coded Matrix Multiplication](https://mlsanity.com/paper/1801.10292/) (2018)
- [Straggler Mitigation in Distributed Optimization Through Data Encoding](https://mlsanity.com/paper/1711.04969/) (2017)
- [Berrut Approximated Coded Computing: Straggler Resistance Beyond Polynomial Computing](https://mlsanity.com/paper/2009.08327/) (2020)
- [Entangled Polynomial Codes for Secure, Private, and Batch Distributed Matrix Multiplication: Breaking the "Cubic" Barrier](https://mlsanity.com/paper/2001.05101/) (2020)
- [ApproxIFER: A Model-Agnostic Approach to Resilient and Robust Prediction Serving Systems](https://mlsanity.com/paper/2109.09868/) (2021)
- [Coded Computing for Resilient Distributed Computing: A Learning-Theoretic Framework](https://mlsanity.com/paper/2406.00300/) (2024)
- [Asymptotic convergence rate of the longest run in an inflating Bernoulli net](https://mlsanity.com/paper/2001.00068/) (2019)

## Built on by (most cited first, 2 of 2)

- [DReS: Dual Reconstruction Smoothing for Functional Regularization](https://mlsanity.com/paper/2510.00253/) (2025)
- [Manifold-Aware General Coded Computing for Straggler-Resilient Distributed Computing](https://mlsanity.com/paper/2609.00552/) (2026)

## Abstract (arXiv)

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 Computing (LeTCC). Under the probabilistic straggler configuration, we demonstrate that the average approximation error for BACC and LeTCC converge to zero with the rate of at least O(log3_frac1p(N)·N-3) and O(log4_frac1p(N)·N-2), respectively. This is perhaps surprising, as earlier results does not indicate a convergence when the number of stragglers scales with the total number of servers N. However, in this case, despite the average number of stragglers being Np, the independence of servers in becoming stragglers allows the approximation error to converge to zero. These theoretical results are validated through experiments on various computing functions, including deep neural networks.