5 / 5 CRDTs, Gossip & Anti-Entropy

The Todo Comes Back

An offline-first todo app syncs by taking the union of the item sets on each device, exactly the way Dynamo's shopping cart merges concurrent versions. A user deletes "renew passport" on their phone. Their laptop, which has been offline since before the delete and never saw it, comes back online and syncs. The item reappears.

What is going on, and what actually fixes it?

A

The sync interval is too long. Syncing on every change means the laptop learns about the delete before it can contribute a stale copy.

B

A union has no way to represent a removal, so the laptop's older copy reintroduces the item. An observed-remove set fixes it by tagging each add with a unique id and recording which tags a remove observed, so a remove beats the adds it saw and a genuinely concurrent add still survives.

C

The phone's version is newer by wall clock, so the merge should have preferred it. Stamping each version with a physical timestamp and taking the latest resolves the merge correctly.

D

Add a tombstone set so removes stick, giving a two-phase set. Tombstones are tiny, so there is no real cost to this over the observed-remove design.