THE ERASURE CODE lose some packets, recover them from the rest — because the data is low-degree
Send more than you need and you can afford to lose some. An erasure code treats a block of data as a low-degree polynomial and transmits its value at several points; a receiver who gets anyk of the n transmitted values can reconstruct the whole thing by interpolation. Reed–Solomon codes work exactly this way, and it is why a scratched CD, a lossy network, or a distributed storage array can hand you back a file with pieces missing. The recovery is caused by the low-degree structure: a degree-(k−1) polynomial is pinned by k points (dart 294), so k survivors suffice — and remove that structure (raise the degree) and the missing pieces become unrecoverable.
THE TECHNIQUE data = a low-degree polynomial; any k of n values reconstruct it
Data encoded as a line (degree 1) sampled at three points; one is erased. The demo recovers it from the two survivors: live demo
HISTORY & CREDIT Reed-Solomon 1960 · Rabin 1989
“A lost packet is lost.” — if the data was sent as a low-degree polynomial with redundancy, any sufficient subset reconstructs it; the erased value is recomputed, not retransmitted. Redundancy with structure beats retransmission. cited
1960 · Irving Reed & Gustave Solomon — codes as polynomial evaluations; any k values recover a degree-(k−1) message. 1989 · Michael Rabin — Information Dispersal: erasure coding for reliable, efficient distribution. now · RAID, CDs/DVDs, QR codes, distributed storage (erasure-coded, not merely replicated).
Encode as a polynomial, oversample, and any k survivors pin it down. The structure — low degree — is what makes the lost pieces recoverable at all. Reed-Solomon 1960
RECOMMEND FOR I-13 erased packet recovered from survivors, computed
On the canonical compiler, data sent as the line y=2x+1 at x=0,1,2 loses the middle value; the two survivors (0,1),(2,5) reconstruct it to 3:
$ i13 run rec_erasure.i13 # recover the erased middle sample
slope = 2
recovered = 3 -- the lost packet, recomputed from the two survivors
Recommend: the erasure code is reconstruction where the structure is unmistakably load-bearing. i13 recovers the erased sample 3 from the two survivors by interpolation — and it works only because the data was a degree-1 polynomial: two points pin a line, so one erasure is survivable. Raise the degree past what the survivors can pin and the recovery is impossible (dart 294's determinant again). The missing information is not stored anywhere; it is recomputed from the redundancy the structure provides. This is the keeper axis in its most practical form: recover the whole from a sufficient part, caused by a preserved structure.