Removed on your phone, re-added on your laptop. Is it in the cart?

transcript

Offline, your phone removes item C from your cart. Your laptop, also offline, adds C again. They sync. Is C in the cart?

First, the naive way. A plain set, merged by union. Start with A and B. Node 1 removes B. It holds just A. Node 2, at the same time, adds C. It holds A, B and C. Union them. B is back. The remove was simply lost.

An OR-Set fixes it. Every add gets a unique tag. Both devices hold C, with tag one. The phone's remove tombstones only the tags it has seen. Tag one. The laptop's add made a fresh tag. Tag two. The remove never saw it. Merge. Tag one is dead. Tag two is alive. So C is in the cart.

And that plain-set bug? B's tags were tombstoned. So B stays removed. A concurrent re-add survives. Add wins over a concurrent remove. And it doesn't matter which device synced last.

Which synced last is last-write-wins thinking. An OR-Set removes what it saw, and keeps what it didn't.

Full breakdown in the lecture.