Re:Network Coding in P2P Networks
by bfuclusion on Monday August 24, 2020 @01:48AM
(#24257824)
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.
[ Parent
| on HN ]
Re:Network Coding in P2P Networks
by lowercase1 on Monday August 24, 2020 @10:26AM
(#24260968)
Ooh interesting, I'd be interested in that code/work. I'm somewhat familiar with Tornado codes but haven't looked in years
Re:Network Coding in P2P Networks
by bfuclusion on Monday August 24, 2020 @09:41PM
(#24267411)
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.