Re: Have maps (was Merkle, URLs, etc)

----- Original Message ----- 
From: "Elliott Mitchell" <[email protected]>
Subject: Re: [BitTorrent] Have maps (was Merkle, URLs, etc)


>>From: Joseph Ashwood <[email protected]>
>> In my view there is no need for another problem. The binary trees create
>> pure bloat that serves no purpose except to provide for more bloat.

> The majority seems to disagree with you and think binary Merkle trees
> will work fine.

I have never argued that binary Merkle trees would not "work fine" I have
always said that they are wasteful of every possible resource and provide
only for increasing the pure overhead. I have also continually sided with
using n-ary trees which would make it so that those people who wish for
their own reason to use binary trees are welcome to do so.

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

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

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.

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 agree that binary trees appear to be very much sub-optimal, but this
> isn't a fatal flaw. Unless you can bring up some fresh new aspect of this
> issue, would you please shut up about this issue?

Besides the simple fact that the choice of binary seems to be based on "but 
it's easier to program" which it isn't I believe I have also brought up the 
necessary branching factor in the verification, but there is also a 
pre-caching problem, a search overhead problem, a construction problem, an 
indexing problem, and a hash size vs input size problem, just off the top of 
my head.

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.

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

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

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

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.

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



 
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:
    [email protected]

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