Operational transformation
In computer science, operational transformation is a technique in building collaborative software systems.
System architecture
Collaboration systems using operational transformations typically use replicated document storage where each user has their own copy of the document. Users operate on their own local copies. Their changes are then pushed to the rest of the users. When a user receives the changes pushed from another user, they typically transform the changes before executing them.
Basics
The idea of operational transformation is to transform (or adjust) the variables of an editing operation according to the effects of previously executed operations so that the transformed operation can achieve the correct effect and maintain document consistency.
Operational transformation can be shown by using the example of a text editing scenario. 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")
generated by two users at sites one and two, suppose the two operations are executed in the order of O1 and O2 (at site one). 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 position variable 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".
Operational Transformation Media
Illustration of the TP1 property
Illustration of the TP2 property
