Operational Transformation (OT)

The Convergence property guarantees that all clients applying the same set of operations, regardless of the order they are received, will eventually arrive at an identical final document state. This is the primary goal of OT: eventual consistency.

• Mechanism: Achieved through transformation functions that adjust the parameters of an incoming operation based on previously executed concurrent operations.
• Example: If Client A inserts "X" at position 1 and Client B concurrently inserts "Y" at position 1, transformation ensures one client sees "XY" and the other sees "YX", not "X" overwritten by "Y" or vice-versa.

Causality Preservation ensures that the order of operations respects their cause-and-effect relationships. If operation O1 causally precedes operation O2 (e.g., O2 was created with knowledge of O1's effects), then O1 will be applied before O2 on all sites.

• Foundation: Relies on a vector clock or Lamport timestamp mechanism to track the partial order of events.
• Violation Consequence: If causality is broken, a user might see text inserted after it was already deleted, creating a logical paradox and breaking user intent.

The Intention Preservation property states that the effect of executing an operation on any document state must match the original intent of the user who generated it, even after transformation. This is the most subtle and critical property.

• User Intent: Defined by the operation's parameters (e.g., "insert 'cat' at index 5") relative to the document state the user saw when creating it.
• Challenge: A simple positional shift is insufficient. If a user intends to delete a specific word, the algorithm must ensure that word is deleted even if other users have inserted text around it.

OT algorithms are built on a pair of transformation functions, TP1 and TP2, which must satisfy formal conditions for correctness.

• TP1(Oa, Ob): Transforms operation Oa against the concurrent operation Ob, producing Oa' which can be applied after Ob.
• TP2(Ob, Oa): Similarly transforms Ob against Oa, producing Ob'.
• Condition TP1: Apply(Apply(S, Oa), TP1(Ob, Oa)) == Apply(Apply(S, Ob), TP2(Oa, Ob)). This ensures convergence.
• Condition TP2: TP2(TP1(Oa, Ob), TP1(Ob, Oa)) == TP1(TP2(Oa, Ob), TP2(Ob, Oa)). This ensures transformation is reversible and consistent for sequences of operations.

Support for Inverse Operations (or undo) is a key feature enabled by OT. To undo an operation, the system generates and applies its inverse, which must also be correctly transformed against any concurrent operations.

• Process: Undoing operation O requires generating its inverse, inverse(O). If concurrent operations occurred, inverse(O) must be transformed against them before application.
• Guarantee: A correct OT system ensures that Apply(Apply(S, O), transform(inverse(O), O')) returns to the state before O was executed, even in the presence of concurrent operation O'.

Strong consistency (or linearizability) is a strict distributed systems guarantee where any read operation on a data item returns the value from the most recent write operation that completed before the read began. This provides the illusion of a single, up-to-date copy of the data.

• OT's Goal: Operational Transformation algorithms are typically deployed within a central server architecture to achieve strong consistency for all collaborating clients in real-time.
• Requires Coordination: Often implemented via a primary node, consensus protocol (like Raft), or a central transformation server that serializes operations.
• Trade-off: Can reduce availability during network partitions, as the system may block writes to maintain consistency.

Event sourcing is an architectural pattern where the state of an application is derived from a sequence of immutable events stored in an append-only log, rather than storing just the current state. The current state is rebuilt by replaying the event log.

• Relationship to OT: OT's sequence of transformed operations (insert, delete) forms an event log. The document state is the result of applying this log. Event sourcing provides a natural audit trail and enables state reconciliation.
• Key Benefit: Enables temporal queries ("what was the state at time T?") and simplifies rebuilding state for new replicas.
• Common Companion: Often paired with CQRS (Command Query Responsibility Segregation) to optimize read and write models separately.

State reconciliation is the general process of resolving differences between two or more divergent versions of a state to produce a single, consistent final state. It is the overarching problem that OT, CRDTs, and version control systems (like Git) aim to solve.

• OT's Approach: Uses transformation functions to adjust concurrent operations so they can be applied in any order to achieve the same state.
• Three-Way Merge: A common reconciliation algorithm used in Git that compares a common ancestor with two divergent branches to automatically merge changes where possible.
• Manual Fallback: When automatic reconciliation fails (e.g., a merge conflict), human intervention is required to resolve the inconsistency.

A Write-Ahead Log (WAL) is a fundamental durability mechanism where all modifications to state are first recorded as entries in a sequential, append-only log on stable storage before the actual state is updated. This ensures recoverability after a crash.

• Role in Stateful Systems: Critical for databases (PostgreSQL, SQLite) and stateful stream processors (Apache Kafka, Apache Flink) to guarantee exactly-once semantics and atomicity.
• Connection to OT/Event Sourcing: The log of transformed operations in an OT system or the event log in event sourcing serves a similar purpose: it is the persistent, ordered record of all state changes.
• Mechanism: On recovery, the system replays the WAL to reconstruct the last consistent state.