Concepts
Operational transformation vs CRDT
Intuition
Two people edit the same text at the same time, each on their own copy, seeing their own change instantly; the problem is that an instruction like "insert at position 5" comes to mean something else after the other person inserts something before that position. There are two ways to solve this: each copy rewrites the instructions that arrive from outside, taking into account the ones it has already applied (in Wave, a central server organizes this), or the data is designed so that changes made at the same time give the same result in any order. In the first case the complexity lies in the rewriting algorithm; in the second, in the design of the data.
How it works
In Operational Transformation (OT), local operations run without blocking and remote operations are transformed before they are executed, so local response time does not depend on network latency. In Google Wave, document operations describe the change by position (retain, insert, delete), and the client waits for the server's acknowledgment before sending more operations, composing the pending ones while it waits; this way the server keeps a single state space (the history of applied operations) and only needs to transform each incoming operation against that history, at the cost of a client seeing blocks of another client's operations at intervals of about one round-trip time. CRDTs take the opposite path: instead of transforming operations, you choose data types whose mathematical properties (monotonicity in a semilattice and/or commutativity) guarantee there are no conflicts, which gives Strong Eventual Consistency (SEC), where replicas that have delivered the same set of updates have equivalent state, with no reconciliation period and no arbitration. In a CvRDT (state-based), the states form a semilattice, merge computes the least upper bound (LUB), and each update only makes the state grow; because the LUB is commutative, associative, and idempotent, the order and duplication of merges do not matter, and with eventual delivery and termination SEC is guaranteed. In a CmRDT (operation-based), there is no merge: SEC is guaranteed if concurrent operations commute, delivery uses reliable broadcast with causal order, and the methods terminate. An SEC replica is always available for reads and writes, even under a network partition; the SEC object tolerates up to n-1 simultaneous crash failures and does not require consensus. The price is semantic: SEC is incomparable with sequential consistency, and the rule for concurrent operations (for example, add wins or remove wins) is a choice that depends on the application.
In practice
Google Wave used OT for live editing of rich text and of structured documents in general, with clients and a server, and with each client waiting for the server's acknowledgment before sending more operations, which keeps the server simple (a single state space) at the cost of a delay of about one round-trip time between the blocks seen by another client. You would choose CRDT when replicas need to accept writes even under a network partition or while disconnected, without depending on consensus, as in the cloud, P2P and disconnected-operation scenarios cited in the paper. In that case you must accept the semantics fixed by the data type for concurrent writes (such as add-wins), which can produce results that are impossible in a sequential execution.
Use it in a design
Practice the cases that rely on this concept in the System Design school.