Re: [Gnu-arch-users] Star-merge Fatally Wounded

[David Allouche]

On Fri, 2004-09-10 at 12:52 -0700, Tom Lord wrote:
>     > From: David Allouche <address@hidden>
> 
>     >         Merge scenario
> 
>     >         A-0 =====> B-0 
>     >          |          |
>     >          |          |
>     >         A-1 --  -- B-1  
>     >          |    \/    |
>     >          |    /\    |
>     >         A-2 <-  -> B-2
> 
> 
> [Nicely lucid message and elegant proof, by the way.  Thanks for
>  taking the time.]

Thanks for the appreciation.

> I believe that what you have in that scenario (since you are planning
> on using star-merge and maintaining a star topology) is, alas, a user
> error.  But let me explan and qualify that and ack that you do have a
> real technical problem that needs attention and make a few suggestions
> about how to solve it.
> 
> Here's the user error:  Which existed first?  A-2 or B-2?   
> 
> Without loss of generality, let's assume that A-2 existed first.
> 
> Then B-2 was created, *in effect*, by:
> 
>       % tla get B-1 
>         % cd B-1
>         % tla star-merge A-1          [***]
>         % tla commit
> 
> The [***] step is the "user error" because, at that time, A-1 is not
> the latest revision.  A-2 was the latest revision (in the absolute
> scheme of things) when that merge was done.

I think we already have that "barrier of languages". In my understanding
your assumption does cause a "loss of generality", and I just cannot
understand what you mean by "in effect".

This scenario arise when the actors only do locally legal merges.
A locally legal merge is merging with the last known revision in the
other branch. The knot of the problem is that "which of A-2 or B-2
happened first" is a question which has no answer in the general case
for *physical* reasons: these are two events happening in different time
lines with no relation of causality. The order in which A-2 and B-2 seem
to happen can be different in timelines A and B.

We have informally pegged merging in this scenario the "relativistic
merge problem" because the root problem is one of Relativity. Thanks
Albert.

Archive mirrors and a pqm running lengthy test suites can exacerbate the
problem, but they only widen the race window, they do not create it.
This race condition cannot be avoided without additional out of band
synchronisation. The existing Arch best practises as I know them do not
require such synchronisation.

Up to now, all that a user needed to know about star-merge was this
simple contract: merge related branches using that operator exclusively
and you will not have spurious conflicts. This contract is not
fulfilled. Either the contract or the tool needs fixing.

No amount of rethoric can make a breach of contract into a user error.

> A proof that nobody can find a general solution is not much harder
> than the proof you have given for why star-merge isn't a general
> solution.  I don't have time ( :-) right now to write (again) such a
> proof myself but here's a hint: in addition to drawing merge diagrams,
> you might try adding some sample file contents.  It isn't that hard to
> construct examples of file contents for which automated merging in
> scenarios like this one is impossible unless the merge tool is an AI
> program that understands what the programmers are trying to do.

That would be a useful proof to have written down in public, since it
would demonstrate the need for a synchronisation protocol.

Whether such a synchronisation protocol can be reliably implemented in
software is another open question.

I do not grok idempotent merging, but from what I gathered, there is a
solution to the problem which is not absolutely correct but whose
usefulness is comparable to diff/patch. Good enough for me.

But we still lack a proof that the problem cannot be solved using
technique which is a lower-hanging fruit than idempotent merge. 

> Short answer, for your immediate needs: if I were you, I'd first try
> to eliminate the race conditions in your merges.  Either your
> infrastructure should never attempt a "[***]" merge (described above)
> or else your infrastructure should have an exception handler to
> recover from this case.

The race condition cannot be avoided without imposing a real burden on
users. Our pqm policy was updated: "do not merge from the pqm-managed
branch until you have received the failure or success message from pqm".
That policy is annoying and slows people down. It causes frustration,
and frustrated people make the world an unpleasant place to live in.

However, we can implement a merge operator which relies on one nice
property of pqm-managed branches: they only contain pure conflictless
merges. And I will write this merge operator in the next days. Unless,
of course, someone comes up with a more general solution.

-- 
                                                            -- ddaa