4 / 5 CRDTs, Gossip & Anti-Entropy

Removed Then Added Again

An add-wins set (the observed-remove set) is replicated on R1 and R2. Both start holding the single element urgent. Nothing syncs until the last step.

step R1 R2
0 {urgent} {urgent}
1 rmv(urgent) gives {}
2 add(urgent) gives {urgent}
3 rmv(urgent) gives {}
4 bidirectional sync bidirectional sync

What do both replicas hold after step 4, and why?

A

It depends on which replica merges first, so the two can settle on different answers until a tiebreak rule is added on top.

B

{urgent}. Add-wins keeps an element unless some remove happened after an add of it, and R2's remove is concurrent with R1's add rather than after it.

C

{}. Two removes against one add, so the removes carry the majority and the element is gone.

D

{}. R2's remove is concurrent with R1's add, and a concurrent add and remove is exactly the case where the remove is defined to win.