Sync

Alice and Bob each have a replica. Now they need to agree. Dialog does this through a remote peer: a peer that both can reach and that stores blocks and cells, such as an S3 bucket, a Cloudflare R2 bucket behind a UCAN service, or a shared folder. The remote peer stores bytes and swaps cells. It does not understand facts, trees or merges. All of that happens on the replicas.

What a branch syncs with is called an upstream: another branch, usually the same branch on a remote peer. An app names a branch’s upstreams, to pull from, to push to, or both, and the repository records them as facts in a small branch of its own. A remote peer is known by its DID and the addresses it can be reached at, which the device keeps as a contact. A pull or a push that names no upstream goes to all of them.

A branch remembers one extra thing per upstream: its sync base, the tree the upstream’s head pointed at the last time the two agreed.

A whole conversation

Here is everything that happens between Alice’s laptop, the remote peer, and Bob’s phone, from Alice’s first push to the moment both replicas hold the same root. Each message is written as what it says:

The rest of the chapter walks through it.

Push

A push moves the remote peer’s head forward to the local one, and only forward.

1. Check. Read the remote peer’s head and check its signature. If it is not the sync base, someone else has pushed since this replica last looked, and the push stops with a refusal: not a fast-forward. The replica must pull first.
2. Find what is new. Compare the local tree with the sync base, skipping every subtree whose hash matches, as described in The Search Tree. What is left are the blocks the remote peer does not have.
3. Upload. Send spilled values and the bytes of new assets, then the new tree nodes, children before parents. A node never arrives before the nodes it points at, so the remote peer never holds a node with a dangling link.
4. Swap the head. Ask the remote peer to set its head cell to the new signed head, if it still holds what step 1 read. If another push slipped in between, the swap fails and nothing points at the uploaded blocks.
5. Record. The new tree becomes the sync base.

On S3 the swap in step 4 is a conditional PUT with If-Match on the cell’s ETag, or If-None-Match: * when there is no head yet.

Pull

A pull brings the remote peer’s changes in. It reads the remote peer’s head, checks the head’s signature, and then asks two questions: has the local replica seen the remote peer’s head, and has the remote peer seen the local head? Each watermark says what its side has seen (see Commits and History), and having seen a head means having seen everything that head had seen. The first question is a lookup in the local watermark. The second needs one row of the remote peer’s watermark, which lives in its tree. When both heads were written by the same writer, the editions answer it with no reads, which is the usual case for a device following its upstream. Otherwise the replica reads that row from the remote peer’s tree, a few blocks. The answers tell the replica which case it is in:

When Bob pulls for the first time, he has no local changes, so he takes Alice’s root as it is. He reads no nodes to do it. The nodes arrive later, on demand, as his queries walk through them (Blocks and Storage).

Merge

When Alice’s push is refused, she pulls and finds that both sides have changes. Her replica has to combine them.

Dialog picks the cheaper direction. It takes the side with fewer changes since the two last agreed, and integrates those changes into the other side’s tree. Here Alice made one commit and Bob made one, so she integrates hers into Bob’s tree. When both sides have more than 8 commits the other has not seen, and they share a sync base, Dialog instead grafts whole subtrees from one tree into the other, which costs less than integrating every change. A grafted subtree can still hold facts the other side removed, so Dialog then lists every removal either side made since the sync base, from the coverage records described in Commits and History, and clears those facts from the merged tree.

Integrating is not blind copying. Every change keeps its temporal information, the version that wrote it, and conflicts are resolved along the way. Unless the two replicas have never seen a single commit from each other’s origins, incoming changes are screened against what the receiving side has seen:

• A fact the receiver has already seen, and no longer holds, stays gone. If Bob had retracted a fact and Alice’s replica still held it, her copy’s version would fall inside Bob’s watermark: Bob saw it, and removed it. It is not brought back. This is how deletes survive a merge without tombstones.
• A removal only removes an entry that matches it exactly, down to the version that wrote it. Alice’s change to the milk’s name removes the name "Oat milk" written at (oA, 0). If the receiver holds a copy of a fact written by some other version, the removal leaves that copy alone.
• A record that superseded something retires what it superseded. Bob’s history record says his done true superseded (oA, 1)’s done false. After the merge, done false is gone on both sides, even on a replica that still held it.

History records are merged before facts, so a removal always lands before an incoming fact could contest the slot it clears.

If the merged tree equals one of the two sides, that side’s head is used as it is. Otherwise the replica makes a merge commit: its parents are both heads, its edition is one more than the larger of theirs, and its watermark covers both. Alice’s merge is (oA, 3).

When both change the same thing

Alice renamed the milk to "Oat milk, 1 L". Bob, without seeing that, renamed it to "Soy milk". A name has one value, so each assertion superseded only the "Oat milk" its writer had seen. Neither saw the other’s value, so the merge keeps both:

A name is meant to have one value, so a reader that asks for it under the pick last sees an election between the two. The fact whose commit had seen more wins: the deeper edition. If the editions are equal, as they are here, the hash of the version decides. Every fact a commit wrote carries the same version, so a whole commit wins or loses together: a reader never sees half of Alice’s edit and half of Bob’s.

The election is a function of the stored facts alone, so every replica elects the same name without talking to anyone. The losing value is not deleted. It stays in the store, and an app that wants to show “edited on two devices” can ask for every value by reading the name under all. It stays even after someone asserts a new name, because an assertion supersedes only the fact a read returned, which is the winner. The loser goes when someone retracts it.

The other picks choose in their own ways, max by the greatest value and top by a ranked list, but always from the stored facts alone, and so the same way on every replica.

After the merge

Alice pushes her merge. This time the remote peer’s head is Bob’s, which is her new sync base, so the push goes through. Bob pulls, sees that Alice’s merge has seen everything he has, and adopts its root without reading a single node. The two replicas now hold the same root, and they agree on every fact.