Re: GSoC: collaborative editing

[Thomas Lord <lord@emf.net>]

On Mon, 2009-04-13 at 23:41 -0400, Brian Templeton wrote:
> Thomas Lord <lord@emf.net> writes:
> 
> > On Mon, 2009-04-13 at 18:04 -0400, Brian Templeton wrote:
> >> Thomas Lord <lord@emf.net> 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.


Oh, well.  It will eventually do both.



> 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.)

Sure.  I think OT and diff sync mostly turn out
the same except that diff sync synthesizes a 
fake edit stream from the buffer rather than
capturing the actual edit stream.

> [...]
> > 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>
> 
> 


Thanks.

-t