Milk on the train, gone by dinner
Lena added milk to the household shopping list, which already held bread and eggs, on the train, in a tunnel with no signal. A few minutes later Tomás, at home on wifi, added coffee. When Lena's phone reconnected, the list showed coffee and no milk, and both phones said they had synced.
The app is built the way offline-first apps usually are. Each phone keeps its own copy of the list and writes to it immediately, network or not, and a sync server exchanges changes when it can. Every copy is a replica that accepts writes without asking anyone first. Regions in a multi-leader setup and nodes in a leaderless store behave the same way, and the setups themselves are explained in Replication & read replicas. What all of them run into is the same: two writes to the same item, each accepted by a replica that did not know about the other.
Those two writes are concurrent, and the word is not about the clock. Lena wrote at 18:02 and Tomás at 18:07, and the writes are still concurrent, because neither was made with the other in view: Tomás's phone had never seen the milk, and Lena's had never seen the coffee. When neither version was built on the other, there is no newest list to keep, only two different lists, and something has to decide what the list becomes. That decision is conflict resolution. The sync server had made one without telling anyone.
The rule that quietly picked a winner
The server's rule was last-write-wins (LWW): every write carries a timestamp, and when two versions of an item meet, the one with the higher timestamp is kept and the other is discarded. Tomás's 18:07 beat Lena's 18:02, so the list became his version, coffee and no milk. LWW has real virtues: it needs nothing beyond a timestamp per write, and, with a fixed tie-breaker for equal timestamps, every replica that has seen both versions picks the same one. Cassandra, for example, resolves concurrent writes to the same column by their write timestamps.
Its cost is in the word discarded. LWW does not merge; it chooses, and the losing write disappears without a trace, even though the user who made it was told it was saved. And its idea of "last" is weaker than it looks:
- Clocks disagree. Each phone stamps writes with its own clock. Had Lena's phone been ten minutes fast, her write would have been stamped 18:12 and would have won, deleting the coffee. Server clocks drift too, usually by less.
- Later is not informed. Even with perfect clocks, Tomás's write was later only by the clock. It was not made with the milk in view, so keeping the later version means throwing away one of two independent edits.
- Another order changes nothing essential. A logical counter with the replica id as a tie-breaker removes the dependence on physical clocks, and one of the two concurrent writes is still thrown away.
LWW is the right rule when overwriting is what the user means: a profile photo, a device's last known location, a setting changed on one device and then on another. It is the wrong rule wherever two people add to the same value, which is what a shopping list stored as one value is. Storing the whole list as one value made it worse, because every item shared the list's fate. Had each item been its own record, milk and coffee would never have collided, and LWW would only bite when both phones changed the same item. Finer granularity makes conflicts rarer; it does not remove them.
The lost update inside a single database looks similar, and Transactions & isolation levels shows how a database prevents it: there, one database sees both writes and can make one wait or fail. Here, no single place saw both writes before they were accepted.
Telling a replacement from a rival
Not every pair of versions is a conflict. If Tomás opens the list after Lena's milk has synced, removes bread and saves, his version was built on top of hers, and keeping it loses nothing. What the server lacked was a way to tell that case from the train case, and timestamps cannot. A version vector can.
A version vector keeps one counter per replica that writes the item. When a replica writes, it increments its own entry, and the version is stored with the resulting vector. To compare two versions, compare their vectors entry by entry. If every entry of A is less than or equal to the matching entry of B, and at least one is smaller, B was made with A in view: A happened before B, and B can replace A. Equal vectors mean the same version. If A is ahead in one entry and B in another, neither saw the other, and they are concurrent.
Run the train through it, with Lena's phone as replica L and Tomás's as replica T. Both phones start from the list at [L:3, T:5]. Lena's milk makes her copy [L:4, T:5]; Tomás's coffee makes his [L:3, T:6]. When the server compares them, the first is ahead in L and the second in T, so it knows they are concurrent, and instead of choosing it keeps both versions, called siblings, and returns both on the next read.
That is the point and the limit of the technique. A version vector detects concurrency; it does not resolve it. Silent loss becomes an explicit pair of versions, handed to whoever reads next. For the list, the app can take the union: bread, eggs, milk, coffee. It saves the merged list with the entry-by-entry maximum of the siblings' vectors, [L:4, T:6], and then increments its own entry for the new write; if Lena's phone did the merge, that gives [L:5, T:6]. That vector is ahead of both siblings, so the merged list replaces them.
The union that brought the eggs back
Union looks like the obvious merge for a list, and it has a flaw that Amazon's Dynamo paper reported about the shopping cart, whose siblings were merged this way: deleted items can come back. A week later, both phones hold [L:5, T:6] with bread, eggs, milk and coffee. In the shop, offline, Lena buys the eggs and removes them, making [L:6, T:6]. At home, Tomás adds rice, making [L:5, T:7]. The versions are concurrent, the app merges them by union, and the eggs are back on the list.
The union cannot tell "Tomás's version has eggs because he never saw them removed" from "Tomás added eggs". A list records what is in it, not how each item got there or left, and a correct merge needs that history.
Data types that merge themselves
A CRDT (conflict-free replicated data type) is a data type designed so that concurrent updates can always be merged, with no conflict left over for anyone to resolve. In the state-based form, each replica holds the full state and merges any state it receives into its own. The merge function is:
- commutative, so the order in which updates arrive does not matter;
- associative, so it does not matter how updates are grouped or relayed;
- idempotent, so a duplicated or retried sync changes nothing.
Together with one more property, that a local update only ever moves the state forward, so that merging in an older state can never undo it, these give convergence: any two replicas that have received the same updates hold the same state, whatever order, duplication or route the updates took. The condition is part of the guarantee. A replica cannot reflect an update it never received, so the replicas are guaranteed to agree only once every update has reached every replica, and the sync still has to keep retrying until it does. What a CRDT removes is the need to agree beforehand: no lock and no coordinator, just a local merge whenever states meet.
For the list, a set CRDT replaces the plain list. In an observed-remove set (OR-Set), every add attaches a unique tag to the element, so Lena's original "add eggs" became eggs#a1. A remove deletes only the tags the removing replica has seen, and records them as removed. In the shop, Lena's remove marks a1 as removed; Tomás's rice arrives as rice#t9. When the phones exchange states and merge, a1 is known to be removed, so the eggs stay off, rice#t9 is kept, and both phones end with bread, milk, coffee and rice.
Diagram components: Client, Data Store, Client, Data Store, Message, Message.
Each phone writes to its own replica, sends its state to the other, and merges what it receives into its own state. Both end with the same list, whichever state arrives first.
Now suppose Tomás had noticed the eggs were out and added them again while Lena was removing them. His add creates a new tag, eggs#t10, which Lena's remove never saw, so it survives the merge and the eggs stay on the list. That is why an OR-Set is called add-wins: when an add and a remove of the same element are concurrent, the add wins. It is a decision, made once by the choice of data type, and it suits a shopping list; a remove-wins set makes the opposite choice. A CRDT does not work out what the users meant. It applies one rule identically everywhere.
What merging cannot do
The price is metadata. A straightforward OR-Set keeps removed tags, called tombstones, so that an old state arriving late cannot bring an element back, and can discard them only once every replica has seen the remove; optimised variants shrink this, and what remains, like a version vector, still grows with the number of replicas.
And convergence is not correctness. Replicas agreeing on a state does not mean the state obeys your rules. A rule that depends on what other replicas are doing at the same moment cannot be checked by one replica acting alone: stock never below zero, one account per username, no more than ten seats sold. Two offline replicas can each sell the last seat, and a counter CRDT will merge the two sales faithfully into minus one seat left. Such rules need agreement before the write is accepted, the strong side of the trade described in Consistency models: strong vs eventual (CAP), through a single leader or a transaction, which usually means giving up the offline write for that operation.
When the app, or a person, has to decide
Some conflicts have no rule a data type can apply. Lena changes the list's note to "oat milk, the barista one"; Tomás, offline, changes the same note to "any milk, we're out". Merging the two edits character by character can produce a sentence nobody wrote, and LWW drops one of them. Keeping both siblings and showing them to the next person who opens the note lets a human choose. File-sync tools often do a version of this, saving a conflicted copy next to the original.
Other conflicts have a rule that belongs to the domain: if two phones change the household's delivery slot, the slot the shop has confirmed wins. That logic lives in the application, and runs when siblings are read or when the server receives a second version. It is the most flexible option and the easiest to get wrong, because the merge must give the same answer on whichever replica runs it and in whichever order it sees the versions, or the replicas stop agreeing.
Make two replicas disagree, then converge
The CRDT Replication challenge is this shopping list, drawn as roles. Give each Client its own replica, a Data Store, and let the replicas send each other their state as Messages; add a CRDT node for the data type, name it OR-Set and write the merge rule on it. Then stage the evening in the shop: Lena's remove and Tomás's add reach the two replicas in opposite orders, and both replicas still end with the same list. Two-Phase Commit, Mutex / Lock and Quorum sit in the palette as temptations. Used across replicas, every one of them makes a replica wait for another, which is exactly what this design does without.
Vector Clocks practises the detection half: each node increments its own counter, clocks merge by entry-by-entry maximum, and a concurrent pair is surfaced as a conflict instead of overwritten. Multi-Region Active-Active asks you to pick and justify a conflict-resolution rule for concurrent writes to the same record, which is this article's whole choice at the scale of a region.