GSoC - Telepathy based collaborative real-time text editor for KDE

Picture 1 – my ultimate ui-goal

Contents:

1. Why KDE?
2. Why Telepathy?
3. Why collaborative editor?
4. Intro
5. What OT already solved?
6. First goal – write system that fits OT requirements.
7. Why OT is not enough?
8. Second goal – write system that fits our expectations.

Why KDE?

It's very easy. Because I use openSUSE with KDE every day for more than a year.

Why Telepathy?

Telepathy give access to quick and easy tools to connect users via the internet. I need to use Telepathy D-Bus tube since I want to get rid from the client-server architecture. Also, if I would have any questions, telepathy have big and responsive community to answer them.

Why collaborative editor?

From time to time I need such tool to communicate with my friends and classmates. This is a great area to apply my knowledge. It allow me to gain experience in development and support software.

Intro

A collaborative real-time text editor is a form of collaborative software application that allows several people to edit a computer text file using different computers in real-time.

The complexity of real-time collaborative editing solutions stems from communication latency. In theory, if communication were instantaneous, then creating a real-time collaborative editor would be no more difficult than creating a single-user editor.

Operational transformation (OT) usually used for collaborative editors. OT is a technology for supporting a range of collaboration functionality in advanced groupware system.

What OT already solved?

1. Convergence requirement.
   All replicas of the shared document must be identical after executing the same group of operations.
   
   
   Since in my system all clients would receive the same events to execute and use the same rules to evaluate events all replicas of the document must be the same.
   
   
2. Intention-preservation requirement.
   The local effect of an operation must be preserved at remote site in the face of concurrency.
   
   
   Since in my system all events would have their priority by time and user that send event all clients would have know the proper timeline of events.
   
   
3. Causality-preservation requirement.
   Operations must be performed in their cause-effect order.
   
   
   I can use the Telepathy D-Bus to trace proper order of operations.

First goal – write system that fits OT requirements.

My proposal is to simulate real-time editing with relative content displaying. But first things first.

For example, I write “H”, then “e”, then “l”, then “l”, then “o” (H-e-l-l-o in future). When I type “H” my friend Bob already understand what I want to type. He press “enter” and type H-i-!

All text editing operations can be do, undo and redo again.

I type H-e-l-l-o. I make 5 insert operations... of what and where? “Character “H” on the 0 position” and so on you may say. Not. I “do” insert “unique object one” (which is character “H”) after the start of the document at the exact time and so on.

Each client have Timeline (T) consist of unique events (UE), Set of Content (SC) consist of unique objects(UO) and independent Cursor (C).

Picture 2 – architecture overview

Here I explain work of the system on my first goal. Further – my action (I), my computer's (my_c), bob's (bob) and bob computer;s (bob_c) step-by-step after creation of the document. Each event produced by current client would send to every clients.

Start time (start)

I type “H”.

my_c make and send UE1: do insert UO1 which is “H” in this time at the start of the document.

my_c receive UE1.

my_c apply UE1 and use this event “do” operation (which is push UO1 “H” to the SC.

my_SC: “H”

my_T: UE1

bob_SC: “

bob_T:

start + 100 ms

bob_c receive UE1.

bob_c apply UE1 and use this event “do” operation (which is push UO1 “H” to the SC.

Bob type <Enter>.

bob_c make and send UE2: do insert UO2 <enter> start + 100ms at the place of his C (in future – do(insert, UO2(<enter>),start+100,bob_C)).

bob_c receive UE2.

bob_c apply UE2.

I type “e”.

my_c make and send UE3: do(insert, UO3(“e”),start+100,my_C).

my_c receive UE3.

my_c apply UE3.

my_SC: “He”

my_T: UE1-UE3

bob_SC: “H<enter>”

bob_T: UE1-UE2

start + 110 ms

Bob type “H”.

bob_c make and send UE4: do(insert, UO4(“H”),start+110,bob_C)).

bob_c receive UE4.

bob_c apply UE4.

I type “e”.

my_c make and send UE5: do(insert, UO5(“l”),start+110,my_C)).

my_c receive UE5.

my_c apply UE5.

my_SC: “Hel”

my_T: UE1-UE3-UE5

bob_SC: “H<enter>H”

bob_T: UE1-UE2-UE4

start + 160 ms

my_c receive UE2.

my_c UE2 is earlier than UE5 – undo UE5.

my_c UE2 is earlier than UE3 – undo UE3.

my_c do UE2.

my_c redo UE3.

my_c redo UE5.

bob_c receive UE3.

bob_c UE3 is earlier than UE4 – undo UE4.

bob_c do UE3.

bob_c redo UE4.

my_SC: “H<enter>el”

my_T: UE1-UE2-UE3-UE5

bob_SC: “H<enter>eH”

bob_T: UE1-UE2-UE3-UE4

start + 170 ms

my_c receive UE4.

my_c UE4 is earlier than UE5 – undo UE5.

my_c do UE2.

my_c redo UE5.

bob_c receive UE5.

bob_c do UE5.

my_SC: “H<enter>eHl”

my_T: UE1-UE2-UE3-UE4-UE5

bob_SC: “H<enter>eHl”

bob_T: UE1-UE2-UE3-UE4-UE5

Why OT is not enough?

For example, I write “H”, then “e”, then “l”, then “l”, then “o” (H-e-l-l-o in future). When I type “H” my friend Bob already understand what I want to type. He press “enter” and type H-i-! What we expect to see? It's obviously, not a something like:

H<enter>eHlilo! (1)

There is the right output:

Hello<enter>Hi! (2)

If we look closer on the first output, we would see that it correct in OT terms (in time and place of inserting characters), but it still not fits our expectations.

Second goal – write system that fits our expectations.

Not already sure how I solve this problem. Probably it would be some mix of prioritized event and clients level of access. For example, client have priority to perform his action in less of 100 ms after his previous action and in this time access to undo method of timeline's unique events for received events would be closed.

But I think my system would give such opportunity.