CRDTs: Replicas That Merge Without Coordinating

The problem. A phone is offline, two data centers lose their link, or a collaborative editor lets two people type at once. Each replica keeps accepting writes. Later they must agree without a central referee and without throwing work away. Locking or consensus would block the writers; a CRDT (conflict-free replicated data type) avoids the conflict by design.

The merge rules. If the merge of two states is commutative (order does not matter), associative (grouping does not matter) and idempotent (merging the same state again changes nothing), then replicas converge no matter how messages are reordered, delayed or duplicated. That is exactly what unreliable networks do, so it is exactly the guarantee you want.

G-counter (grow-only counter). Give every replica its own slot in a map from replica id to count. A replica only increments its own slot. The value is the sum of all slots. Merge takes the larger number in each slot. Because each slot has one writer and only grows, the maximum is always the newest value. A like counter or view counter spread over several regions works this way.

class GCounter:
    def __init__(self, replica):
        self.replica, self.slots = replica, {}

    def increment(self, n=1):
        self.slots[self.replica] = self.slots.get(self.replica, 0) + n

    def value(self):
        return sum(self.slots.values())

    def merge(self, other):
        for r, n in other.slots.items():
            self.slots[r] = max(self.slots.get(r, 0), n)

a, b = GCounter('a'), GCounter('b')
a.increment(3); b.increment(2)         # concurrent, while disconnected
a.merge(b); a.merge(b)                 # merging twice is harmless
b.merge(a)
print(a.value(), b.value())            # 5 5

PN-counter. A counter that can also go down uses two G-counters: one for increments and one for decrements. The value is the first sum minus the second. You cannot decrement a slot directly, because then the max-merge would bring the old larger value back.

Sets. A grow-only set merges by union. To allow removal, an observed-remove set tags every add with a unique id, and a remove deletes only the tags it has seen. If one replica adds an element while another removes it, the add carries a tag the remover never saw, so the element survives: 'add wins'. That matches what users expect from a shared shopping cart or list.

Registers. A last-writer-wins register keeps the value with the highest timestamp. It is simple and always converges, but it silently discards one of two concurrent writes, and clock skew between replicas can make the 'last' write the wrong one. Using logical clocks or keeping both values for the application to resolve avoids that.

What it costs. CRDTs carry metadata: per-replica slots, unique tags, tombstones for removals. That metadata can grow without bound unless you garbage-collect it once all replicas have seen it. Also, convergence is not the same as intent: a merged text document is consistent but may not read the way either author meant. Use a CRDT when availability and offline writes matter more than strict ordering.