Loading presentation...

Present Remotely

Send the link below via email or IM

Copy

Present to your audience

Start remote presentation

  • Invited audience members will follow you as you navigate and present
  • People invited to a presentation do not need a Prezi account
  • This link expires 10 minutes after you close the presentation
  • A maximum of 30 users can follow your presentation
  • Learn more about this feature in our knowledge base article

Do you really want to delete this prezi?

Neither you, nor the coeditors you shared it with will be able to recover it again.

DeleteCancel

Make your likes visible on Facebook?

Connect your Facebook account to Prezi and let your likes appear on your timeline.
You can change this under Settings & Account at any time.

No, thanks

Operational Transformation Demystified

No description
by

Attila Gazso

on 17 December 2013

Comments (0)

Please log in to add your comment.

Report abuse

Transcript of Operational Transformation Demystified

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
Full transcript