[p2p-hackers] Error correcting codes to prevent failure in BitTorrent like systems?

[Nick Johnson]

coderman wrote:

> you are assuming there was at least one complete distribution.
>
>in the situation you describe (last seed leaves) some of the remaining
>peers do then become seeds as they obtain requisite missing chunks to
>complete the torrent, if the remaining peers have the blocks required
>to complete what is missing.  i don't see how error codes would be an
>improvement (considering coding overhead / expansion), unless the
>distribution of blocks using the current bittorrent algorithm was
>heavily weighted somehow. (is it?)
>
>if a complete copy has not been distributed within the group then it
>doesn't matter what encoding mechanism you use, and in my experience
>this has been the usual cause of partial failures.
>  
>
No, the point behind using ECC is that you don't need a complete 
distribution, only 90%. Here's some stats:

Assume a file is distributed in 1000 blocks. The last seed goes offline, 
leaving 4 peers, each with an average of 500 blocks. Between them, they 
will, on average, have 1 - (500/1000)^4 percent of the blocks - 93.75%. 
The lieklihood of them having the entire file is (1 - 0.5^4) ^ 1000 - a 
very, very small number (approximately 10^-30).

However, if we precode this file into 1100 blocks, of which only 1000 
are required, assuming the same 500 blocks per peer, they have on 
average 1 - (600/1100)^4 percent of the blocks - 91.1%. Since they only 
require 10/11 (90.9%), they will usually have enough to reconstruct the 
original file. Unfortunately, I can't recall the neccessary stats to 
calculate the exact chance of success.

-Nick Johnson