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

On Mon, 7 Mar 2005 17:21:38 -0800, Joseph Ashwood <[email protected]> wrote:
> From: "Konstantin 'Kosta' Welke" <[email protected]>
>> On Sun, 6 Mar 2005 17:36:43 -0800, Joseph Ashwood <[email protected]> wrote:

> [Optimal case for binary trees?]
>> In the case of "I need to verify this one piece to be able to share it".
> Actually the optimum case for that is having the verification in the node,
> regardless of branching. this then leads to the overhead to verification =
> depth, binary trees will be deepest, they are not optimal.

IBTD. Branching is as important as tree depth. In order to verify a
piece, one needs its hash. To verify the hash, you need all the siblings
and its parent. So the total number of nodes needed to verify a hash
is about braching*depth. Of course, this number decreases with every
piece we download, as we already have internal nodes.

> Searching is important when a piece is requested, there is a search overhead
> to determine whether or not that piece is available. Using a perfectly flat
> tree this is a search of the minimum possible area, using a binary tree it
> is a search of the maximum possible area. These represent the extremes
> available, the binary tree is the most costly.

I thought of an implentation where this search is not necessary. If a piece is
avaiable (i.e. downloaded and checked), some bit will be switched to 1 in a
bitfield of size p. Checking that is O(1) as we know which piece is requested.
I also thought that the tree nodes are numbered consequtively. (This is very easy
for a binary tree) This makes it possible to just use simple arrays to store
the tree, too. I think someone posted some basic math to do that on this list
about a month ago. In other words: All node-retrieving and storing operations
are done in O(1) time. This also means that calculating which nodes are necessary
for a piece are done in O(h*N) time.

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

> It is the second case (peer need). The overhead of this becomes critical as
> the trees and number of connections grows, it is linear in both but
> exponential in the combined. By adding overhead to the search for the next
> piece you slow down the tit-for-tat, on a single peer with a single file and
> a single connection, this is not ciritical, but as these numbers grow it
> becomes increasingly necessary to predict what your peers will want in order
> to reduce the computation overhead (i.e. don't flush it out of the memory
> cache).

I'll think about it, but cant we just evade the problem by letting the peer
that needs the nodes just request them?

> I didn't post about it. The search overhead problem is succinctly "find me
> piece with hash X" finding it in a Merkle tree is costly, binary is the most
> costly, flat the least, but finding it in a 256-ary tree in a shared
> MerklePool eliminates the advantage/disadvantage in this case.

Why dont just number the pieces. No search required.
And finding a node in an unordered tree in linear to the number of nodes, so there
should not be a very big difference between binary tree flat tree, as the
binary tree only has about twice the nodes of the flat one.

[tree construction]
> The better way is to compute all the nodes at a single level (this is where
> I began the use of the MerklePool), but the cost is primarily in the depth
> of the tree. as the depth increase it becomes necessary to maintain indexing
> across multiple levels, by flattening the tree this again exponential
> overhead is reduced.

Sorry, I dont understand :)

> Modern hashes have substantial overhead in the finalization operations, by
> having the smallest nodes possible the finalization code is executed the
> maximum number of times. As the size of the nodes shrinks linearly, the
> number of internal nodes increases super-linearly.

Not necessarily.

> As the number of nodes
> increases the number of times it is necessary to run the finalization code
> increases.

As the number of siblings on one level increases, this increases.

> I did have a misstep there, I believe it is only a polynomial
> increase, not exponential.

I think that is it polynomial in O(height^2) or something like that. I was
unaware of that problem, good that you mentioned it.

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

> Here is where we substantially differ. In verifying a single piece in a
> properly formatted n-ary tree (like my proposal) the cost is the tree depth.

I think that the cost is depth*N. How do you check a node without knowing
its silblings?

> This is the same optimal cost for binary trees. The n-ary tree will be
> flatter and so offers faster verification of the piece than the binary
> version. For reference, my implemenation can verify a single piece of a
> 478MB file in 4 hashes, assuming 4KB blocks, the same performance for a
> binary tree would only be a 65KB file, again assuming 4KB blocks. Verifying
> the same 478MB file would take a binary tree 29 hashes (assuming I counted
> correctly) approximately 7 times as long. 7 times the time is not a small
> performance penalty.

Could you write out what exactly is calculated here? Are you assuming
that you only need all ancestors of a leaf to verify it and its contents?

>> 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.
> I agree a simulator would be of great help.

Lets start with a tree calculator! ;)

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

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