4 ms·

Reed Solomon might run into issues with it's n^2 runtime if you make too many pieces. Fountain codes or other codes though could do the job.

sliken 6y ago
Heh, don't let computer science blind you to the real world realities of running something. Sure the n^2 time will dominate somewhere before infinity, doesn't mean that Reed Solomon is slow for practical use cases. I have a 19GB test file on a desktop Xeon e3-1230 v5 (a quad core Intel from 2015) and an encoder written in Go (not the fastest language). I can turn a 19GB file into 10 2.4GB files in 44 seconds, I can recover the original with any 8 of the 10 files. That sounds pretty slow, but it is reading 19GB and writing 24GB. In fact when I watch with top it looks like it spends a good while reading in 19GB, spends 1-2 seconds running the Reed Solomon calculation on 4 cores, then spending a bunch of time writing out 10 2.4GB files. So Reed Solomon is fine even on a 6 year old computer on a pretty large file. I suspect a current 8 core desktop from 2020 could do even a 100GB file without taking noticeably long. After all a 100GB file shared over a p2p network is going to take WAY longer than the reed solomon calculation. Similarly I expect a recent vintage android phone or IOS phone could manage similar not to differently than a 6 year old desktop.
bfuclusion 6y ago
Take a look at tornado codes if you want a rated (instead of rateless) erasure code. It's related to fountain codes (and linked on the wikipedia article), and does basically the same thing as Reed-Solomon but with quasi linear encoding, IIRC n(log*n). I have to check if the patents expired, but my masters work was adapting BitTorrent to be backed by Tornado codes. Works surprisingly well since the original BitTorrent is structured around blocks anyways. I have the Ruby code around somewhere. When I modeled it, when the last seed left you'd need about half to one quarter the number of non-seed nodes in the network to be able to reconstruct the file.
- lowercase1 6y ago
  Ooh interesting, I'd be interested in that code/work. I'm somewhat familiar with Tornado codes but haven't looked in years
  - bfuclusion 6y ago
    I'll have to go searching (been 13 years), but conceptually building a tornado encoder is a multi stage pipeline with input blocks and output blocks depending on how the bipart graph is set up. Once you have that you extend the bittorent block dictionary a bit and you're pretty much there.

sliken 6y ago

Heh, don't let computer science blind you to the real world realities of running something. Sure the n^2 time will dominate somewhere before infinity, doesn't mean that Reed Solomon is slow for practical use cases. I have a 19GB test file on a desktop Xeon e3-1230 v5 (a quad core Intel from 2015) and an encoder written in Go (not the fastest language). I can turn a 19GB file into 10 2.4GB files in 44 seconds, I can recover the original with any 8 of the 10 files. That sounds pretty slow, but it is reading 19GB and writing 24GB. In fact when I watch with top it looks like it spends a good while reading in 19GB, spends 1-2 seconds running the Reed Solomon calculation on 4 cores, then spending a bunch of time writing out 10 2.4GB files. So Reed Solomon is fine even on a 6 year old computer on a pretty large file. I suspect a current 8 core desktop from 2020 could do even a 100GB file without taking noticeably long. After all a 100GB file shared over a p2p network is going to take WAY longer than the reed solomon calculation. Similarly I expect a recent vintage android phone or IOS phone could manage similar not to differently than a 6 year old desktop.

bfuclusion 6y ago

Take a look at tornado codes if you want a rated (instead of rateless) erasure code. It's related to fountain codes (and linked on the wikipedia article), and does basically the same thing as Reed-Solomon but with quasi linear encoding, IIRC n(log*n). I have to check if the patents expired, but my masters work was adapting BitTorrent to be backed by Tornado codes. Works surprisingly well since the original BitTorrent is structured around blocks anyways. I have the Ruby code around somewhere. When I modeled it, when the last seed left you'd need about half to one quarter the number of non-seed nodes in the network to be able to reconstruct the file.

lowercase1 6y ago
Ooh interesting, I'd be interested in that code/work. I'm somewhat familiar with Tornado codes but haven't looked in years
- bfuclusion 6y ago
  I'll have to go searching (been 13 years), but conceptually building a tornado encoder is a multi stage pipeline with input blocks and output blocks depending on how the bipart graph is set up. Once you have that you extend the bittorent block dictionary a bit and you're pretty much there.