Re: Consistency question

On Wed, 15 Jan 2014 14:00:30 +0000, David Kastrup wrote:

Andreas Krey [off-list ref] writes:

...

quoted

Hmm, how about traversing from all the start commits downwards
simultaneously, noting which start you say each commit from, and stopping
when you have a commit carrying all start labels?

It means that when the start commits are at considerably different
depth, you'll traverse much more material than necessary.

But it has the advantage that you don't need to traverse the DAG
to the root when the differences are small - the runtimes are roughly
proportional to the difference between the commits.

Also you need labels.

Yes, I assume that that (marking commits) is not a cost factor.

quoted

I don't quite see how the same size plus lockstep works out (but the
'same size' part is possibly the same as my 'concurrent traversal').

It just equalizes the depth before starting, so you don't need labels:
any common ancestor is reached at the same time by its descendants.

Of course, I conveniently forgot merge commits.

I finally noticed but forgot to mention in the last post.

Merges also mean that there is not necessarily a unique common
ancestor between commits.

Andreas

-- 
"Totally trivial. Famous last words."
From: Linus Torvalds <torvalds@*.org>
Date: Fri, 22 Jan 2010 07:29:21 -0800