GSoC: collaborative editing

GSoC: collaborative editing

[Brian Templeton]

Would anyone be willing to mentor me for this project, if my application
is accepted?

Package name and title of the project (e.g.: emacs - better foo bar):

Emacs - collaborative editing system

Summary:

A real-time collaborative editing system for GNU Emacs.

Benefits:

This project will provide a free alternative to existing proprietary
collaborative editors such as SubEthaEdit and MoonEdit, and it will be
more extensible and will have more powerful editing features than
existing free collaborative editors like Gobby.

As an ancillary benefit, a precise change tracking mechanism will be
useful to other Emacs projects, particularly projects involving
hypertext and version control. For example, Planner could transclude
task list entries instead of keeping multiple copies of the same data in
different files, ensuring the consistency of the task database as well
as providing a more intuitive user interface.

Deliverables:

1. A precise change reporting mechanism, replacing
   {before,after}-change-functions. This will require cooperation with
   other Emacs developers and must not reduce performance for
   applications not requiring precise change reporting.

2. A transclusion system, which will be used as a test of the new change
  reporting mechanism.

3. A collaborative editing system using a modified version of the
   Jupiter algorithm
   (<ftp://ftp.lambda.moo.mud.org/pub/MOO/papers/JupiterWin.ps>),
   comprising:

   - A client written in Emacs Lisp.
   - A modified version of an existing server written in Erlang. (I
     wrote the server in 2007 for a commercial project; it has not yet
     been released to the general public.)

4. End-user documentation, including a user guide published either as
   Texinfo or on the EmacsWiki.

5. An updated version of the Emacs Lisp manual describing the new change
   reporting mechanism.

Plan:

In the time before May 23, I'll familiarize myself with the relevant
parts of Emacs's C code and discuss possible designs for an improved
change-tracking system with other Emacs developers -- on emacs-devel,
etc.

In the six weeks before mid-term evaluations, I'll implement the new
change-tracking system, write the transclusion library, and improve the
GOTO inclusion transformation function to avoid inefficient corner
cases. I'll also debitrot the Erlang server and add support for a simple
binary protocol in addition to the HTTP interface used by the old JS and
Flash clients.

During the last half of the program I will work on the client itself --
implementing the revised Jupiter algorithm, support for the binary
protocol, a simple interactive client, lists of remote users,
visualization of the activity of other users (e.g. coloring spans of
text according to who last edited it, indicating others' point
positions, etc.), and so on. If time permits, I hope to include some
sort of history-browsing feature and a useful undo command. I will also
write the user documentation during this time period.

I will be able to work on this full-time.

Communication:

I am willing to use whatever communications media my mentor finds
convenient: email, IM, telephone or voice-chat, etc.

I will publish my code in darcs repositories available via HTTP and in
AFS space.

Qualification:

I have been using Emacs and writing in Emacs Lisp since 2001 or so. I
have contributed small amounts of code to GNU Emacs and am the original
author of a few publicly released Emacs packages, including HCoop's
domtool-mode. I also have previous experience with real-time
collaborative editing systems; in 2007 I wrote a collaborative editing
system with an Erlang server and Javascript and Flash clients, and began
work on an Emacs client but found that it was not possible to write a
reliable client without hacking on Emacs internals.

Re: GSoC: collaborative editing

[Michael Albinus]

Brian Templeton <bpt@tunes.org> writes:

> Would anyone be willing to mentor me for this project, if my application
> is accepted?
>
> Package name and title of the project (e.g.: emacs - better foo bar):
>
> Emacs - collaborative editing system
>
> Summary:
>
> A real-time collaborative editing system for GNU Emacs.
>
> Benefits:
>
> This project will provide a free alternative to existing proprietary
> collaborative editors such as SubEthaEdit and MoonEdit, and it will be
> more extensible and will have more powerful editing features than
> existing free collaborative editors like Gobby.
>
> As an ancillary benefit, a precise change tracking mechanism will be
> useful to other Emacs projects, particularly projects involving
> hypertext and version control. For example, Planner could transclude
> task list entries instead of keeping multiple copies of the same data in
> different files, ensuring the consistency of the task database as well
> as providing a more intuitive user interface.
>
> Deliverables:
>
> 1. A precise change reporting mechanism, replacing
>    {before,after}-change-functions. This will require cooperation with
>    other Emacs developers and must not reduce performance for
>    applications not requiring precise change reporting.
>
> 2. A transclusion system, which will be used as a test of the new change
>   reporting mechanism.
>
> 3. A collaborative editing system using a modified version of the
>    Jupiter algorithm
>    (<ftp://ftp.lambda.moo.mud.org/pub/MOO/papers/JupiterWin.ps>),
>    comprising:
>
>    - A client written in Emacs Lisp.
>    - A modified version of an existing server written in Erlang. (I
>      wrote the server in 2007 for a commercial project; it has not yet
>      been released to the general public.)
>
> 4. End-user documentation, including a user guide published either as
>    Texinfo or on the EmacsWiki.
>
> 5. An updated version of the Emacs Lisp manual describing the new change
>    reporting mechanism.
>
> Plan:
>
> In the time before May 23, I'll familiarize myself with the relevant
> parts of Emacs's C code and discuss possible designs for an improved
> change-tracking system with other Emacs developers -- on emacs-devel,
> etc.
>
> In the six weeks before mid-term evaluations, I'll implement the new
> change-tracking system, write the transclusion library, and improve the
> GOTO inclusion transformation function to avoid inefficient corner
> cases. I'll also debitrot the Erlang server and add support for a simple
> binary protocol in addition to the HTTP interface used by the old JS and
> Flash clients.
>
> During the last half of the program I will work on the client itself --
> implementing the revised Jupiter algorithm, support for the binary
> protocol, a simple interactive client, lists of remote users,
> visualization of the activity of other users (e.g. coloring spans of
> text according to who last edited it, indicating others' point
> positions, etc.), and so on. If time permits, I hope to include some
> sort of history-browsing feature and a useful undo command. I will also
> write the user documentation during this time period.
>
> I will be able to work on this full-time.
>
> Communication:
>
> I am willing to use whatever communications media my mentor finds
> convenient: email, IM, telephone or voice-chat, etc.
>
> I will publish my code in darcs repositories available via HTTP and in
> AFS space.
>
> Qualification:
>
> I have been using Emacs and writing in Emacs Lisp since 2001 or so. I
> have contributed small amounts of code to GNU Emacs and am the original
> author of a few publicly released Emacs packages, including HCoop's
> domtool-mode. I also have previous experience with real-time
> collaborative editing systems; in 2007 I wrote a collaborative editing
> system with an Erlang server and Javascript and Flash clients, and began
> work on an Emacs client but found that it was not possible to write a
> reliable client without hacking on Emacs internals.

[Fullquote for the benefit of Alban, who doesn't follow emacs-devel]

Hi Brian,

half a year ago, I wrote a small collaborative editing package for
Emacs, using Alban Crequy's approach described at
<http://alban.apinc.org/blog/collaborative-editing/>. He wrote plug-ins
for gvim and gedit. All these editors were able to communicate with each
other (with some deficiencies, but it was just a proof of concept).

The major advantage was usage of D-Bus for communication. This means,
that no addition to the core of those editors are necessary. The obvious
disadavantage is, that it doesn't run on systems which do not speak
D-Bus.

Maybe you can have a look on this. Since then, the project is stalled,
unfortunately (in my case: lack of time). But I believe, there are good
reasons to add collaborative editing features to Emacs, so I am willing
to discuss your plans with you in detail.

Best regards, Michael.

Re: GSoC: collaborative editing

[Miles Bader]

Michael Albinus <michael.albinus@gmx.de> writes:
> The major advantage was usage of D-Bus for communication. This means,
> that no addition to the core of those editors are necessary. The obvious
> disadavantage is, that it doesn't run on systems which do not speak
> D-Bus.

Is there something unique about dbus that made it a hard dependency?
(instead of using dbus for one implementation of a more abstract
transport/rendezvous interface of some sort)

-Miles

-- 
Accordion, n. An instrument in harmony with the sentiments of an assassin.

Re: GSoC: collaborative editing

[Michael Albinus]

Miles Bader <miles@gnu.org> writes:

> Michael Albinus <michael.albinus@gmx.de> writes:
>> The major advantage was usage of D-Bus for communication. This means,
>> that no addition to the core of those editors are necessary. The obvious
>> disadavantage is, that it doesn't run on systems which do not speak
>> D-Bus.
>
> Is there something unique about dbus that made it a hard dependency?
> (instead of using dbus for one implementation of a more abstract
> transport/rendezvous interface of some sort)

Alban's protocol is based on D-Bus messages. That's why I've used it.

D-Bus has the advantage, that many applications under GNU/Linux (and
also BSD, and also OS X) are prepared for this meanwhile. The plugins
for gedit and gvim, written by Alban, are very straightforward.

If there would be a more general interface for collaborative editing,
one could apply D-Bus messages as one implementation of such an interface.

> -Miles

Best regards, Michael.

Re: GSoC: collaborative editing

[Thien-Thi Nguyen]

() Brian Templeton <bpt@tunes.org>
() Sat, 11 Apr 2009 16:07:20 -0400

   [introduction]

Sounds interesting.  Have you thought about a peer-to-peer architecture?
I don't know if i'm qualified to be a sponsor, but i wouldn't mind
helping, w/ the caveat that the design move away from requiring a
separate server and towards peer-to-peer.

   1. A precise change reporting mechanism, replacing
      {before,after}-change-functions.  This will require cooperation
      with other Emacs developers and must not reduce performance for
      applications not requiring precise change reporting.

Why must these be replaced?

   2. A transclusion system, which will be used as a test of the new change
      reporting mechanism.

   3. A collaborative editing system using a modified version of the
      Jupiter algorithm, comprising:

      - A client written in Emacs Lisp.
      - A modified version of an existing server written in Erlang.

I think a server written in Emacs Lisp would gain more traction.

   4. End-user documentation, including a user guide published either as
      Texinfo or on the EmacsWiki.

   5. An updated version of the Emacs Lisp manual describing the new change
      reporting mechanism.

   [Plan: discuss change functions and then] debitrot the Erlang server
   and add support for a simple binary protocol in addition to the HTTP
   interface used by the old JS and Flash clients.

Probably you want to avoid binary protocol unless absolutely necessary.
Why not translate the existing protocol to use Emacs-`read'able sexps?

   During the last half of the program I will work on the client itself
   -- implementing the revised Jupiter algorithm, support for the binary
   protocol, a simple interactive client, lists of remote users,
   visualization of the activity of other users (e.g. coloring spans of
   text according to who last edited it, indicating others' point
   positions, etc.), and so on.

Many of these features are supplied by Emacs itself.  Indeed, Emacs is
already a "simple interactive client" of its change-recording internals.

thi

Re: GSoC: collaborative editing

[Thomas Lord]

I have been organizing some materials about
a "Collaboration WebOS" project: a project to
help many free software projects - like Emacs - 
build in collaboration features in coordinated
ways.   See http://basiscraft.com


On Mon, 2009-04-13 at 16:43 +0200, Thien-Thi Nguyen wrote:
> () Brian Templeton <bpt@tunes.org>
> () Sat, 11 Apr 2009 16:07:20 -0400
> 
>    [introduction]
> 
> Sounds interesting. 
[...]
>    3. A collaborative editing system using a modified version of the
>       Jupiter algorithm, comprising:
> 
>       - A client written in Emacs Lisp.
>       - A modified version of an existing server written in Erlang.
> 
> I think a server written in Emacs Lisp would gain more traction.


Please consider this third alternative which I 
think has advantages to both:

1. Do not write a custom server.
2. Use a chat server (such as a Jabber implementation).
3. If some server-side computation is needed other
   than just forwarding messages in the manner of a chat
   session, write that new server-side code as a 
   chat client.

Reasons:

a. "no new server" means less work
b. "no new server" means less work for server
   administrators if they are already running
   a chat server
c. "use Jabber (XMPP)" means that the same
   message bus can be shared with other programs
   such as the "collaborative whiteboard" feature
   of Inkscape
d. XMPP implementations are actively maintained
   and aggressively improved.  It is hard to image
   a new, less general-purpose server "catching up"
   and to catch up suggests doing a lot of redundent
   work

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

Reasons and Cautions:

a. Caution: "mobwrite" currently makes the same 
   mistake of using a custom server.  To make
   it acceptable for this project, ideally
   it would be modified to use XMPP.

b. Caution: "mobwrite" is new and experimental.
   The design needs to be scrutinized with care.

c. Caution: "mobwrite" is a project of Google
   Inc.   Past experience with free software 
   development projects that become intertwined
   with development corporations of for-profit 
   firms is that the for-profit firm's motives
   to cooperate may prove fickle.   It is easy 
   to wind up with a situation where the for-profit
   firm benefits for its own purposes, but the
   cause of software freedom gains little or even
   loses ground.

d. Reason: Perhaps using "mobwrite" can save work.

e. Reason: Since other editors are considering 
   or being modified to use "mobwrite", perhaps this
   approach can ultimately allow collaborative sessions
   in which some users are using "emacs" while others
   use "bespin" or "vim" or what have you.




-t

Re: GSoC: collaborative editing

[Stefan Monnier]

> Sounds interesting.  Have you thought about a peer-to-peer architecture?

A peer-to-peer approach has advantages, of course, but it also makes it
very difficult to recover a total ordering and hence guarantee that
every client sees the same content.


        Stefan

Re: GSoC: collaborative editing

[Brian Templeton]

Thomas Lord <lord@emf.net> writes:

> On Mon, 2009-04-13 at 16:43 +0200, Thien-Thi Nguyen wrote:
>> () Brian Templeton <bpt@tunes.org>
>>    3. A collaborative editing system using a modified version of the
>>       Jupiter algorithm, comprising:
>> 
>>       - A client written in Emacs Lisp.
>>       - A modified version of an existing server written in Erlang.
>> 
>> I think a server written in Emacs Lisp would gain more traction.
>
> Please consider this third alternative which I 
> think has advantages to both:
>
> 1. Do not write a custom server.
> 2. Use a chat server (such as a Jabber implementation).
> 3. If some server-side computation is needed other
>    than just forwarding messages in the manner of a chat
>    session, write that new server-side code as a 
>    chat client.
>
> Reasons:
>
> a. "no new server" means less work
> b. "no new server" means less work for server
>    administrators if they are already running
>    a chat server
> c. "use Jabber (XMPP)" means that the same
>    message bus can be shared with other programs
>    such as the "collaborative whiteboard" feature
>    of Inkscape
> d. XMPP implementations are actively maintained
>    and aggressively improved.  It is hard to image
>    a new, less general-purpose server "catching up"
>    and to catch up suggests doing a lot of redundent
>    work

I have already written a server, so using XMPP wouldn't save any work in
the short run. I evaluated XMPP when I wrote the server and wasn't able
to determine whether using Jabber as a message bus for a Jupiter-based
protocol would require misusing XMPP, since some server-side computation
and modification of client messages is required. But I'm not averse to
using Jabber as a message bus if it wouldn't be considered a misuse of
the protocol, and it would certainly be a good fit if I implemented an
algorithm for P2P editing, which wouldn't require server-side
computation/message modification at all.

The current server is written in Erlang; it would be only moderately
difficult to adapt it to work with ejabberd's mod_muc.

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

> b. Caution: "mobwrite" is new and experimental.
>    The design needs to be scrutinized with care.
>
Yes, and I don't want to have to be the one to scrutinize it. There is a
great deal of theoretical work available on OT approaches, and several
algorithms have been proven correct; I'd rather rely on a functioning
network (i.e., one that doesn't drop messages constantly) than attempt
to prove the correctness of 'fuzzy' matching algorithms and
'best-effort' patching algorithms.

> e. Reason: Since other editors are considering 
>    or being modified to use "mobwrite", perhaps this
>    approach can ultimately allow collaborative sessions
>    in which some users are using "emacs" while others
>    use "bespin" or "vim" or what have you.
>
Which editors? Are any editors currently using mobwrite, besides editors
specifically written to use mobwrite?

Re: GSoC: collaborative editing

[Thomas Lord]

You seem to not mind "full quoting with sparse
comments" --- I actually like that too, some don't.
In any event I'll use that style to so, scroll 
way down to find my comments :-)




On Mon, 2009-04-13 at 18:04 -0400, Brian Templeton wrote:
> Thomas Lord <lord@emf.net> writes:
> 
> > On Mon, 2009-04-13 at 16:43 +0200, Thien-Thi Nguyen wrote:
> >> () Brian Templeton <bpt@tunes.org>
> >>    3. A collaborative editing system using a modified version of the
> >>       Jupiter algorithm, comprising:
> >> 
> >>       - A client written in Emacs Lisp.
> >>       - A modified version of an existing server written in Erlang.
> >> 
> >> I think a server written in Emacs Lisp would gain more traction.
> >
> > Please consider this third alternative which I 
> > think has advantages to both:
> >
> > 1. Do not write a custom server.
> > 2. Use a chat server (such as a Jabber implementation).
> > 3. If some server-side computation is needed other
> >    than just forwarding messages in the manner of a chat
> >    session, write that new server-side code as a 
> >    chat client.
> >
> > Reasons:
> >
> > a. "no new server" means less work
> > b. "no new server" means less work for server
> >    administrators if they are already running
> >    a chat server
> > c. "use Jabber (XMPP)" means that the same
> >    message bus can be shared with other programs
> >    such as the "collaborative whiteboard" feature
> >    of Inkscape
> > d. XMPP implementations are actively maintained
> >    and aggressively improved.  It is hard to image
> >    a new, less general-purpose server "catching up"
> >    and to catch up suggests doing a lot of redundent
> >    work
> 
> I have already written a server, so using XMPP wouldn't save any work in
> the short run.


Sure.  It would even mean a little work to switch
over.   On the scale of the whole Emacs project, 
I think that tiny blip of extra work is small
compared to what the project is set up for in the
long run if a custom server is used.


>  I evaluated XMPP when I wrote the server and wasn't able
> to determine whether using Jabber as a message bus for a Jupiter-based
> protocol would require misusing XMPP, since some server-side computation
> and modification of client messages is required.


You can do your server-side stuff either as
an XMPP extension or as a server-side client
of the XMPP session.

One suggestion I would have (just my biases) is
to not worry about performance too much up front
if you are confident it can be improved later -- 
so I would try doing any extra server side 
computation in a server-side client of vanilla 
or Jabber-ish XMPP.   If "barely usable - but usable"
can be achieved that way AND if "looks easy to 
fix the performance problems" is the outcome: that's
gold (imo).



>  But I'm not averse to
> using Jabber as a message bus if it wouldn't be considered a misuse of
> the protocol,

It's definitely not.   

Very briefly, you can make a taxonomy of 
communications busses.  There's "persistent", 
there's "store / forward", there's "lossy routing"
and there are orthogonal aspects to -- but not 
very many.

If you can reduce something to "lossy routing
network" - that suggests finding one way or another
to build on chat and if building on chat, XMPP seems
to me a good choice.

Ultimately, all those different kinds of messaging
get integrated a bit - e.g., the "store and forward"
service (such as for mail and lists) and "lossy routing"
(such as for chat) can share user identities, authentication,
and so on.  That way, we keep servers simple - they just 
(mostly) run a few very basic services, nicely integrated.



>  and it would certainly be a good fit if I implemented an
> algorithm for P2P editing, which wouldn't require server-side
> computation/message modification at all.


Don't over-reach for a summer project.  Do whichever
is easier to get working!

Even if you use XMPP but don't right away do P2P edits?
You'll still have made plausible progress on P2P edits
because the server side will already be done in the 
form of chat rooms and chat server peering - leaving you
to think about the hard problems on the client side.

(Again: don't spontaneously take on mathematically
hard problems at the last minute for a summer project.
Don't misunderstand me to suggest you should go for P2P 
edits!)



> 
> The current server is written in Erlang; it would be only moderately
> difficult to adapt it to work with ejabberd's mod_muc.

There ya go.  So, let's see what the Emacs
maintainers think, if they care to comment.


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



> 
> > b. Caution: "mobwrite" is new and experimental.
> >    The design needs to be scrutinized with care.
> >
> Yes, and I don't want to have to be the one to scrutinize it. 

If I understand your point about "OT vs diff-sync" above,
you get mobwrite just fine, imo.   That's care.



> There is a
> great deal of theoretical work available on OT approaches, and several
> algorithms have been proven correct; I'd rather rely on a functioning
> network (i.e., one that doesn't drop messages constantly) than attempt
> to prove the correctness of 'fuzzy' matching algorithms and
> 'best-effort' patching algorithms.


That's a confusion on your part, I think.

The network unreliability is real and unavoidable. 
You can't wish it away by insisting on a design
that assumes a loss-less network.  That doesn't
preclude OT, I think.

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?




> 
> > e. Reason: Since other editors are considering 
> >    or being modified to use "mobwrite", perhaps this
> >    approach can ultimately allow collaborative sessions
> >    in which some users are using "emacs" while others
> >    use "bespin" or "vim" or what have you.
> >
> Which editors? Are any editors currently using mobwrite, besides editors
> specifically written to use mobwrite?
> 


The (verbally spread) news at a recent conference
was that someone with the mobwrite project was working
on extending several editors, including Emacs, with
mobwrite support.

Both Google and the Mozilla Foundation are investing
in collaborative editing technology.

-t

Re: GSoC: collaborative editing

[Thomas Lord]

I should add that a previous GSoC
project added a collaborative edit session
feature to the Inkscape SVG editor: a 
"shared whiteboard" mode.

I have not extensively tested it and I understand
that the feature has some problems and was not realized
as fully as the student aimed for at the start of
the summer - but it is there, and at least somewhat
works, and ... uses XMPP :-)

-t



On Mon, 2009-04-13 at 18:04 -0400, Brian Templeton wrote:
> Thomas Lord <lord@emf.net> writes:
> 
> > On Mon, 2009-04-13 at 16:43 +0200, Thien-Thi Nguyen wrote:
> >> () Brian Templeton <bpt@tunes.org>
> >>    3. A collaborative editing system using a modified version of the
> >>       Jupiter algorithm, comprising:
> >> 
> >>       - A client written in Emacs Lisp.
> >>       - A modified version of an existing server written in Erlang.
> >> 
> >> I think a server written in Emacs Lisp would gain more traction.
> >
> > Please consider this third alternative which I 
> > think has advantages to both:
> >
> > 1. Do not write a custom server.
> > 2. Use a chat server (such as a Jabber implementation).
> > 3. If some server-side computation is needed other
> >    than just forwarding messages in the manner of a chat
> >    session, write that new server-side code as a 
> >    chat client.
> >
> > Reasons:
> >
> > a. "no new server" means less work
> > b. "no new server" means less work for server
> >    administrators if they are already running
> >    a chat server
> > c. "use Jabber (XMPP)" means that the same
> >    message bus can be shared with other programs
> >    such as the "collaborative whiteboard" feature
> >    of Inkscape
> > d. XMPP implementations are actively maintained
> >    and aggressively improved.  It is hard to image
> >    a new, less general-purpose server "catching up"
> >    and to catch up suggests doing a lot of redundent
> >    work
> 
> I have already written a server, so using XMPP wouldn't save any work in
> the short run. I evaluated XMPP when I wrote the server and wasn't able
> to determine whether using Jabber as a message bus for a Jupiter-based
> protocol would require misusing XMPP, since some server-side computation
> and modification of client messages is required. But I'm not averse to
> using Jabber as a message bus if it wouldn't be considered a misuse of
> the protocol, and it would certainly be a good fit if I implemented an
> algorithm for P2P editing, which wouldn't require server-side
> computation/message modification at all.
> 
> The current server is written in Erlang; it would be only moderately
> difficult to adapt it to work with ejabberd's mod_muc.
> 
> > 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.
> 
> > b. Caution: "mobwrite" is new and experimental.
> >    The design needs to be scrutinized with care.
> >
> Yes, and I don't want to have to be the one to scrutinize it. There is a
> great deal of theoretical work available on OT approaches, and several
> algorithms have been proven correct; I'd rather rely on a functioning
> network (i.e., one that doesn't drop messages constantly) than attempt
> to prove the correctness of 'fuzzy' matching algorithms and
> 'best-effort' patching algorithms.
> 
> > e. Reason: Since other editors are considering 
> >    or being modified to use "mobwrite", perhaps this
> >    approach can ultimately allow collaborative sessions
> >    in which some users are using "emacs" while others
> >    use "bespin" or "vim" or what have you.
> >
> Which editors? Are any editors currently using mobwrite, besides editors
> specifically written to use mobwrite?
> 
> 
> 

Re: GSoC: collaborative editing

[Richard M Stallman]

    A peer-to-peer approach has advantages, of course, but it also makes it
    very difficult to recover a total ordering and hence guarantee that
    every client sees the same content.

Yes, but it should be possible to set it up so that conflicts are
reported.  They will only happen when two people edit the same area
in a short period, and that is asking for trouble anyway.

It is very important to promote peer-to-peer methods of doing various
collaborative tasks, because servers cause issues of control vs
freedom, and peer-to-peer is the only way to avoid them.

Re: GSoC: collaborative editing

[Brian Templeton]

Thien-Thi Nguyen <ttn@gnuvola.org> writes:

> () Brian Templeton <bpt@tunes.org>
> () Sat, 11 Apr 2009 16:07:20 -0400
>
>    [introduction]
>
> Sounds interesting.  Have you thought about a peer-to-peer architecture?
> I don't know if i'm qualified to be a sponsor, but i wouldn't mind
> helping, w/ the caveat that the design move away from requiring a
> separate server and towards peer-to-peer.

I have considered a P2P architecture, but as Stefan mentions, that makes
it much harder to ensure consistency, and P2P algorithms are
considerably more complicated than algorithms that rely on a central
server.

>    1. A precise change reporting mechanism, replacing
>       {before,after}-change-functions.  This will require cooperation
>       with other Emacs developers and must not reduce performance for
>       applications not requiring precise change reporting.
>
> Why must these be replaced?

Emacs does not report changes precisely enough to allow one to infer the
sequence of basic editing operations performed from a sequence of calls
to a *-change-functions hook. For example, substituting a character in a
region results in a single large change being reported. Currently it's
possible to write a client that would work correctly as long as the user
limits themselves to simple editing operations, but naïve change hook
functions will detect operations incorrectly in many situations (e.g.,
when filling paragraphs).

>    2. A transclusion system, which will be used as a test of the new change
>       reporting mechanism.
>
>    3. A collaborative editing system using a modified version of the
>       Jupiter algorithm, comprising:
>
>       - A client written in Emacs Lisp.
>       - A modified version of an existing server written in Erlang.
>
> I think a server written in Emacs Lisp would gain more traction.
>
>    4. End-user documentation, including a user guide published either as
>       Texinfo or on the EmacsWiki.
>
>    5. An updated version of the Emacs Lisp manual describing the new change
>       reporting mechanism.
>
>    [Plan: discuss change functions and then] debitrot the Erlang server
>    and add support for a simple binary protocol in addition to the HTTP
>    interface used by the old JS and Flash clients.
>
> Probably you want to avoid binary protocol unless absolutely necessary.
> Why not translate the existing protocol to use Emacs-`read'able sexps?

My wording was misleading; I only meant a protocol more compact than
HTTP, which is very verbose for applications like this.

>    During the last half of the program I will work on the client itself
>    -- implementing the revised Jupiter algorithm, support for the binary
>    protocol, a simple interactive client, lists of remote users,
>    visualization of the activity of other users (e.g. coloring spans of
>    text according to who last edited it, indicating others' point
>    positions, etc.), and so on.
>
> Many of these features are supplied by Emacs itself.  Indeed, Emacs is
> already a "simple interactive client" of its change-recording internals.

But not a simple interactive client for displaying changes made in
_other_ editors. Some of them are easy to implement, but none of these
features are supplied by Emacs itself.

Re: GSoC: collaborative editing

[Stephen J. Turnbull]

Brian Templeton writes:

 > I have considered a P2P architecture, but as Stefan mentions, that makes
 > it much harder to ensure consistency, and P2P algorithms are
 > considerably more complicated than algorithms that rely on a central
 > server.

Basically what you're saying is "OK, let's impose an arbitrary total
ordering on the changes."  Indeed that makes writing the collaborative
tool easier, but it also undermines collaboration by giving priority
to getting there *first* rather than doing it *better*.

Richard already said basically the same thing in a different way, of
course.

Re: GSoC: collaborative editing

[Brian Templeton]

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.

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>

Re: GSoC: collaborative editing

[Brian Templeton]

"Stephen J. Turnbull" <stephen@xemacs.org> writes:

> Brian Templeton writes:
>
>  > I have considered a P2P architecture, but as Stefan mentions, that makes
>  > it much harder to ensure consistency, and P2P algorithms are
>  > considerably more complicated than algorithms that rely on a central
>  > server.
>
> Basically what you're saying is "OK, let's impose an arbitrary total
> ordering on the changes."  Indeed that makes writing the collaborative
> tool easier, but it also undermines collaboration by giving priority
> to getting there *first* rather than doing it *better*.
>
Most P2P algorithms *do* impose a total order on operations; it's just
more difficult to maintain that order.

Re: GSoC: collaborative editing

[Thomas Lord]

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

Re: GSoC: collaborative editing

[Stephen J. Turnbull]

Brian Templeton writes:

 > Most P2P algorithms *do* impose a total order on operations; it's just
 > more difficult to maintain that order.

Excuse me?  How do you do that when you may not currently be in
contact with all the peers who are operating on the text?

Re: GSoC: collaborative editing

[Brian Templeton]

"Stephen J. Turnbull" <stephen@xemacs.org> writes:

> Brian Templeton writes:
>
>  > Most P2P algorithms *do* impose a total order on operations; it's just
>  > more difficult to maintain that order.
>
> Excuse me?  How do you do that when you may not currently be in
> contact with all the peers who are operating on the text?

Most published algorithms on P2P collaborative editing implicitly or
explicitly assume the availability of a fairly reliable network, and
assume that peers can stay in almost constant contact with each other.
Many algorithms would technically "work" with an unreliable network, but
the implementations would not be very usable.

Re: GSoC: collaborative editing

[Thien-Thi Nguyen]

() Thomas Lord <lord@emf.net>
() Mon, 13 Apr 2009 09:11:12 -0700

   I have been organizing some materials about
   a "Collaboration WebOS" project: a project to
   help many free software projects - like Emacs -
   build in collaboration features in coordinated
   ways.   See http://basiscraft.com

Thanks for the pointer.

   1. Do not write a custom server.
   2. Use a chat server (such as a Jabber implementation).
   3. If some server-side computation is needed other
      than just forwarding messages in the manner of a chat
      session, write that new server-side code as a
      chat client.

I would agree if given s/server/protocol/g.  A p2p-oriented
XMPP-speaking Emacs-Lisp-implemented server would be a fine
summer hack (depending on one's tolerance for XML...)

thi

Re: GSoC: collaborative editing

[Richard M Stallman]

    Basically what you're saying is "OK, let's impose an arbitrary total
    ordering on the changes."  Indeed that makes writing the collaborative
    tool easier, but it also undermines collaboration by giving priority
    to getting there *first* rather than doing it *better*.

With all due respect, I think that is a misunderstanding of the issue.
We are talking about editing conflicts on timescales of a few seconds.
If two people are trying to edit the same part of the text at the same
time, they are stepping on each other's feet.  Which one does the
stepping "better" is hardly an issue.

Re: GSoC: collaborative editing

[Brian Templeton]

If anyone would be willing to mentor me for this project, please email
me _immediately_ (or contact me via jabber, jid bpt@hcoop.net). I don't
expect to need much direct assistance, but I do need someone to evaluate
my work for Google.

Re: GSoC: collaborative editing

[Brian Templeton]

Brian Templeton <bpt@tunes.org> writes:

> If anyone would be willing to mentor me for this project, please email
> me _immediately_ (or contact me via jabber, jid bpt@hcoop.net). I don't
> expect to need much direct assistance, but I do need someone to evaluate
> my work for Google.

To be specific, if nobody volunteers within the next five hours or so I
probably won't be able to work on this project unless I'm able to find
other funding.

Re: GSoC: collaborative editing

[Thomas Lord]

On Tue, 2009-04-14 at 05:09 -0400, Brian Templeton wrote:

> Most published algorithms on P2P collaborative editing implicitly or
> explicitly assume the availability of a fairly reliable network, and
> assume that peers can stay in almost constant contact with each other.

It's not really that simple and detached operation
semantics, robustly handled, are important ... but
beyond scope for a summer project.

-t

Re: GSoC: collaborative editing

[Thomas Lord]

On Tue, 2009-04-14 at 12:42 +0200, Thien-Thi Nguyen wrote:

> I would agree if given s/server/protocol/g.  A p2p-oriented
> XMPP-speaking Emacs-Lisp-implemented server would be a fine
> summer hack (depending on one's tolerance for XML...)
> 

Hopefully with some tasteful and forward-looking
design of the  abstractions it floats to clients, 
perhaps so.

-t

Re: GSoC: collaborative editing

[Thomas Lord]

On Tue, 2009-04-14 at 17:14 -0400, Richard M Stallman wrote:
> Basically what you're saying is "OK, let's impose an arbitrary total
>     ordering on the changes."  Indeed that makes writing the collaborative
>     tool easier, but it also undermines collaboration by giving priority
>     to getting there *first* rather than doing it *better*.
> 
> With all due respect, I think that is a misunderstanding of the issue.
> We are talking about editing conflicts on timescales of a few seconds.
> If two people are trying to edit the same part of the text at the same
> time, they are stepping on each other's feet.  Which one does the
> stepping "better" is hardly an issue.


You still need a way to keep remote buffers in sync
and to re-sync them after temporary netsplits.
The issue Stephen is worried about is that the 
proposal offered is to ignore that problem and
assume a reliable network.   FWIW I think Stephen's
concerns are valid but that there is value in a 
short experimental project that ignores the problem
to get something basic working - at least as long
as there is some confidence that the solution to the
simpler problem stands a good chance of growing into
a solution for the more general problem.  Stephen
is right on strategy here but the offered tactic
might have some value anyway.  (Or it might not, I'm
not evaluating.)

-t