Questions: Operational Transformation for Collaborative Editing

Question 1

Users A and B both start with the string 'hello'. A inserts '!' at position 5 (→ 'hello!'). Simultaneously, B inserts '?' at position 5 (independently intending 'hello?'). When B's insert arrives at A's replica, what must OT do to preserve both users' intentions?

• A. Apply B's insert at position 5, overwriting A's '!' with '?'
• B. Discard B's insert because A's operation was applied first locally
• C. Transform B's insert to position 6 so both characters are preserved, producing 'hello!?'
• D. Merge both characters randomly and propagate the result to all replicas

Answer: (C)

OT's job is *intention preservation*: both users intended to append a character, so both characters must appear. When two insertions target the same position, the transformation function adjusts one index (using a deterministic tiebreaker like user ID to decide ordering) so both characters end up in the document. Applying B's insert at position 5 without transformation (option A) would place '?' before '!' — or displace '!' — violating A's intent. Discarding B's edit (option B) would violate B's intent. OT must transform to produce a result that reflects both operations.

Question 2

Why does operational transformation require a central server or an agreed-upon total ordering of operations, while CRDTs do not?

• A. OT operations contain too much metadata to be broadcast efficiently in a peer-to-peer network
• B. OT transformation functions must be applied in a consistent order at every replica; without a serialization point, the same transformations applied in different orders at different sites can diverge
• C. CRDTs are incompatible with the text editing operations that OT is designed for
• D. OT was invented before peer-to-peer networking existed and has never been updated

Answer: (B)

OT convergence is order-sensitive: the transformation function T(op1, op2) produces a different result depending on which operation is treated as 'already applied' and which as 'incoming.' Without a canonical order, two replicas may apply the same set of transformations in different sequences and reach different final states. A central server (as in Google Docs) serializes all operations into a single canonical order and broadcasts transformed operations to clients, ensuring all replicas apply the same sequence. CRDTs are designed so that merging is commutative, associative, and idempotent — order literally does not matter, enabling true peer-to-peer operation.

Question 3

In OT, the transformation function adjusts operation indices to account for the effects of concurrent operations, ensuring that when applied in any order all replicas reach the same final document state.

• T. True
• F. False

Answer: True

This is the core mechanism of OT. When User A inserts a character before position p, any concurrent operation targeting position ≥ p must have its index incremented by one before being applied to A's replica — otherwise it would target the wrong character. The transformation function encodes these adjustment rules for every pair of operation types (insert-insert, insert-delete, delete-delete). Correctly applying these transforms makes operations commutative, so the final state is the same regardless of which order the operations arrive.

Question 4

Operational transformation is a fully decentralized protocol that allows clients to exchange operations directly peer-to-peer without any central coordinator.

• T. True
• F. False

Answer: False

OT requires a central server or agreed-upon total order to serialize concurrent operations. Without serialization, replicas applying the same transformation functions in different orders can diverge — a notoriously difficult class of bug to reproduce and debug. Systems like Google Docs use a central server that determines the canonical order and broadcasts transformed operations to all clients. CRDTs are the decentralized alternative: they achieve convergence without coordination by using data structures where merge operations are order-independent.

Question 5

Using the 'abc' example from the topic, explain how OT's transformation function preserves both users' intentions when concurrent edits would otherwise corrupt the document.

Model answer: User A inserts 'X' at position 1 (intending 'aXbc'); concurrently, User B deletes position 2 (intending to remove 'b' from 'abc', producing 'ac'). When B's delete arrives at A's replica, A has already applied the insertion. Position 2 now refers to 'X' rather than 'b' — applying the delete naively would remove the wrong character. OT transforms B's operation: because A inserted at position 1 (before position 2), everything shifted right by one, so B's delete index must be incremented to position 3. The transformed delete applied to 'aXbc' correctly removes 'b', producing 'aXc'. Both users' intentions — insert 'X' and delete 'b' — are preserved.

This example illustrates the fundamental problem OT solves: concurrent edits encode intentions about a document state that may no longer exist when the operations arrive. The transformation function 'interprets' each arriving operation in light of what has already happened, adjusting indices to make the operation target its intended content rather than whatever character now happens to occupy the original index.