The peer-to-peer sync protocol: gossip, anti-entropy, and delta exchange

The problem: convergence with nobody in charge

When every device holds a full copy of the shared memory and any of them can accept writes, you need a way for those copies to agree without a central server to funnel through. The naive approach — periodically have each peer send its whole corpus to every other peer — converges, but it costs O(state) bandwidth per round and gets worse the more history you accumulate. The real protocol design problem is: how do two replicas converge while transmitting only what one of them is missing?

The answer comes in two cooperating layers. Gossip spreads new writes quickly and cheaply. Anti-entropy runs underneath as a completeness guarantee, periodically proving two peers hold the same data and repairing them when they don’t. Neither needs a coordinator, and both tolerate the network being unreliable.

Gossip: epidemic dissemination

Gossip protocols borrow their math from epidemiology. When a node has news — a new record — it doesn’t broadcast to everyone. It picks a small random set of peers each round and tells them; they tell their peers; and so on. An update reaches the whole network in a number of rounds that grows only logarithmically with the number of peers, and it does so with no single node bearing the fan-out cost. This is epidemic dissemination, and it is robust precisely because it is redundant: there is no critical path, so losing any node just means the news takes another route.

Gossip comes in three modes, distinguished by who initiates and what flows:

• Push — a node with new data offers it to a peer. Fast at spreading a fresh write, but wasteful late in a round when most peers already have it.
• Pull — a node asks a peer “what’s new?” Efficient at finishing dissemination, when few updates remain.
• Push-pull — both directions in one exchange. This is the usual default because it combines the early speed of push with the tail efficiency of pull.

Anti-entropy: proving and repairing divergence

Gossip is best-effort. Messages drop, nodes go offline, partitions form — so some replicas will silently fall behind. Anti-entropy is the reconciliation pass that closes the gap: two peers compare summaries of their entire state and exchange whatever differs. Run often enough, it guarantees eventual consistency no matter what the gossip layer lost.

The expensive way to do anti-entropy is to compare full state. The cheap way is to compare a Merkle index. Each peer maintains a tree where leaves hash individual records (or small ranges) and every parent hashes its children. Two peers reconcile by comparing root hashes: if the roots match, the entire datasets are identical and nothing needs to be sent. If they differ, the peers descend, comparing child hashes and pruning every subtree whose hash already agrees. They only ever transmit the leaves under the branches that actually diverge. This Merkle reconciliation turns full-corpus comparison into a logarithmic set reconciliation that discovers the diff and ships only the missing records. HiveMind uses exactly this — a Merkle index to find differences efficiently — so a sync moves deltas, not the whole corpus. (The same tree structure underpins tamper-evident history; see the Merkle DAG provenance deep-dive.)

The payload: delta-state CRDTs

Finding the diff is half the job; the other half is making the exchange safe to apply in any order. The records on the wire are delta-state CRDTs — small fragments of conflict-free replicated state. Because CRDT merge is commutative, associative, and idempotent, a peer can apply incoming deltas regardless of arrival order, duplication, or how many partitions they crossed to get there. That is what lets gossip be lossy and anti-entropy be retried freely: re-delivering a delta is harmless. HiveMind’s record is append-mostly, which keeps the merge a clean monotone union and makes the Merkle ranges stable. The full treatment is in the CRDTs for agent state deep-dive.

Churn, partitions, and the transport

Devices join, leave, and reconnect constantly — that’s churn — and the protocol is built to not care. No write waits on any specific peer, so a partition just means each side keeps appending and gossiping locally; when the link returns, one anti-entropy round compares Merkle roots and heals the split in both directions. The peers reach each other over a private encrypted mesh rather than a public relay (see the WireGuard mesh and NAT traversal deep-dive), which is what keeps P2P replication working across home networks without your data ever transiting a server.

Why sync is what makes delegation observable

The plain-English twin of this piece is simple: you can’t delegate to what you can’t see. Sync is the mechanism that makes shared state visible everywhere. Because anti-entropy proves what each replica holds, you can ask any device what it knows and trust the answer — convergence isn’t hoped for, it’s demonstrated by a matching Merkle root. An agent acting on one machine writes into a memory that provably reaches every other machine, and you can look in from any of them. That is the difference between handing work to a black box and delegating to something you can observe.

Frequently asked

Related