4 ms·

From the theoretical point of view we can get huge improvements both in terms of torrent availability and latency, by making use of "fountain codes". Basically

From the theoretical point of view we can get huge improvements both in terms of torrent availability and latency, by making use of "fountain codes". Basically it is a family of error correcting code which splits the data in N+M distinct pieces, and allow you to reconstruct the data once you have any distinct N of these pieces. This allow you to seed any one of these small pieces yet allow the reconstruction of the whole data provided there are enough other people seeding other pieces (Typically number of "seeds" will increase between x100 and x1000 (Note that it obviously don't increase the outgoing bandwidth of your network, but it makes it a lot easier to conserve and distribute rare files). Which also means any of these pieces can help getting the first packets needed to begin streaming which reduces latency. The negative aspects, are : - bigger "torrent" files (because you need to store the hashes of more pieces). - Some time you'll download an extra piece. - More compute power needed on the clients to decode the stream. - More complexity in the code. Why is it not implemented ? Mainly because it is not a standard yet. There is quite a lot of freedom in the ways to implement it, and it will probably fracture the pools with plenty of non compatible protocols. And if you have a new version of the protocol to improve some things you need the seeds to re-encode the data to be protocol compatible. That is also probably a subject which is encumbered by software patents. Economically targeting the fat tail of rare torrents is probably not worth it. It's fun algebra you should check if you don't know it already :)

elcritch 8y ago
It’s pretty straightforward math! I did an M:N implementation in Elixir via on shamir’s key sharing [1]. As you say, there’s no real standard for how to pack the hash bytes for even basic Shamir’s and so I followed Hashicorp Vault’s impl and tested it to their test data. Multiplexing an entire file over this wouldn’t be too hard, but the index/hash table would be need a good protocol. Wasn’t there some cloud storage systems tried using M:N at one time.. Plus the recombination computation can get expensive over lots of data. 1: https://github.com/elcritch/keyx https://github.com/elcritch/keyx
eximius 8y ago
Decentralized storage is already barely economical compared to centralized storage, if it makes sense at all. While this might reduce latency, it sounds like in practice it'd multiple the redundancy of the system and make it even less cost effective?
- GistNoesis 8y ago
  Quite the opposite (it's like a RAID storage system), because of the error correcting scheme, you need a lot less storage to provide a good level of redundancy. You only need to store pieces of size 1/N * file size, and as long as you can get N of those pieces you can reconstruct the file. To guarantee a high level of availability, you only need that there are more than N hosts up containing distinct pieces. So typically you will use (~3 * size of file) of storage on your network, instead of (number of seeds * size of file) bits, and still provide with the same level of service as if number of seeds where seeding the whole file. So each node is able to store a lot more pieces of other files.
  - eximius 8y ago
    I might need to look up how they work because that's basically what my next question is: how do the chunks overlap and how does that affect the probability of a file being unrecoverable? If I have a stupid simple scheme where I split a file into 100 pieces and replicate each piece 3 times, I have a 100C1 * p^3 chance of irrecoverability where p is the independent probability of pieces dropping out. I guess I just want to know, given arbitrary p, what the probability of the file being gone is.
    - GistNoesis 8y ago
      Error correction codes are quite magical. Instead of splitting in 100 pieces each piece 3 times, you split it in 300 distinct pieces of size 1/100 * filesize, which any 100 can reconstruct the file. So basically you can drop 2/3 of the pieces and yet be able to reconstruct the file. So as long as your nodes uptime is greater than 33% + eps, the file is not gone. The eps is quite small because of the law of great number. For example if your node uptime is 50%, the pieces will be in average available on 300 * 50% = 150 +- C*uptimevariance /sqrt(N) nodes which is greater than 100 with probability ~ 1, so the file will be recoverable almost surely.

elcritch 8y ago

It’s pretty straightforward math! I did an M:N implementation in Elixir via on shamir’s key sharing [1]. As you say, there’s no real standard for how to pack the hash bytes for even basic Shamir’s and so I followed Hashicorp Vault’s impl and tested it to their test data. Multiplexing an entire file over this wouldn’t be too hard, but the index/hash table would be need a good protocol. Wasn’t there some cloud storage systems tried using M:N at one time.. Plus the recombination computation can get expensive over lots of data. 1: https://github.com/elcritch/keyx https://github.com/elcritch/keyx

eximius 8y ago

Decentralized storage is already barely economical compared to centralized storage, if it makes sense at all. While this might reduce latency, it sounds like in practice it'd multiple the redundancy of the system and make it even less cost effective?

GistNoesis 8y ago
Quite the opposite (it's like a RAID storage system), because of the error correcting scheme, you need a lot less storage to provide a good level of redundancy. You only need to store pieces of size 1/N * file size, and as long as you can get N of those pieces you can reconstruct the file. To guarantee a high level of availability, you only need that there are more than N hosts up containing distinct pieces. So typically you will use (~3 * size of file) of storage on your network, instead of (number of seeds * size of file) bits, and still provide with the same level of service as if number of seeds where seeding the whole file. So each node is able to store a lot more pieces of other files.
- eximius 8y ago
  I might need to look up how they work because that's basically what my next question is: how do the chunks overlap and how does that affect the probability of a file being unrecoverable? If I have a stupid simple scheme where I split a file into 100 pieces and replicate each piece 3 times, I have a 100C1 * p^3 chance of irrecoverability where p is the independent probability of pieces dropping out. I guess I just want to know, given arbitrary p, what the probability of the file being gone is.
  - GistNoesis 8y ago
    Error correction codes are quite magical. Instead of splitting in 100 pieces each piece 3 times, you split it in 300 distinct pieces of size 1/100 * filesize, which any 100 can reconstruct the file. So basically you can drop 2/3 of the pieces and yet be able to reconstruct the file. So as long as your nodes uptime is greater than 33% + eps, the file is not gone. The eps is quite small because of the law of great number. For example if your node uptime is 50%, the pieces will be in average available on 300 * 50% = 150 +- C*uptimevariance /sqrt(N) nodes which is greater than 100 with probability ~ 1, so the file will be recoverable almost surely.