[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.
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