Pratyush | Design Collabrative Editing

Operation Tranformation

Operational transformation (OT) is a technology for supporting a range of collaboration functionalities in advanced collaborative software systems. OT was originally invented for consistency maintenance and concurrency control in collaborative editing of plain text documents

System Architecture

each client has their own copy of the document
clients operate on their local copies in a lock-free, non-blocking manner
the changes are then propagated to the rest of the clients
When a client receives the changes propagated from another client, it typically transforms the changes before executing them;
- the transformation ensures that application-dependent consistency criteria (invariants) are maintained by all sites

Basics

Given a text document with a string “abc” replicated at two collaborating sites; and two concurrent operations:

O1 = Insert[0, “x”] (to insert character “x” at position “0”)
O2 = Delete[2, “c”] (to delete the character “c” at position “2”)

Suppose the two operations are executed in the order of O1 and O2 (at site 1)

After executing O1, the document becomes “xabc”
To execute O2 after O1, O2 must be transformed against O1 to become: O2' = Delete[3, "c"], whose positional parameter is incremented by one due to the insertion of one character “x” by O1
Executing O2’ on “xabc” deletes the correct character “c” and the document becomes “xab”. However, if O2 is executed without transformation, it incorrectly deletes character “b” rather than “c”