CRDTs: conflict-free replicated data types

Click P and Q's buttons in whatever order and however many times you like — they never talk to each other while doing it. Then hit "Merge": both boxes turn out exactly the same, holding the full total of everything either one ever did.

A G-Counter (grow-only counter) CRDT gives every replica its own slot that only that replica may increment. Merging two replicas' states takes the pointwise max of every slot:

• $A_i$, $B_i$ — replica $i$'s slot count as last seen by state $A$ or $B$.
• $\text{merge}(A,B)_i$ — the merged state's slot $i$: whichever of $A$ or $B$ has seen more of replica $i$'s increments.
• value(state) — the counter's logical total: the sum of every slot.

1. Merge is commutative and idempotent

   $\max(A_i,B_i) = \max(B_i,A_i)$ for every slot, so it never matters who initiates a merge — and merging a state with itself changes nothing, so re-merging the same update twice is harmless.

2. Merge is associative

   $\max$ over three or more values doesn't depend on how they're grouped, so merging replicas two at a time, in any order or pairing, reaches the exact same final state as merging them all at once.

Increment P and Q in any pattern — three P's then one Q, alternating, whatever. The panel always computes merge(P, Q) and merge(Q, P) side by side: they never disagree, at any point, no matter what either replica has done up to that moment.

Three replicas, each incrementing only their own slot, entirely independently:

1. Independent local states

   • P increments 3 times: $\{P{:}3, Q{:}0, R{:}0\}$
   • Q increments 2 times: $\{P{:}0, Q{:}2, R{:}0\}$
   • R increments once: $\{P{:}0, Q{:}0, R{:}1\}$

   None of them has seen either of the others' updates.

2. Merging P and Q, either direction

   $\text{merge}(P,Q) = \{P{:}\max(3,0), Q{:}\max(0,2), R{:}\max(0,0)\} = \{3, 2, 0\}$. Merging the other way, $\text{merge}(Q,P)$, produces the exact same $\{3, 2, 0\}$.

3. Bringing in R, in either grouping

   $\text{merge}(\text{merge}(P,Q), R) = \{P{:}\max(3,0), Q{:}\max(2,0), R{:}\max(0,1)\} = \{3,2,1\}$, and $\text{merge}(P, \text{merge}(Q,R))$ also comes out to $\{3,2,1\}$ — total value $6$, regardless of which two replicas happened to sync with each other first.