A Gentle Introduction to Erasure Codes (2017)
akalin.com
akalin.com
I always wanted to know but was afraid to ask. I see why people choose Cauchy for encoding: it's simple and fast (more foolproof? - that I don't see). However, Cauchy erasure decoding would always involve matrix inversion, which is not as simple and fast (Hadoop 3.0 is a good example). But what do people do when they want to do error correction after Cauchy encoding?
I think we discussed a while ago doing Vandermonde decoding without matrix inversion, so that’s one advantage that Vandermonde matrices have. (Although I haven’t seen an implementation do that optimization.)
I don’t actually know if Cauchy matrices apply for error correction and not just erasure codes —- I’d be interested if other people know!
> The recovery algorithm had a bug, due to a flaw[1] in the academic paper[2] on which it was based.
I remember that the same bug was cited by ZFS[3]. Amazing. Of all algorithm descriptions, one with a bug seems to have been picked up the most. Of course, there is nothing wrong with Vandermonde encoding itself, just don't use that paper any more.
Cauchy is equivalent to Vandermonde, so it should allow for error correction to the same extent but I couldn't find any algorithm description/implementation.
[1] Plank, James S.; Ding, Ying (April 2003). "Note: Correction to the 1997 Tutorial on Reed-Solomon Coding"
[2] Plank, James S. (September 1997). "A Tutorial on Reed-Solomon Coding for Fault-Tolerance in RAID-like Systems"
[3] https://github.com/illumos/illumos-gate/blob/master/usr/src/...