Re: [Monotone-devel] nuskool & certs created after a revision

[William Uther]

On 02/05/2008, at 10:08 AM, Lapo Luchini wrote:

> OK. It transfers the DAG oh-so-nice, and cleverly so too.

Yeah - 'tis a cool idea.

> Then they told me about the problem with certs: either they are sent  
> together the rev they refer to at once, or they never get sent later  
> as the rev is never sent again.

Yeah - Graydon had a plan for this I thought.  It vaguely sounded  
similar to yours, with some differences in details.  From memory it  
was something like: build a separate tree of certs based on time of  
cert creation, and sync it using the same nuskool algorithm.

While I can see that working, something feels a little untidy about  
it.  I started trying to think of other ways of doing it.

I came up with a method which was half-way between his and yours:   
Each rev keeps a hash of all the certs on all ancestor revs (each rev  
gets an xor of the fingerprints of all ancestor revs certs?).  First  
you sync revs using standard nuskool.  Then you sync revs using these  
new hashes.  A hash mismatch means there is a cert somewhere in the  
ancestor tree that isn't sent.  You keep searching backwards to find  
the first unsent cert along each branch of the DAG.  You send those  
missing certs.  Once you send a cert you need to update the hash  
values on all descendent revs (a local operation on the end that  
receives the new cert).  As those hashes have changed, you'll need to  
run the run the algorithm again over that part of the DAG to find the  
next cert to send.

I was unconvinced this was simpler than using a merkle trie for certs.

The only advantage of this over the merkle trie is that this algorithm  
takes advantage of locality - most certs are added near the leaves of  
the DAG.

Cheers,

Will       :-}