[darcs-users] Fwd: Towards a conflict-free revision control system.

[Jean-Philippe Bernardy]

On Wed, Jan 7, 2009 at 2:23 PM, Eric Kow <kowey at darcs.net> wrote:

> Very interesting.  Thanks very much for sharing that!

Thanks for the feedback!

>> We do not have the intention to develop the prototype any further (for
>> the moment at least), but we thought you might be interested in at least taking
>> a look at the work and the underlying ideas. We'll be happy to answer questions
>> if you have any.
>
> First (of two) questions: what, in a nutshell, does it mean not to have any
> conflicts?  Clearly, there can be conflicting situations (i.e. two people edit
> different parts of a file).  How roughly does your idea cope with them?  As you
> can see, I haven't yet had the chance to read the paper, but was hoping for a
> little bit more of a taster (now that I've had the teaser)

Let me step back a little to give a complete answer. First of all, we
know that some
structures are inherently conflict-free. For example, take a bank
account: just can
spend money from your account while your employer pays you,
concurrently. The order
in which those operations happen does not matter (they commute), so, no problem.
But, wait a minute: what if your bank does not allow to go below zero
on your account?
Then the order matters, and we have conflicts again.

This example illustrates that by generalizing a structure, we can
remove the problem
of commutation. Some states of the generalized structure might not be
very "pleasing"
(eg. a very big negative amount on your account), but it "smoothes
out" difficulties.

The question now is: what is a good generalized structure for a
project source-tree?
In this project, we have tried one implementation. There might be
better ones, but
it is at least a first reasonable try.

In our representation of files, each line is given a unique identity.
Let's imagine for
a moment that two people replace the same part of a file with another. It means
that some portion of the file was removed twice. Therefore, there will
be a "minus one"
zone in that portion of the file that indicate the problem. (This is
very similar to two
people withdrawing the same money concurrently on the bank account.)

> Second question.  The paper says:
> | Darcs will flag this scenario as a conflict, i.e. it cannot represent such a
> | merge. The result of a merge in Darcs is dependent on the order that the
> | changes are applied, Darcs will try all possible "non conflicting" permutations
> | of the changes which will result, in the worst case, in exponential complexity.
>
> What does this mean, please?  I thought the whole point of the darcs approach
> to conflicts is that it be completely independent of order (i.e. we cancel out
> both patches).

Surely you know more about darcs than us, so we can clear it up
together. Note that
we refer to darcs 1.0. Isn't it true that the patch representation
(potentially) changes
after a reordering?

> As a more general remark, I was glad to see your reference to Lippe 2002 in the
> paper, that is, to the idea of patch commutation expressed outside of the darcs
> world (and pre-dating David's darcs work?).

I've never seen David mentioning it. I guess it was discovered independently.

> I would love to see the darcs/camp community link up a bit more with
> researchers working in this area, but (1) I don't know what "this area" is
> and (2) I don't know who the right people are.  Do you have any thoughts on
> what people we should be trying to talk to (names? sub-discliplines? research
> topics?).  If I'm not mistaken, the current (darcs) assesment on pre-existing
> work is that none of it deals with conflicts in any way, which doesn't help us
> much.

Lippe's work seems a good start; you might also want to read Tom Mens survey
of merging techniques. Andres Löh did also work on this
(http://people.cs.uu.nl/andres/VersionControl.html); he told me in private
communication that it was difficult to get principled approaches published,
because the "versioning" people have the idea that the topic is "known" and
therefore not a subject of research any longer.

> I once tried to get some connections going between darcs folks and the
> Libresource/so6 folks (notably, Pascal Molli <http://www.loria.fr/~molli>,
> but that has not taken off yet. (Pascal Molli seems to be working on
> collaborative distributed systems.  I guess an example application might be
> text editors where different people are writing at the same time?)

Collaborative edition (ie. realish time) seems a more fertile area for research
indeed. It is different though, because they don't suffer from the disconnected
concurrency problem in the same way.

Cheers,
JP.