[BitTorrent] Sharing packets
Harold Feit - Depthstrike.com Administrator
dwknight at depthstrike.com
Fri Aug 27 12:50:37 EDT 2004
There is no 100% sure-fire way to implement a function into the BitTorrent
protocol that completely prevents these sort of collisions of missing data,
simply because of the possibility that anyone with data that is otherwise
missing from the swarm could disappear off the face of the earth at any
given time. There is however an already-implemented seeding algorithm
designed specifically to deal with situations where a number of pieces of a
torrent are absent or rarer then the others.
http://bittornado.com/docs/superseed.txt is the technical document on John
Hoffman's Super-Seed mode which is designed specifically to prevent that
sort of collision set in the initial seed base. The algorithm was designed
primarily for the initial seeding of a file or for a reseed later on when
self-sustainability of the torrent has been lost.
I've actually seen how super-seed mode works in situations where a torrent
is started and other people who download from the torrent already have
pieces of it (usually in the case of multiple file torrents where someone
gets one or more of the files from another source. With that super-seed
mode, when a small set of pieces exists already on the torrent, those pieces
aren't uploaded by any super-seeds until after all other pieces that have
not yet been uploaded are. Because of these supplemental partial-seeds, I
have seen a torrent reach self-sustaining capabilities before the 75% mark
in total uploaded.
I haven't gone over the code in the algorithm you're proposing yet so I
don't know for sure how different from the primary seeding algorithm or
super-seed mode it is, but I do know that there is already code implemented
in advanced clients that has been written for handling the absence of rare
From: Robert C. Helling [mailto:helling at atdotde.de]
Sent: Tuesday, August 24, 2004 7:23 AM
To: BitTorrent at yahoogroups.com
Subject: [BitTorrent] Sharing packets
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
University of Cambridge
print "Just another Phone: +44/1223/766870
stupid .sig\n"; http://www.aei-potsdam.mpg.de/~helling
Yahoo! Groups Sponsor
Yahoo! Groups Links
a.. To visit your group on the web, go to:
b.. To unsubscribe from this group, send an email to:
BitTorrent-unsubscribe at yahoogroups.com
c.. Your use of Yahoo! Groups is subject to the Yahoo! Terms of Service.
Outgoing mail is certified Virus Free.
Checked by AVG anti-virus system (http://www.grisoft.com).
Version: 6.0.744 / Virus Database: 496 - Release Date: 8/24/2004
[Non-text portions of this message have been removed]
------------------------ Yahoo! Groups Sponsor --------------------~-->
$9.95 domain names from Yahoo!. Register anything.
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