[Monotone-devel] Re: Scalability question

[Steven E. Harris]

Nathaniel Smith <address@hidden> writes:

> The merkle trie synchronization algorithm is a set synchronization
> algorithm -- given a set of items here and a set of items there,
> each with a unique id, it lets each side figure out what it needs to
> send so that the other side will end up with everything in either
> set.

Perfect. That's what I have to do in the program I'm developing, but
there's still a disconnect. All that I've read about Merkle Trees
discuss applying them to a stream or sequence of leaf-level data. To
work with sets, it seems that one would need to flatten the set into a
sequence before building a Merkle Tree on top of it, and the two sides
comparing would need to agree on a ordering scheme or the same sets,
ordered differently, could produce two very dissimilar trees, save for
the leaf-level nodes.

It's not too hard to come up with /some/ strict weak ordering scheme
for the set items, but the Merkle Trees seem to be most beneficial
when they help discover a lot of "shared structure", meaning that the
differences needing synchronization would be easy to spot
quickly. Hence, it would be best if the flattened set sequence "grows
to the right" (choosing one direction arbitrarily), meaning that over
time the summarizing hash tree is most stable to the left and changes
only at the right edges. That preference points toward a set ordering
scheme that puts "newer" items last (to the right).

Do you agree with the above argument? Does monotone use an ordering
scheme on the sets of keys, epochs, and certs that favors putting
newer items to one side or the other, or at least clumping older items
together?

> content addressing makes storage easier and reduces the severity of
> bugs,

How so?

> stateless protocols make everything easier and reduce the occurrence
> of bugs, the ability to magically pick up where one left off,
> without any special code paths, definitely reduces user frustration
> and increases error recovery.

These are the properties I'm after in my program. It's reassuring to
hear that the techniques we're discussing work toward the goal.

> citeseer might be better than google in this case, if you really
> want background reading.

Thanks, I found more there to study.

-- 
Steven E. Harris