Two Devices, No Server, No Conflicts: How Local-First Apps Merge

Software is quietly moving back toward running on your device. Apps that work on a plane, sync when they can, and never show a spinner because a server is deciding something — local-first is the usual name — and the hard part is not storage. It is what happens when two devices changed the same thing while neither could see the other.

The traditional answers are both bad. Refuse to merge and you get a conflict dialog nobody understands. Take the last write and you silently throw away somebody’s work.

Conflict-free replicated data types are the third answer, and the surprising thing about them is not the algebra. It is that the merged result is usually a list neither device was holding.

Predict the merge

Both devices started with the same list, then went offline and edited independently.

Why milk comes back

class OrSet:
    """Observed-remove set. Each add makes a UNIQUE tag; a remove deletes only the tags this
    replica has actually seen. That is the whole mechanism, and it is why concurrent
    add-and-remove resolves to add."""

    def __init__(self, replica):
        self.replica = replica
        self.adds = set()          # (element, tag)
        self.removes = set()       # tags
        self.counter = 0

    def add(self, element):
        self.counter += 1
        self.adds.add((element, f"{self.replica}{self.counter}"))

    def remove(self, element):
        for el, tag in self.adds:
            if el == element:
                self.removes.add(tag)   # only tags visible HERE

    def value(self):
        return sorted({el for el, tag in self.adds if tag not in self.removes})

    def merge(self, other):
        merged = OrSet(self.replica + other.replica)
        merged.adds = self.adds | other.adds
        merged.removes = self.removes | other.removes
        return merged

    def copy_as(self, replica):
        clone = OrSet(replica)
        clone.adds = set(self.adds)
        clone.removes = set(self.removes)
        return clone


# Both devices start from the same synced state.
origin = OrSet("s")
origin.add("eggs")
origin.add("milk")
print("both start with:", origin.value())

alice = origin.copy_as("a")
bob = origin.copy_as("b")

# Offline, at the same time, neither seeing the other.
alice.remove("milk")
alice.add("bread")
bob.remove("eggs")
bob.add("milk")          # a NEW add, with a new tag

print("alice offline has:", alice.value())
print("bob offline has:  ", bob.value())

merged = alice.merge(bob)
print("after syncing:    ", merged.value())
print()

# The naive alternative: whole-document last-writer-wins.
print("last-writer-wins would keep one device's list and discard the other:")
print("  if alice wrote last:", alice.value())
print("  if bob wrote last:  ", bob.value())
print()

# Order of merging must not matter. That is the property the whole family is named for.
print("merge is order-independent:", alice.merge(bob).value() == bob.merge(alice).value())
print("merging twice changes nothing:", merged.merge(bob).value() == merged.value())
print("merging with itself changes nothing:", merged.merge(merged).value() == merged.value())

both start with: ['eggs', 'milk']
alice offline has: ['bread', 'eggs']
bob offline has:   ['milk']
after syncing:     ['bread', 'milk']

last-writer-wins would keep one device's list and discard the other:
  if alice wrote last: ['bread', 'eggs']
  if bob wrote last:   ['milk']

merge is order-independent: True
merging twice changes nothing: True
merging with itself changes nothing: True

Neither device was holding bread, milk. It is nevertheless the right answer, and it is the union of what the two people actually intended: Alice wanted bread, Bob wanted milk, and eggs was removed by someone and re-added by no one.

Milk survives Alice’s removal because her removal never saw Bob’s addition. Every add creates a unique tag. A remove deletes the tags that replica can currently see — Alice deleted the tag from the original shared state. Bob’s re-add produced a different tag, one Alice’s remove could not have touched. After the merge that tag is still live, so milk is in the set.

That is causality doing the work, not time. Nowhere in the merge does anything ask which edit happened later, and there is no clock to disagree about — which matters, because clocks on separate devices genuinely do disagree, and a merge that depends on them is a merge that depends on a lie.

Why the three laws at the bottom matter

They look like formality and they are the entire operational argument.

• Order-independent. Alice can sync with Bob or Bob with Alice; same answer. So devices can reach each other in any order.
• Repeatable. Merging the same update twice changes nothing, so a message can be delivered twice, which unreliable networks do constantly.
• Self-stable. A device can merge its own state without damage, so recovery and replay are safe.

Together these mean sync needs no coordination at all. No leader, no locks, no ordering guarantee from the network — only that every update eventually reaches every device, in any order, possibly more than once. That is a much weaker requirement than a database transaction, and it is why this approach works over flaky mobile connections and peer-to-peer links where consensus protocols struggle.

What it costs

The tags. Every addition stores a unique tag forever, and removals store the tags they deleted, so the metadata grows with the history rather than with the current contents. A list of ten items edited for a year is far bigger than a list of ten items. Real implementations spend considerable effort on compaction, and it is the main practical objection to CRDTs.

There is also no such thing as the correct merge in general — only a defined one. This set is add-wins: a concurrent add and remove keeps the item. A remove-wins variant is equally consistent and drops it. Neither is more correct; they encode different product decisions, and choosing between them is a design question rather than a technical one.

What this page simplifies

• One data type. An observed-remove set. Real applications need lists with ordering, text with cursors, counters and maps, and text in particular is substantially harder — concurrent insertions at the same position need a total order nobody agreed on in advance.
• Tags never compacted. Production implementations use version vectors and periodic compaction to stop metadata growing without bound. This one keeps everything, which is what makes the mechanism visible.
• No network. Delivery is assumed. CRDTs guarantee that devices which have seen the same updates agree; getting the updates there is a separate problem with its own failure modes.
• Add-wins is a choice. Stated above and worth repeating, because it is often presented as the behaviour rather than as one of two defensible ones.