grack.com

I posted the analysis from earlier to the Bittorrent development mailing list. I received a reply from Bram Cohen illustrating one flaw in the argument:

You make the assumption that the probabilities of different clients having a given block are decorrelated, which is wrong. That’s the point of rarest first, it makes it so that if one peer doesn’t have something it’s more likely that another peer will.

Yeah - good point. I had neglected to factor that in - and it makes all the difference. In fact, with rarest first, it’s quite likely that both of those situations described have a 100% recovery probability (reading the source, it appears that rarest first kicks in after you’ve downloaded 4 blocks, and will ensure that each block has at least 3 peers hosting it).

I’ll put forward a slightly different case - it may be such a rare case that it might not be worth worrying about. It’s probably good to at least understand where the (potential) weaknesses might be, even if the probability is fairly low of being exposed to them.

We can take the situation from before and add another network failure - one of the remaining nodes drops off. I’ll use the case where the rarest first algorithm has ensure that each node has a fully disjoint set of pieces from the initial download (though there will likely be *some* overlap due to the random first downloads).

Each of the 30 nodes has 5% of the 200 pieces = 10 blocks. This yields 300 pieces total in the system: 50% of the blocks have a single peer, while the other 50% have two peers hosting it. Rarest first has kicked in here, but hasn’t completely propagated the blocks out yet.

The probability that any given block is dropped out of the system by this event is the weighted sum of these two probabilities:

1. Only one of these blocks in the system: 50% * probability that the block was hosted on the node that went down. There are 30 peers, so the chance is 1/30.
2. More than one of these blocks in the system: 0% (there will always be the other block to download)

The probability is then 1/60 that the block went down, or 59/60 that it survived. The probability that each of these 50 blocks (the blocks without a redundant copy somewhere) survived is (59/60)^50 = 43.16%. This is a 56.84% chance that the extra node dropping off took an essential block with it, leaving the network with a maximum completion percentage of 199/200 = 99.5%.

In the Reed-Solomon case (400 blocks total, 200 required), there would still be 290 distinct blocks left, more than the 200 required to recover the system.

As I mentioned before, both of these cases assume that the downloaded blocks are fully disjoint. The math would certainly be more difficult to determine without this assumption, however.

So - I believe that this would a case where redundant encoding would be better, but how likely is it for the network to encounter this situation? Is it worth programming for this case? Is this case representative of a lot of torrents?

The question remains open.