[BitTorrent] Have maps (was Merkle, URLs, etc)

Konstantin 'Kosta' Welke kosta at fillibach.de
Mon Mar 7 15:22:41 EST 2005


On Sun, 6 Mar 2005 17:36:43 -0800, Joseph Ashwood <ashwood at msn.com> wrote:

>>  There are certainly places where they are far from ideal,
>> but
> You forgot one critical aspect, there is no location where a binary Merkle
> tree is ideal.

They are the quickest way of getting a partial tree to verify one
piece.

>> remember that a flat DB is also far from ideal in some places.

Same for binary trees.

> And now you are once again mistaking my preferred usage scenario with the
> formatting I have suggested. Besides that rather critical
> misinterprettation, name even a single case where a completed DB that is not
> as flat as possible offers performance gains over one that is flat.

In the case of "I need to verify this one piece to be able to share it".

> I'll save you some effort, it doesn't exist. This is the search difference
> between hash-search and binary search. A hash search breaks the rules by
> enabling indexed searching.

I do not quite follow you here... I think that the tree implementation should imply
what hash is whose parent and child (for binary trees, this is very easy).
So there is no need for "searching". Did I miss something?

> The pre-caching problem is this: The computations necessary to predictively
> load the next requested nodes from disk is exponentially more complex with
> binary than with as flat as possible.

Just so I get it right: Are you talking about "What partial trees do I need
next?" or "What partial trees does my peer need?". In the first case, I
cant follow you (should be logarithmic, just like for all trees). In the second
case, I can neither see a computational difference.

> The search overhead is related but can be solved using some of the more
> esoteric possibilities of the MerklePool concept I laid out before.

Sorry I must have missed both the problem and your solution. Can you point
me to a date/time and subject of your message so I can re-read it?

> Construction problem is that with each layer of the tree that is build
> maintaining anything resembling balance (necessary in order to make noth the
> pre-caching and search problems as easy as possible, even though still far
> worse than n-ary) becomes increasingly difficult and as it requires an
> exponential time algorithm, this can become very costly

The total size of the tree should be easy to calculate for all n-ary trees.
I dont see how balancing makes any sense in a Merkle Tree as it cannot
save any space. Is there a better way than the naive approach of constructing
an n-ary tree? (Naive meaning the first n leaves have one parents, the first
n parents have a parent etc. Disadvantage is that the tree tends to get empty
towards the end in non-optimal cases).

> Indexing problem. In short you run out of indexes much faster this way.

I agree. If using an unsigned :) 32-bit integer as hash index, you can store
2^32-1 leaf hashes in a flat tree, but only 2^31 leaf hashes in a (perfect)
binary tree. For 4K piece size, this is the difference between 16 Terabyte
and 8 Terabyte maximum file size.

> The hash size vs input size problem is that the hashes used slow down as
> there is less input, leading to exponential slow down of the entire system
> as the inputs shrink.

Can you please rephrase this sentence so that I can understand it?

> Is that enough problems or should I think for more than 30 seconds on it?

Please think of more. ;)

Note that I do neither think that binary trees are the best choice. They are
worst case for tree size but optimal case for quick verification of a single
piece. To know if this is really relevant, this bittorrent simulator might
be helpfull (I think I'll start coding next week). If it is irrelevant, we
should use flat trees. I not, a tradeoff using n-ary trees seems good.

Does anyone have a good URL about n-ary trees that goes a bit further
than http://www.brpreiss.com/books/opus5/html/page257.html and
http://www.utc.edu/Faculty/Christopher-Mawata/petersen/lesson13.htm ?

Kosta


 
Yahoo! Groups Links

<*> To visit your group on the web, go to:
    http://groups.yahoo.com/group/BitTorrent/

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

<*> Your use of Yahoo! Groups is subject to:
    http://docs.yahoo.com/info/terms/
 





More information about the BitTorrent mailing list