Skip to content

Anti-Entropy Reconciliation Exchange

Background reconciliation protocol — instantiates Asynchronous Replica Convergence

A background peer-to-peer exchange in which two replicas compute what each is missing and back-fill both directions until they provably hold the same state.

Anti-Entropy Reconciliation Exchange is the standing background process that guarantees divergent replicas actually meet. Two peers periodically compare their state, compute the symmetric difference — what each holds that the other lacks — and back-fill both directions until they hold the same set, reconciled by version. Its defining feature is the reciprocity and the guarantee behind it: it assumes nothing about whether foreground writes were ever delivered, and instead treats divergence as normal while promising it is bounded in time — given enough rounds, every update reaches every replica. Where a read fixes what it happens to touch and a handoff bridges one node's outage, this is the exhaustive, symmetric sweep that closes every gap, and it is the mechanism the archetype's convergence guarantee ultimately rests on.

Example

A company runs a service-discovery registry — the list of which services live at which addresses — replicated across three datacenters so any region can resolve locally. A partition splits them for half an hour: DC-A registers a batch of new payment workers that DC-B never hears about, while DC-B marks a retired cache fleet as gone, news that never reaches DC-A. Neither is simply "stale" — each learned real things the other missed.

When the link heals, A and B run a reconciliation exchange: each summarizes its state (delegating the which entries differ step to a Merkle-Tree Divergence Scan), they compute the symmetric difference, and then back-fill both ways — A ships B the new payment workers, B ships A the retirements — resolving each entry by its version. Within a round or two all three datacenters carry the identical registry. The exchange's promise is not that any single lookup was fresh during the split, but that, absent new writes, the replicas reconverge within a bounded number of rounds.

How it works

Its distinctive stance is that it never trusts a write arrived. On a cadence, peers select each other — often by gossip — and reconcile: detect the difference (it consumes a Merkle scan, so identical regions cost almost nothing to verify), then exchange the differing items in both directions, combining values by the state's own rule (a CRDT-Like State Merge, or a version-vector comparison to tell newer from concurrent). What makes it a convergence guarantee rather than mere propagation is the reciprocity and repetition: because every pair eventually reconciles fully and symmetrically, the whole set is driven to a common state within a bounded number of rounds. It orchestrates detection, causal ordering, and merge into that guarantee; it implements none of them itself.

Tuning parameters

  • Sync cadence — how often the exchange runs. Frequent rounds tighten the convergence bound and shrink the divergence window, but spend CPU and network even when nothing drifted.
  • Reconciliation direction — one-way push, one-way pull, or full reciprocal exchange. Reciprocal converges fastest and handles the both-sides-have-news case, but doubles the comparison and transfer.
  • Peer selection — full mesh versus gossip / random pairing. Gossip scales to many replicas but converges over more rounds; full mesh is fast but O(n²).
  • Repair scope — sweep the whole keyspace or only ranges flagged as divergent. Targeted repair is cheaper; a full sweep catches drift nothing else noticed.
  • Bandwidth throttle — a cap on reconciliation traffic so a large divergence can't starve live requests.

When it helps, and when it misleads

Its strength is being the backstop that makes "eventually consistent" true: without a symmetric background sweep, a write that missed a replica during a fault stays missing until something else happens to touch that key. Its honest limit is that it is eventual and coarse — it does nothing for a client that needs this read fresh now, and a slow cadence can leave replicas divergent for minutes while the exchange traffic itself is not free. The subtler trap is that the exchange only converges replicas to agreement, not to correctness: reconcile by wall-clock "last write wins" instead of real causal order and the sweep will faithfully propagate a value that silently erased a concurrent update — every replica now agrees on the wrong answer.[1] The discipline is to drive reconciliation from proper causal metadata rather than timestamps, and to size cadence against the divergence window the convergence contract actually promises.

How it implements the components

Anti-Entropy Reconciliation Exchange fills the repair-and-guarantee components — the ones a standing background process can fill:

  • update_propagation_and_repair_contract — it is the repair loop: the reciprocal exchange that detects and back-fills missing or newer updates in both directions until peers match.
  • convergence_contract — its bounded-round guarantee that all replicas eventually reach a common state is the archetype's convergence promise made operational.

It does not find *which keys differ (Merkle-Tree Divergence Scan), decide newer-versus-concurrent (Version-Vector or Dotted-Context Exchange), or combine two values (CRDT-Like State Merge) — it consumes all three and orchestrates them into the guarantee.*

Notes

Three mechanisms here repair divergence at different scopes, and a healthy system runs all three: Read Repair on Access fixes what is read (hot data, read path), Hinted-Handoff Buffer bridges one replica's brief absence (write path), and this exchange is the exhaustive background sweep that eventually reaches everything else — including cold data neither of the others would ever touch.

References

[1] Anti-entropy is a term from epidemic (gossip) protocols for a background process that spreads updates until replicas agree, classically implemented with Merkle-tree comparison so that detecting divergence between large replicas stays cheap. It bounds when replicas converge; it does not by itself decide what they converge to — that depends on the merge rule it is paired with. ↩