Erasure coding explained: Reed-Solomon codes and polynomial interpolation
Thread296 words
Explains erasure coding as redundancy that lets original data be rebuilt from any k of n pieces, using Reed-Solomon codes where a degree k-1 polynomial is determined by any k points.
Key claims
Any k of n pieces suffice to reconstruct the original data
A cubic polynomial can be reconstructed from any 4 points
What is Erasure Coding?
Erasure coding is an error correction technique. The key property is that, if the redundant data is available, the original data can be reconstructed in the event some part of the data gets lost. Even more importantly though, it doesn’t matter which part of the data is lost. As long as X% (tolerance threshold) of the data is available, the full original data can be reconstructed.
The maths behind erasure coding is pretty complex. For Reed-Solomon codes it's rooted in polynomial interpolation from finite field arithmetic, as in Reed-Solomon encoding, each row and each column of the data matrix can be seen as a separate set of data points, and each of these sets can be represented by its own polynomial. It works thanks to the property of polynomials that a polynomial of degree n can be uniquely determined by n+1 points. So, a cubic polynomial (degree 3) for example can be reconstructed if we have any 4 points from the curve.
More generally, if you want to encode k data pieces, you would use a polynomial of degree k−1. To add redundancy, you evaluate the polynomial at more than k points. The magic is that to reconstruct a polynomial of degree k−1, you then only need k points.
So basically, the key idea is that any k pieces of the n total pieces (original + redundant data) are sufficient to reconstruct the original data, because if you have enough data points remaining (thanks to the redundant points you added), you can recreate the polynomial and find the missing data points.
This is a snippet from my in depth research report on data availability that will drop soon. Stay tuned!👀
for more on erasure coding check this big-🧠 post by @whisker17
0xwhisker.hashnode.dev/erasure-code-deep-dive