Coded Computing for Fault Tolerant Distributed Systems

This direction is merged into another direction: coded distributed computing. Its last version stays readable and citable here.

Version 1 of 117 papers17 conceptsfrozen 2026-10-04

In large-scale distributed computing, hardware failures and "stragglers"—nodes that are significantly slower than others—are statistical certainties rather than anomalies. Traditional solutions like checkpoint-restart or modular redundancy (running the same task multiple times) impose massive overheads, often doubling or tripling the required hardware and energy resources. Researchers are instead developing Coded Computing, a framework that applies principles from information theory to inject mathematical redundancy directly into computations, allowing systems to recover lost or delayed results with minimal overhead.

The Core Intuition: From Data to Computation

The fundamental insight of coded computing is that the same erasure coding techniques used to protect data in storage (like RAID or Reed-Solomon codes) can be applied to the operations performed on that data.

In a standard distributed matrix multiplication, you might split two matrices into blocks and distribute them across workers. If one worker fails, that block of the result is lost. In a coded approach, such as the one proposed in Polynomial Codes by Qian Yu and Salman Avestimehr, the input matrices are instead used to define polynomials. The workers compute evaluations of these polynomials. Because a polynomial of degree $d$ can be reconstructed from any $d+1$ points, the master node only needs to wait for a subset of the fastest workers to finish. This effectively "obliviously" bypasses stragglers without needing to know which nodes will be slow in advance.

Resilience in Linear Algebra and HPC

For high-performance computing (HPC), the goal is to maintain the speed of algorithms like the Fast Fourier Transform (FFT) or linear solvers while surviving node crashes.

Coding for Machine Learning Inference

The "straggler" problem is particularly acute in real-time machine learning inference, where tail latency (the delay of the slowest request) dictates the user experience.

Jack Kosaian and K. V. Rashmi introduced Parity Models (ParM), which move beyond simple linear codes. Instead of replicating a neural network, they train a "parity" neural network that takes a combination of multiple inputs (e.g., the sum of two images) and learns to predict a combination of their outputs. If one of the primary nodes is slow, the parity model's output can be used to mathematically "subtract" the known result and recover the missing one.

Similarly, Collage Inference by Krishna Giri Narra and Coded-InvNet by Tuan Dinh use specialized architectures like Invertible Neural Networks (INNs) to ensure that the information from multiple queries is preserved and recoverable, reducing the resource tax of reliability from 100% down to as little as 10–25%.

Beyond Failures: Byzantine Resilience

In decentralized or adversarial environments, nodes might not just be slow; they might return incorrect or malicious data. Nirupam Gupta and Nitin H. Vaidya explore Randomized Reactive Redundancy, which uses coding and verification to identify and ignore these "Byzantine" workers. By leveraging the mathematical structure of the learning task, these systems can maintain accuracy even when a portion of the compute cluster is actively working against the training process.

Papers in this version

History & citationVersion 1 · 2026-10-04

Merged into another direction · Permanent link

View frozen version 1

Cite this direction

Latest version (a living page):

@misc{lacuna_coded_computing_for_fault_tolerant_distr_612a8ff0,
  title = {Coded Computing for Fault Tolerant Distributed Systems},
  author = {{Lacuna}},
  howpublished = {Lacuna research direction},
  year = {2026},
  url = {https://lacuna.tiptreesystems.com/direction/coded-computing-for-fault-tolerant-distributed-systems/rdr_612a8ff06cb841928266c663d6304d0d},
  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_fault_tolerant_distr_612a8ff0_v1,
  title = {Coded Computing for Fault Tolerant Distributed Systems},
  author = {{Lacuna}},
  howpublished = {Lacuna research direction},
  year = {2026},
  url = {https://lacuna.tiptreesystems.com/direction/coded-computing-for-fault-tolerant-distributed-systems/rdr_612a8ff06cb841928266c663d6304d0d/v/1},
  note = {Version 1, frozen 2026-10-04. Accessed 2026-11-20},
}