Coded Computing for Resilient Distributed Learning

You are reading version 1 of this direction, frozen 2026-10-04. The latest version is version 2.

Version 1 of 2242 papers416 conceptsfrozen 2026-10-04

In distributed machine learning, the speed of a training iteration is often dictated by the slowest participant. This "straggler problem" occurs when a single worker node—due to network congestion, hardware thermal throttling, or background processes—delays the entire synchronous update. Traditionally, systems either wait for the straggler (wasting time) or ignore it (introducing statistical bias).

Coded Computing offers a third way. By applying principles from information theory to distributed algebra, researchers have developed frameworks that allow a central server to reconstruct the exact result of a computation from only a subset of worker responses.

The Straggler as an Erasure

The core intuition behind coded computing is to treat a slow or non-responsive worker not as a failure to be ignored, but as an erasure in a communication code.

In classical coding theory, if you want to send a message across a noisy channel, you add redundancy so the receiver can recover the original data even if some bits are lost. Dimitris Papailiopoulos and Deniz Gunduz argue that we can apply this same logic to computation. Instead of encoding bits, we encode the data or the tasks themselves.

Gradient Coding

The most direct application of this idea is Gradient Coding, introduced by Rashish Tandon and Alexandros G. Dimakis in Gradient Coding.

In a standard distributed setup, each of $N$ workers computes a gradient on a unique $1/N$ fraction of the data. The server must wait for all $N$ gradients to compute the full-batch update. In Gradient Coding, the data is distributed with redundancy: each worker is assigned multiple overlapping data partitions. When a worker finishes, it sends a linear combination of the gradients it computed.

Because of the clever way these linear combinations are designed, the central server can solve a system of linear equations to recover the exact full-batch gradient as soon as any $K$ out of $N$ workers respond. This $K$ is known as the recovery threshold. This ensures the optimization process remains statistically identical to synchronous full-batch updates while running at the speed of the fastest workers.

Optimal Matrix Multiplication with Polynomial Codes

While Gradient Coding handles the aggregation of first-order derivatives, many machine learning tasks rely on heavy matrix-matrix multiplications. Qian Yu and colleagues proposed Polynomial Codes to make these operations straggler-resilient.

The mechanism works by mapping the matrices into polynomials. If you want to multiply matrices $A$ and $B$, you partition them and define polynomial functions $A(x)$ and $B(x)$ such that the product $C = A \times B$ is embedded in the coefficients of the product polynomial $P(x) = A(x) \times B(x)$.

  1. The server sends different evaluations of these polynomials (e.g., $A(z_i)$ and $B(z_i)$) to different workers.
  2. Each worker performs a single matrix multiplication.
  3. The server treats the incoming results as points on the polynomial $P(x)$.

Using Reed-Solomon-style interpolation, the server can reconstruct the entire polynomial—and thus the final matrix product—once it receives enough points to satisfy the degree of the polynomial. Pedro Soto and Jun Li further refined this with Dual Entangled Polynomial Codes, which allow workers to perform multiple sub-computations to "pack" and cancel out unwanted interference terms, further lowering the recovery threshold.

Resilience at the Wireless Edge

The need for coded computing is most acute in Federated Learning (FL), where "workers" are often unpredictable mobile devices. Sagar Dhakal and Salman Avestimehr developed CodedFedL to handle the extreme volatility of wireless edge networks.

In these environments, simply ignoring stragglers is dangerous because edge data is often non-IID (not identically distributed). If you ignore the slow phones, you might accidentally ignore an entire demographic or geographic region, leading to a biased model. Reent Schlegel and Siddhartha Kumar show in CodedPaddedFL that by using redundant "parity" data, the server can mathematically recover the missing updates from stragglers. This ensures the final global model reflects the entire dataset's characteristics without waiting for the slowest device.

Moving Beyond Linear Algebra

Early coded computing relied on the linearity of gradients and matrix multiplication. However, modern research is extending these benefits to non-linear tasks like neural network inference.

  • Parity Models: ParM introduces the idea of training specialized "parity models" that take a linear combination of multiple inputs and produce a result that can help recover missing inferences from primary models.
  • Learning-Theoretic Coding: Behrooz Tahmasebi and Mohammad Ali Maddah-Ali suggest moving away from rigid algebraic codes entirely. In Coded Computing: A Learning-Theoretic Framework, they propose using neural networks to learn the optimal encoding and decoding functions, allowing for statistical rather than exact recovery, which is often more efficient for general machine learning workloads.

By shifting the burden from the network (waiting for data) to the processor (computing redundant math), coded computing transforms the fundamental trade-offs of distributed systems, making them robust to the inherent "noise" of real-world hardware.

Papers in this version

Showing 60 of 242 papers.

History & citationVersion 2 · 2026-10-04

Current · Permanent link

  1. Version 2 (latest) · 2026-10-04 · 214 papers
  2. Version 1 · 2026-10-04 · 242 papers
Cite this direction

Latest version (a living page):

@misc{lacuna_coded_distributed_computing_eaf6b213,
  title = {coded distributed computing},
  author = {{Lacuna}},
  howpublished = {Lacuna research direction},
  year = {2026},
  url = {https://lacuna.tiptreesystems.com/direction/coded-distributed-computing/rdr_eaf6b21341de456497fe32ec87ac114b},
  note = {Latest version of a living research direction; cite a version for a fixed text. Accessed 2026-11-20},
}

This exact version (version 1, frozen text):

@misc{lacuna_coded_computing_for_resilient_distribute_eaf6b213_v1,
  title = {Coded Computing for Resilient Distributed Learning},
  author = {{Lacuna}},
  howpublished = {Lacuna research direction},
  year = {2026},
  url = {https://lacuna.tiptreesystems.com/direction/coded-computing-for-resilient-distributed-learning/rdr_eaf6b21341de456497fe32ec87ac114b/v/1},
  note = {Version 1, frozen 2026-10-04. Accessed 2026-11-20},
}