[darcs-users] Darcs and Operational Transformations (Team ECOO)

Tue Sep 15 07:18:15 UTC 2009

Hello,

Thank you Eric for the references you sent us. And thanks again for the 
presentation about Darcs and for your effort to ‘merge’ the Darcs 
community with the OT community. We will have a look in more detail 
about the work you do on the theory of patches in Darcs and Camp and the 
work in FoCAL project. It would be great to have some meetings in the 
future.

To answer to some of William questions, both So6 and GoogleWave 
architecture are based on a central server which simplifies the OT 
algorithms.

So6 is based on the SOCT4 algorithm whose description you can find here

Nicolas Vidot, Michelle Cart, Jean Ferrié and Maher Suleiman, Copies 
convergence in a distributed real-time collaborative environment, 
Proceedings of CSCW 2000

http://portal.acm.org/citation.cfm?doid=358916.358988

In SOCT4 the operations are ordered globally using a timestamp given by 
a sequencer. An operation generated at a site is executed immediately at 
that site but it is not broadcast to the other sites until it is 
assigned a timestamp and all the operations which precede it according 
to the timestamp order have been received and executed at that site. Due 
to the global order of integration, the TP2 condition is not necessary.

GoogleWave uses the Jupiter algorithm based on operational transformation

David A. Nichols, Pavel Curtis, Michael Dixon and John Lamping, 
High-latency, low-bandwidth windowing in the Jupiter collaboration system,
Proceedings of UIST 1995

http://portal.acm.org/citation.cfm?doid=215585.215706

Jupiter algorithm does not need TP2 condition.

The tree structure that you mentioned comes from the fact that 
GoogleWave deals with XML documents.

If you need an OT algorithm for a tree structured document you can maybe 
have a look at this one

Claudia-Lavinia Ignat and Moira C. Norrie, Multi-level editing of 
hierarchical documents. Journal of Computer Supported Cooperative Work, 
17(5-6):423-468, December 2008.

http://www.springerlink.com/content/472w061011830726/

Regards,
Claudia

PS. As ECOO team is divided into two main axes, there are only some 
people from the group interested in collaborative editing, I listed them 
as recipients of this email. So, in order not to spam some of our 
colleagues, I think it would be better to continue the discussion only 
with the listed ECOO members instead of ecoo at loria.fr

William Uther wrote:
> Hi,
>   Sounds very interesting.  If you let me know when the next meeting is, 
> if there is one, I might see if I can make it.  I went as far as 
> starting to develop my own VCS, but time constraints overtook me (this 
> is a side-interest of mine).  I have a few things to note:
> 
>   - Google Wave also appears to use OT (and was developed by some guys I 
> know at Google Sydney I believe).
>   - My understanding is that instead of enforcing TP2, both SO6 and 
> Google Wave enforce tree-structured patch sharing.  Is that still true 
> for SO6?
>   - Thanks for the links to FoCAL.  Looks interesting.
> 
>   My thoughts on making an OT based VCS went in a different direction 
> from 'conflict free', but rather moving to a representation where the 
> conflicts were an integral part of the representation.  This means 
> moving away from linear strings.  The OT internals all worked with that 
> more expressive representation, but it would be linearised and conflict 
> markers introduced when you built a working copy.  The patch creation 
> code would handle mapping back from the linearised workspace to the more 
> expressive representation.
> 
>   The best analogy I can think of is wanting to introduce square root in 
> a number system.  The reals are great, but sometimes the square root 
> operation takes you outside the reals, e.g. sqrt(-1).  So you expand 
> your representation space to the complex numbers.  In that space you can 
> take square roots freely and everything works.  I guess you could say 
> that in this expanded space my system is conflict free, or you could 
> look at is as the 'conflicts' corresponding to the 'imaginary' part of 
> the representation.
> When you need to feed a complex number into a system that cannot handle 
> them, you need to force things back to plain reals - in the VCS case 
> this consists of building a conflict marked version in a plain text format.
> 
> Be well,
> 
> Will      :-}
> 
> On 15/09/2009, at 1:47 AM, Eric Kow wrote:
> 
>> Dear Darcs-Users, Team ECOO and William Uther,
>>
>> Last week I had the great opportunity to meet and talk about Darcs with
>> members of Team ECOO in Nancy.
>>
>> Team ECOO are an INRIA research group that working on lots of different
>> topics related to computer-mediated cooperation <http://ecoo.loria.fr/>.
>> They have a special interest in (distributed) revision control systems,
>> wikis and other such software.  The team has a lot of experience working
>> in distributed revision control; in fact they have even put together a
>> patch-based system known as 'so6' ("saucisse") with some intriguing
>> similarities to Darcs.
>>
>> Overall, the purpose of this meeting was for Darcs to start cultivating
>> a long-term relationship with the research world.  There is a lot of
>> work out there on advanced revision control.  If we could only make sure
>> that we're all talking to each other on a regular basis, perhaps we
>> could pool our efforts somehow.  Maybe one day, we can put revision
>> control back on the map as a serious research topic.  Maybe one day, we
>> can give these Gits a run for their money.
>>
>> The meeting was long and interesting.  I presented Darcs a little bit;
>> we talked about the formal properties that Darcs tries to ensure and
>> also about the potential relationship between Darcs and Operational
>> Transformations.  I hope to put together a more detailed write-up about
>> the things we talked about.  Here I just want to give a very quick
>> overview.
>>
>> 1. I talked about some key Darcs features: dependency inference
>>   and pervasive cherry-picking (even in our undo operations).
>>
>> 2. Pascal Molli brought up a standard test from the
>>   Operational Transformations literature (TP2;
>>   http://bugs.darcs.net/issue1609)
>>
>> 3. I discussed how Darcs patch theory can be seen as a sort of
>>   multi-layer onion:
>>
>>     a. properties of the commutation/inverse operations
>>     b. conflicts (eg darcs-1 vs darcs-2)
>>     c. definition of primitive patches and commutation
>>     d. conflict marking
>>
>>  Here I was trying to convey the idea that while the bug above was on
>>  the level of (c-d), what the Darcs community is most pre-occupied with
>>  at the moment are (a-b), which we think we may be able solve
>>  independently of each other.
>>
>> 4. We talked about the relationship between Darcs and Operational
>>   Transformations.  If I can give a caricature of the state of
>>   affairs:
>>
>>    * OT has definitions and proofs of formal properties
>>
>>    * Darcs has a story for conflicts (ie. parts a-b above).
>>      Our story may not be perfect (exponential merges, open questions),
>>      but it's out there in the wild and mostly works in practice.
>>
>> 5. We suggested some interesting steps forward such as
>>
>>   * Within the Darcs community? Attempt to formulate Darcs (3a) in
>>     terms of Operational Transformations
>>
>>   * Within the ECOO team?  Study the Darcs (3b) story for conflicts
>>     and compare with previous work on OT 'conflict objects'.  I
>>     still think that the Darcs idea that 'conflicting patches cancel
>>     each other out' is potentially new and interesting for ECOO
>>     reseachers.
>>
>>   * Within the Darcs community? Read up on OT literature (in
>>     separate mail) on formal properities and proofs thereof
>>     (Could be very interesting for Ian and all his Coq-writing
>>     work)
>>
>>   * Darcs and ECOO: Bring a Patch Theory Expert (ahem Ian?) to Nancy so
>>     they cane talk to Team ECOO!
>>
>> 6. Team ECOO talked a bit about some new directions they are
>>   exploring in conflict-free revision control.  It sounds rather
>>   familiar to Jean-Phillipe Benardy's work on Focal.
>>
>> Apologies if I've glossed over or misunderstood anything important!
>> I hope to follow up one this with a few more concrete details.
>>
>> Many thanks to Claudia Ignat, Gerald Oster and the rest of team ECOO for
>> this opportunity.  I hope we can continue this discussion and keep on
>> exchanging ideas :-)
>>
>> -- 
>> Eric Kow <http://www.nltg.brighton.ac.uk/home/Eric.Kow>
>> PGP Key ID: 08AC04F9
> 