Re: GSoC: collaborative editing

[Brian Templeton]

Thomas Lord <address@hidden> writes:

> On Mon, 2009-04-13 at 18:04 -0400, Brian Templeton wrote:
>> Thomas Lord <address@hidden> writes:
[...]
>> > There is a second question.  What payload goes
>> > in chat messages?   How are mutually remote buffers
>> > synchronized.   In that area I suggest:
>> >
>> > 1. Carefully evaluating and considering adopting
>> >    (and helping to adapt) the "mobwrite" 
>> >    system of "diff sync" (see
>> >    http://code.google.com/p/google-mobwrite/
>> >    )
>> >
>> I am planning to use operation transformation, which is also used by
>> most existing collaborative editors (Gobby, SubEthaEdit, etc.).
>> Operation transformation is easier to implement and more elegant than
>> differential synchronization, IMO. In the context of real-time
>> collaborative editing of text documents, DS does not seem to solve any
>> actual problems that aren't already solved by OT.
>
> Does "operation transformation" mean taking a 
> log of edit commands and applying outcome-preserving
> transformations upon it to compress it to a shorter
> log of edit commands?
>
> If so, fwiw, from my background -- that *does* sound like
> a much better approach.   I could boor you for hours as to
> why but ... well, why? No need. :-)

Operation transformation does use outcome-preserving transformations,
not for compressing the log of edit commands but to reconcile the
effects of concurrently generated commands.

My implementation will only require an inclusion transformation, which
transforms an operation to "include" the effect of another operation,
which allows one to avoid divergence of document state when edits are
being applied concurrently. (For example, if Bob inserts a character at
position 12 at the same time that Alice inserts five characters at
position 0, Alice needs to shift the position of the insertion operation
she recieves from Bob forward by five characters to take into account
her own operation that Bob didn't know about.)

[...]
> It's a big topic, though, so it would help if I
> were more certain you meant by "OT" what I take
> you to mean.   Can you point to some docs I can
> read to make sure we're talking about the same thing?

You can get a decent overview from the ACE project's evaluation of
various algorithms:

  
<http://ace.svn.sourceforge.net/viewvc/ace/ace/tags/ACE_20050624/doc/pdf/algorithm.pdf>

The Jupiter algorithm is described in this paper, also linked to in my
initial post:

  <ftp://ftp.lambda.moo.mud.org/pub/MOO/papers/JupiterWin.ps>

An inclusion transformation function for operations on text documents is
defined in this paper:

  <http://www.cs.cityu.edu.hk/~jia/research/reduce98.pdf>