find_difference shortcut failure without walking out

[Aaron Bentley]

-----BEGIN PGP SIGNED MESSAGE-----
Hash: SHA1

John Arbash Meinel wrote:
> The only algorithm I can think of off-hand, is the Greatest Distance From
> Origin that Aaron and Robert talked about in London. Basically, every node is:
> max(parent_distances) + 1.

It seems to me that the problem here is finding the right stop
condition; stop too early and you incorrectly determine nodes to be
"uncommon", stop too late and you waste resources.

So when can we stop?  When it's impossible that we can determine any
more nodes to be common.  Since ancestry is a DAG, we know that no
descendant of a node can also be its ancestor.  In order for a searcher
to find that a previously-uncommon node is common, it must search from
an ancestor of that node.

Therefore, when all search nodes are descendants of all
apparently-uncommon nodes, we can stop.

Does that make sense?  Have I missed anything?

Aaron
-----BEGIN PGP SIGNATURE-----
Version: GnuPG v1.4.6 (GNU/Linux)
Comment: Using GnuPG with Mozilla - http://enigmail.mozdev.org

iD8DBQFHYMBw0F+nu1YWqI0RAs+IAJ9HgupoQxhDlT5jzDy1ViyTeW1dzgCghlLE
2cmSyisaophb288pKVTVZ1c=
=f7vM
-----END PGP SIGNATURE-----