[BitTorrent] Sharing packets

Robert C. Helling helling at atdotde.de
Tue Aug 24 06:23:29 EDT 2004


I learnt about bittorrent only a couple of minutes ago so please forgive 
me if this posting is not relevant (ie misunderstanding of my part, 
already considered, already implemented etc).

>From what I saw on the website, bittorrent works by chopping a file into 
pieces and then organising peers to share those pieces. Is this correct? 
Then there is the obvious question of what happens if there are collisions 
in the sense that A wants a piece that nobody else but the original server 
has. From what I see, you have spend some thoughts on how to prevent this 
but let me nevertheless make another suggestion:

There is an easy algorithm (involving some randomness) to start from a big
file (size L say) and derive from it a new file that is L/N in size (plus
some small, fixed size administrative overhead). That by itself is not
interesting. But every time you run this algorithm it produces a different
size L/N file, even if you run it much more often than N times. And now 
there is a reverse algorithm that takes _any_ (actually nearly any) N of 
the smaller files and reconstructs the original size L file from it. 
Actually it is possible to take M of the smaller files and produce new 
size N/L size files from them such that those tertiary files can replace 
any of the M files themselves.

So if you implemented this algorithm in bittorrent it would eliminate the 
need for bookkeeping and risk of collisions nearly completely. (Of course 
if a peer as only part of a file it cannot share more information than it 
already has but it is most likely to be independent of the information 
that other peers have and the probability for overlap of information would 
be reduced significantly).

This was the advertising bit. Now some technical details. This it how it
works: It is based on linear algebra and there is an easy visualisation.  
Assume that the information we would like to share is the position and
orientation of a plane in 3-space. Then this can be done by specifying
three points on it that are not on a common line. But any such three
points do the trick. So to spread out the information about the plane I 
tell people about random points on the plane. And whenever three of them 
come together they can share their points and reconstruct the plane. 

Now you do this with hyperplanes in N-space and this is your algorithm. 
For computer applications, it is of course better to use some finite field 
for your vector space in order to be able to do integer arithmetic and not 
floating point (with rounding errors).

This algorithm has of course many uses (RAID disks are one), distributing 
files over floppy disks with some redundancy is another one, but file 
distribution systems like bittorrent sound like an obvious other one.

Some time ago, we implemented the splitting and reconstruction programs in 
both Perl and C (as proof of concept) but I just realised that at least I 
don't have the C versions anymore. I only have the perl versions (that are 
very slow, C worked in a split second even on large files) and you can 
find them as


Usage (after unpacking) is 

./split.pl split 3 filename > a
./split.pl split 3 filename > b
./split.pl split 3 filename > c

to split filename in three parts a b and c (repeat ad lib) and then

./split.pl combine 3 a b c >out.file

which reconstructs filename as out.file.

Have fun

Robert C. Helling     Department of Applied Mathematics and Theoretical Physics
                      University of Cambridge
print "Just another   Phone: +44/1223/766870
    stupid .sig\n";   http://www.aei-potsdam.mpg.de/~helling

------------------------ Yahoo! Groups Sponsor --------------------~--> 
Make a clean sweep of pop-up ads. Yahoo! Companion Toolbar.
Now with Pop-Up Blocker. Get it for free!

Yahoo! Groups Links

<*> To visit your group on the web, go to:

<*> To unsubscribe from this group, send an email to:
    BitTorrent-unsubscribe at yahoogroups.com

<*> Your use of Yahoo! Groups is subject to:

More information about the BitTorrent mailing list