Erasure Coding

Disks die. Servers catch fire. Whole data centers go dark. So if your file matters, you keep more than one copy. The brute-force answer is replication: store the file three times, and you can lose any two copies and still be fine. Simple — but you now pay for three times the storage to protect one file.

Erasure coding does dramatically better. Instead of copying the file, it transforms it into n pieces — called shards — with a magic property: any k of them are enough to reconstruct the original, and the other $n - k$ can vanish. Pick n = 6, k = 4 and you survive any two lost shards while paying only 1.5× the storage, not 3×.

How can fragments you've never seen rebuild data they don't literally contain? The answer is a piece of mathematics that quietly runs underneath your CDs, QR codes, hard-drive arrays and cloud buckets.

Below, a secret value is encoded into 6 shards so that any 4 can rebuild it. Click shards to "destroy" them, then press Rebuild and watch the original reappear — or fail when too few survive.

<p class="hint">{{hint}}</p>
<div class="secret">{{secret_label}} <span id="secret">?</span></div>
<div id="shards" class="shards"></div>
<div class="status" id="status">{{status_init}}</div>
<div class="btns">
  <button id="rebuild" type="button">{{btn_rebuild}}</button>
  <button id="reset" type="button" class="ghost">{{btn_reset}}</button>
</div>

* { box-sizing: border-box; }
body { font-family: system-ui, sans-serif; color: #222; margin: 0; }
.hint { font-size: .9rem; color: #444; margin: 0 0 .7rem; line-height: 1.45; }
.secret { font-size: 1rem; font-weight: 600; margin: .3rem 0 .6rem; }
.secret span { font-family: ui-monospace, monospace; color: #1d3557; }
.shards { display: grid; grid-template-columns: repeat(6, 1fr); gap: 8px; margin: .5rem 0; }
.shard { padding: .6rem .3rem; border-radius: 10px; text-align: center; cursor: pointer;
         user-select: none; border: 2px solid #cdd9e3; background: #e8eef3; transition: all .12s; }
.shard:hover { border-color: #1d3557; }
.shard .lbl { font-size: .72rem; color: #57708a; }
.shard .val { font: 700 16px ui-monospace, monospace; color: #1d3557; margin-top: 2px; }
.shard.dead { background: #f3d6d9; border-color: #e0a4ab; opacity: .55; }
.shard.dead .val, .shard.dead .lbl { color: #b03a46; text-decoration: line-through; }
.status { font-size: 1rem; font-weight: 600; margin: .6rem 0; min-height: 1.4em; }
.status.ok { color: #0a7d33; }
.status.bad { color: #c92f3c; }
.btns { display: flex; gap: .5rem; flex-wrap: wrap; }
button { font: 600 14px system-ui, sans-serif; padding: .45rem .9rem; border: 1px solid #1d3557;
         background: #1d3557; color: #fff; border-radius: 8px; cursor: pointer; }
button.ghost { background: #fff; color: #1d3557; }

// Code not found

The trick is that the shards are points on a polynomial. Four points uniquely fix a degree-3 curve, so any four of the six points recover the same curve — and reading its value at x = 0 gives back the original data. Knock out three or more shards and only $\le 3$ points remain: infinitely many curves pass through them, so reconstruction becomes impossible. That sharp $k$-point threshold is exactly what makes Reed-Solomon codes so reliable.

Erasure coding is a rare happy story in this site: the problem is solved, optimally, and efficiently.

• The construction. The classic scheme is the Reed-Solomon code, introduced by Irving Reed and Gustave Solomon in 1960. Treat the data as the coefficients of a polynomial of degree $k - 1$, then evaluate it at $n$ distinct points. Those $n$ values are the shards.
• Why any k suffice. A degree $k - 1$ polynomial is uniquely determined by any k of its values (polynomial interpolation). So any $k$ surviving shards rebuild the exact polynomial, and with it the original data — the missing $n - k$ are irrelevant.
• It's provably optimal. Reed-Solomon codes are MDS (Maximum Distance Separable): they meet the Singleton bound, the information-theoretic limit. You cannot tolerate $n - k$ losses with fewer than $k$ survivors — no code can do better, and Reed-Solomon hits the line exactly.
• And it's efficient. Encoding and decoding are matrix/polynomial operations over a finite field — fast, deterministic polynomial-time algorithms, not a brute-force search.

So unlike the P vs NP hard problems elsewhere on this site, erasure coding sits in the comfortable corner: the optimum is known, achievable, and cheap to compute.

"Survive losses without paying for full copies" is one of the most valuable guarantees in computing, and erasure coding delivers it everywhere:

• Cloud object storage: systems like Azure Storage, Facebook's HDFS and Ceph store data as $n$-of-$k$ shards across machines and racks, cutting durability overhead from 200% (3× replication) to ~50%.
• RAID arrays: RAID 6 is small-scale erasure coding — two parity shards let any two disks in an array fail without data loss.
• CDs, DVDs and QR codes: Reed-Solomon error correction is why a scratched disc still plays and a partially obscured QR code still scans.
• Deep-space communication: NASA missions code their telemetry so the data survives the noise of an interplanetary radio link, where retransmission is impossibly slow.

The same polynomial idea also shows up in error correction — see Hamming codes and Reed-Solomon codes for the closely related task of fixing bit errors rather than recovering lost shards.

Erasure coding takes the crude idea of "keep extra copies" and replaces it with something far more elegant: scatter your file into $n$ mathematically intertwined shards, and any $k$ of them rebuild the whole — no matter which $k$. The redundancy is spread thin and used to the theoretical limit.

It is one of the satisfying results in this collection: a problem that is completely solved, with a construction that is both optimal (it meets the Singleton bound) and efficient (polynomial-time encode and decode). The next time a disk dies in a data center and nobody notices, thank a 1960 polynomial — and the quiet certainty that any $k$ survivors are all you ever needed.