On Wed, Jan 7, 2009 at 2:23 PM, Eric Kow <[email protected]> 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. _______________________________________________ darcs-users mailing list [email protected] http://lists.osuosl.org/mailman/listinfo/darcs-users
