**Operational Transformation**

**Demystified**

1989: Ellis & Gibbs: GROVE

**History**

**The problem**

**It's not ...**

**... an algorithm**

**Rather**

a bunch of technologies for

Collaborative Editing

**The future**

**Prediction: By 2020 real-time collaboration will be standard in every editor**

Alice

Bob

O1

O1

O2

O2

"abc"

"abc"

Insert(0, 'x')

Delete(2, 1)

"xabc"

"xac"

"ab"

"xab"

Solution (kinda): server side ordering

Alice

Bob

O1

O2

"abc"

"abc"

Insert(0, 'x')

Delete(2)

"xabc"

"xac"

"xac"

Server

O1

O2

O1

O2

"xabc"

**}**

latency

Alice

Bob

O1

O1'

O2

O2'

"abc"

"abc"

O1 = Insert(0, 'x')

O2 = Delete(2)

"xabc"

"xab"

"ab"

"xab"

Solution (kinda): dOPT algorithm

O1' = T(O1, O2) = Insert(0, 'x')

O2' = T(O2, O1) = Delete(

3

)

**Resources:**

http://en.wikipedia.org/wiki/Operational_transformation

Wikipedia, surprisingly comprehensive:

http://www3.ntu.edu.sg/home/czsun/projects/otfaq/

OT FAQ, totally comprehensive:

https://www.lri.fr/~mbl/ENS/CSCW/2012/papers/Ellis-SIGMOD89.pdf

The original paper by Ellis and Gibbs from 1989:

Consistency maintenance

Conflict resolution

Group undo

Locking

Operation compression

Consistency-related requirements

Causality preservation

O1

O1 = Insert('What is the sum of 2 + 3?')

O1

O2

O2

What is the sum of 2 + 3?

O2

What is the sum of 2 + 3?

O2 = Insert('The sum is 5')

O1

What is the sum of 2 + 3?

The sum is 5

The sum is 5

What is the sum of 2 + 3?

The sum is 5

O1

O1'

O2

O2'

"abc"

"abc"

O1 = Insert(0, 'x')

O2 = Delete(2, 1)

"xabc"

"xab"

"ab"

"xab"

O1' = T(O1, O2) = Insert(0, 'x')

O2' = T(O2, O1) = Delete(

3

, 1

)

Convergence

O1

O1'

O2

O2'

"abcde"

"abcde"

O1 = Insert(1, '12')

O2 = Delete(2, 2)

"a12bcde"

"a12be"

"abe"

"a12be"

O1' = T(O1, O2) = Insert(1, '12')

O2' = T(O2, O1) = Delete(

4

, 2)

Intention preservation

Intention: delete "cd"

Intention: delete "cd"

1995: Nichols et al.: Jupiter

2009: Wang et al: Google Wave

2010: Google Docs

**Years of academic research**

**Mainstream**

Character-wise transformation rules

tie break

Identity (do nothing)

Case study: Google Docs

Undo effect and undo property

O1

O2

"12"

"12"

O1 = Insert(2, 'y')

"12y"

"x12"

"12y"

"x12"

Undo(O1)

O2 = Insert(0, 'x')

"x12y"

"x12y"

Undo(O2)

"12"

"12"

Undo effect:

Undo not the last operation

Undo property:

Undo all operations in any order results in the original state

Compression effect

O1

O2

"123"

"123"

O1 = Insert(2, 'x') L = [O1]

"12x3"

O2 = Insert(1, 'abc') L = [O1, O2]

"1abc2x3"

O3

O3 = Insert(2, 'y') L = [O1, O2, O3]

"1aybc2x3"

O4

O4 = Delete(7, 1) L = [O1, O2, O3, O4]

"1aybc23"

L' = Compress(L = [O1, O2, O3, O4]) = [O2']

O2' = Insert(1, 'aybc')

"1aybc23"

"1aybc23"

Compression effect

L and L' has the same effect when applied to the original state

Alice

Bob

O1

O1

O2

O2'

"abc"

"abc"

O1 = Insert(0, 'x')

O2 = Delete(3)

"xabc"

"xab"

Solution (kinda): Locking

"xabc"

Lock

"xab"

Lock

Interactivity

Alice

Bob

O1

O1

O2

"abc"

"abc"

O1 = Insert(0, 'x')

O2 = Delete(2)

"xabc"

"xab"

Solution (kinda): Rebasing

"xab"

"ab"

O2

O1'

O1' = Undo(O1)

"abc"

O2 = Delete(2)

"ab"

O1

O1 = Insert(0, 'x') = Undo(O1')

2011: Share.js

Derby, Meteor, Firebase etc.

Alice

Bob

Carlos

What is the sum of 2 + 3?

The sum is 5

Alice

Bob

OT

* requires additional distributed computing techniques

Present