[BitTorrent] Re: Trackerless BitTorrent

sh4dowmatter mgp at ucla.edu
Fri Dec 31 03:23:39 EST 2004

I'll confess I haven't read everything in this thread, so I apologize
in advance if my two cents are out of context:

1) First, if you're going to have peers gossiping with each other,
swapping lists of peers they're connected to as a discovery mechanism
for new peers, you can use Bloom filters to drastically reduce
overhead. A Bloom filter, put simply, is a compact way of representing
a set. Say A has a peer list; he uses this peer list to construct a
Bloom filter denoting it, and sends it to peer B. B goes through each
peer in its list, one by one, and checks of it is caught by the Bloom
filter. If a peer is not caught by the Bloom filter, A is guaranteed
not to have it. The only caveat: Bloom filters have a 'false positive'
aspect, meaning B may think that A already has a peer because it is
caught by the Bloom filter, although A doesn't have it. Fortunately,
the false positive rate is tunable and can be made
almost-insignificant for all practical purposes while still saving a
lot of ovehread. Finally, B returns to A not caught by the sent Bloom
filter, expanding A's peer list. A Bloom filter is very easy to code;
see here:
* http://www.perl.com/lpt/a/2004/04/08/bloom_filters.html
* http://www.cs.wisc.edu/~cao/papers/summary-cache/node8.html

2) I know that for 'epidemic algorithms' such as the gossip mechanism
above, information can travel through N peers in log(N) time if the
network is 'well connected' -- which is quite fast. In the scenario in
which I've seen this, N nodes all know about each other and
occasionally each node pings another node, asking it if any new peers
have connected to it as a gateway/bootstrap node. So assuming that the
network is well connected enough when the tracker dies (what is the
typical peer distribution on a BitTorrent network -- power-law?), this
bound might hold. Now assuming that all nodes try to pull new peers
from one another with roughly the same frequency, the network should
stay well connected (indeed, it should become _better_ connected) and
you won't have fragmentation or islands of peers.

- shadowmatter

------------------------ Yahoo! Groups Sponsor --------------------~--> 
$4.98 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 mailing list