[bittorrent] question on the blocks downloading in BT

Simon Spero ses at unc.edu
Sun Jun 12 10:59:06 EDT 2005


Elliott Mitchell wrote:

>For an example. Imagine getting  piece #n blocks 1-4 from peer 1, and
>piece #n blocks 5-8 from peer 2, due to peer 1 disconnecting;
>subsequently piece #n fails hash check. You now ask for piece #n blocks
>1-4 from peer 2. If piece #n now checks correctly, peer 1 was at fault.
>If piece #n doesn't check correctly, peer 2 was at fault, and blocks 1-4
>from peer 1 can still be used
>  
>
This approach doesn't quite work; this case reduces to the Byzantine 
General  problem; there's no solution unless 2/3rds of the peers are honest.

In the example above, if the checksum fails all that you can determine 
is that peer 2 is dishonest; we still don't know if peer 1 was dishonest 
too. 

For bittorrent, you can't tell who is honest and who is dishonest until 
you have sucessfully verifed an entire piece.

There's a nice summary of the classic Lamport et. al. paper on the BGs 
at the link below.  (no, it's not in LaTeX format :-)

   http://www.cs.wisc.edu/~sschang/OS-Qual/reliability/byzantine.htm



More information about the BitTorrent mailing list