Conflict Resolution

What "Eventually Converges" Actually Requires

"Eventually consistent" is a promise with preconditions, and most systems that claim it satisfy them only most of the time. Convergence needs delivery to every replica, a merge that is order-independent, and a quiet period in which to finish. Remove any one and replicas diverge permanently.

▶ Run the lab

The question this answers

The question

My system says it is eventually consistent. What has to be true for that to actually happen, and how would I know if it stopped?

The guarantee — the property claimed, and its scope

Replicas converge if and only if three conditions hold: (1) every update eventually reaches every replica, (2) the merge is deterministic, commutative, associative and idempotent, and (3) updates stop for long enough that propagation can catch up. Condition 3 is the one nobody states: convergence is a claim about a *quiescent* system, and a system under continuous write load may never be converged at any instant while still being eventually consistent.

Everything below is bought to hold this sentence. "Strongly consistent" with no scope attached is a slogan, not a guarantee — read what it actually covers, and what it explicitly does not.

What a node knows — observation versus inference

A replica knows its own state and which peers it has recently exchanged with. It does not know whether it is converged — that would require knowing what every other replica holds and that nothing is in flight. "Am I up to date?" is not a locally answerable question, which is why convergence must be measured by an external comparison (Merkle Trees: Finding the Difference Without Reading the Data) rather than reported by a node.

A node knows its own state and the messages that arrived. Everything else is inference from evidence that was already stale. "B has not replied in five seconds" is knowledge; "B is down" is a decision — and usually the bug.

What guarantee?→What does a node know?→How does it work?→What can fail?→How does it fail?→Where is coordination?→What holds under failure?→How does it recover?→How would you know?→What is the simpler thing?
convergenceeventual consistencyanti-entropydivergenceliveness

The three conditions, and how each one fails

"Eventual consistency" is usually taught as a weaker guarantee than strong consistency. It is more useful to teach it as a *conditional* guarantee: it holds when three things are true, and each of them fails in production for reasons that have nothing to do with your merge logic.

Delivery. Every update must eventually reach every replica. Replication streams break, queues drop, a replica is down longer than the retention window, a key is never touched again so nothing carries the repair. This is what Anti-Entropy: Repairing Divergence Nobody Reported exists for — a background process that compares replicas and repairs differences regardless of whether a message was lost. Without it, "eventually" is contingent on the network never having failed, which is not a system you have.

A merge that is a join. Deterministic, commutative, associative, idempotent (Only the Application Knows What the Merge Means). A rule missing any of these can leave two replicas holding different values forever, and the divergence appears only under delivery orders you cannot reproduce.

Quiescence. Convergence is defined over a period with no new updates. Under continuous writes there may be no moment at which all replicas agree — the property is still satisfied (they *would* agree if writes stopped), but "converged" is not a state you can observe on a busy key. This is why measuring convergence means measuring the *rate of repair* and the *age of divergence*, not asking whether the system is currently converged.

Fails whenWhat the operator observesFix
Delivery to every replicaassumptionStream breaks, retention expires, cold key never re-touched, replica down too longTwo replicas disagree indefinitely; refreshing changes the answerAnti-entropy with Merkle comparison, plus read repair
Merge is a joinprotocolRule is not commutative, associative or idempotent; reads a clockRepair runs forever on the same keys and divergence never reaches zeroProperty-test the three laws
QuiescenceprotocolContinuous writes to a hot key; propagation slower than update rateDivergence age grows steadily; replicas never agree even brieflyReduce fan-out, batch, or accept and measure the lag
The three conditions and their production failure modes

How convergence is actually achieved

In practice three mechanisms work together, and a system relying on only the first is fragile in a way that does not show up until an incident.

Replication in the write path. The fast path: a write propagates to peers immediately. Covers the overwhelming majority of updates, and covers none of the cases where a message was lost.

Read repair. When a read touches several replicas and finds them disagreeing, it repairs the stale ones. Cheap and effective — and it only ever repairs keys that are *read*. A key written during a partition and never read again is never repaired by this mechanism, which is the origin of long-lived silent divergence.

Anti-entropy. A background process that compares replicas wholesale and repairs whatever differs, whether or not anyone reads it. Comparing everything is expensive, so implementations compare hashes hierarchically: a Merkle tree over the key range lets two replicas find their differences with a number of exchanges proportional to the number of differing keys rather than the total (Merkle Trees: Finding the Difference Without Reading the Data, Gossip: Epidemic Spread Instead of Everyone Telling Everyone for how the state spreads).

The design conclusion is simple and frequently ignored: read repair alone is not convergence. A system that repairs only on read has a growing tail of cold keys that diverged during some past incident and will stay divergent until something touches them — which may be never, or may be a year later during an audit.

Anti-entropy repairs what replication lost and reads never touchedtypical
Replica AReplica Breplicate k=v2: sent, never arrives — dropped in flightreplicate k=v2dropped — never arrivesMerkle root for range: deliveredMerkle root for rangediffering subtree: delivereddiffering subtreek=v2: deliveredk=v2write k=v2 (write) at t=1write k=v2still holds k=v1 — nobody reads k (read) at t=5still holds k=v1 — nobody reads kanti-entropy: compare range digests (decide) at t=8anti-entropy: compare range digestsk=v2 — converged (recover) at t=12k=v2 — convergedt=1time →t=12
delivereddelayed (dashed, long)duplicated (×2)dropped — stops short, never arriveswritereadrecoverdecide
The replication message was lost and no read ever touched the key, so nothing in the fast path would have repaired it. Convergence here is entirely due to the background process — which is why its absence is invisible right up until it matters.

What breaks convergence permanently

Some failures delay convergence; others prevent it outright. The second group is worth memorising, because they all look like the first group on a dashboard.

A non-commutative or non-associative merge. Two replicas apply the same versions in different orders and reach different results. Repair runs, the values differ again, repair runs again. The signature is anti-entropy repairing the same key set indefinitely with divergence never reaching zero.

A non-idempotent merge. Repair itself becomes a corruption source — every anti-entropy cycle changes the value. Counters that only ever grow are the classic example, and the system looks *more* broken the harder it tries to fix itself.

Premature tombstone GC. A delete is forgotten before every replica has seen it, and a lagging replica reintroduces the deleted value. The two replicas then disagree, repair propagates the resurrection outward, and the delete is permanently undone (Version Vectors: Making the Conflict Visible).

A replica that is down longer than the retention window. It returns holding old state, with no log left to replay. Without a full state transfer it may reintroduce stale values, and if the merge is LWW with clock skew it can even *win* against newer data.

Silent metadata loss. An intermediary strips causal context, so conflicts are misread as supersessions and the repair itself discards data. The metric improves; the data degrades.

Persistent one-way partitions. Asymmetric reachability — A can send to B but not the reverse — defeats naive gossip and produces divergence that survives even though every node reports healthy peers.

HEALTHY (converging):
  divergent_keys after anti-entropy pass:   4,102 -> 380 -> 12 -> 0
  oldest_divergence_age:                    rises during incident, falls after
  repair_rate:                              spikes, then returns to baseline

BROKEN (never converges):
  divergent_keys after anti-entropy pass:   118 -> 121 -> 117 -> 119
  oldest_divergence_age:                    monotonically increasing
  repair_rate:                              constant, non-zero, forever

The second pattern is a merge that is not a join, or a resurrection loop.
More repair capacity will not help; the same keys are being fixed and
re-broken every cycle.
The two signatures, and what separates them

Measuring it, and being honest about what you promise

Because no node can report whether the system is converged, convergence must be measured from outside, by comparison. The good news is that this is straightforward and almost nobody does it.

The measurements that matter: divergent key count after a completed anti-entropy pass (should trend to zero), age of the oldest divergence (the real user-facing number — how stale can a replica be), and repair rate (constant non-zero repair on the same keys is the non-convergence signature). Add an out-of-band consistency checker that samples keys across replicas and compares, because it catches everything the internal mechanisms are blind to.

And be precise in what you promise downstream. "Eventually consistent" without a time bound is not a contract anyone can build on. A usable statement is bounded and conditional: *"replicas converge within N seconds under normal operation; during a partition, divergence persists for the partition duration plus the anti-entropy cycle time; concurrent writes are resolved by [rule]"*. Every clause there is something a consumer needs and a bare "eventually" hides (Session Guarantees: The Underrated Middle Ground for the client-facing guarantees that make eventual consistency usable, Eventual Consistency: If Updates Stop, Replicas Converge for the model itself).

The last honest note: convergence is a liveness property — it says something good eventually happens — and liveness properties cannot be verified by observation, only violated by it. You can never prove your system has converged; you can only detect that it has not. That asymmetry is why the measurement has to be continuous rather than a one-off check.

Key points

  • Convergence requires delivery to every replica, a merge that is a join, and a quiet period — all three, or it does not happen.
  • Quiescence is the unstated condition: under continuous writes there may be no instant at which replicas agree.
  • Read repair only fixes keys that are read. Cold keys diverged during an incident stay diverged without anti-entropy.
  • A merge that is not commutative, associative and idempotent produces permanent divergence, not slow convergence.
  • Premature tombstone GC turns a delete into a resurrection that repair then spreads.
  • No node can report whether the system is converged; it must be measured by external comparison.
  • "Eventually consistent" without a bound is not a contract. State the window, the partition behaviour and the resolution rule.

The chain, answered

Every field here is required, which is why no lesson in this domain can recommend a design without naming what an operator sees when it fails, what survives the partition, what repairs it afterwards, and the simpler thing to consider first.

How it works
  • • A write is applied locally and propagated to peers on the fast path.
  • • Reads that touch multiple replicas detect disagreement and repair the stale ones opportunistically.
  • • A background anti-entropy process compares replicas by hierarchical hashes and repairs differences regardless of read traffic.
  • • Every repair applies the merge function, so order-independence is what makes repeated repair safe.
  • • Given no new writes, repeated repair drives all replicas to the same state, and further repairs become no-ops.
What can fail at the boundary
  • • A replication message is lost and the key is never read again, so nothing triggers a repair.
  • • A replica is offline past the log retention window and returns with no way to catch up incrementally.
  • • The merge is not order-independent, so repair oscillates instead of converging.
  • • Tombstones are collected early and deletes are undone by lagging replicas.
  • • Anti-entropy is disabled or throttled to nothing for cost reasons, leaving read repair as the only mechanism.
  • • Asymmetric network reachability defeats gossip, so a subset of replicas never receives updates despite reporting healthy peers.
How it fails — what an operator sees
  • • Refreshing the page changes the answer: a key is divergent across replicas and the load balancer picks a different one each time. The operator sees an unreproducible bug that follows no user and no request.
  • • Repair that never finishes: divergent-key count after each anti-entropy pass stays flat and non-zero. The operator sees constant repair traffic and no improvement — the merge is not a join.
  • • Deleted data returns: an object is removed, disappears, and reappears after a repair cycle. The operator finds the tombstone GC watermark ahead of the slowest replica.
  • • Divergence discovered by an audit: a reconciliation report months later finds thousands of keys differing between replicas, all dating to one past incident, none of them ever read since.
  • • Stale reads that outlast the incident: divergence age keeps climbing after the network recovered, because anti-entropy was throttled and the backlog exceeds the repair rate.
  • • Post-partition repair storm: healing generates repair traffic that saturates the same links that just recovered, extending the outage. The operator sees recovery causing a second latency spike.
Where coordination is required
  • • Convergence itself requires no agreement — replicas exchange state and merge, never vote.
  • • It does require *communication*, which is a weaker but non-negotiable requirement: a replica nothing ever talks to never converges.
  • • Anti-entropy has a real cost in bandwidth and IO, and the common failure is throttling it until it cannot keep up while continuing to claim eventual consistency.
  • • Tombstone GC is the one place genuine agreement is needed — you may only forget a delete once every replica has recorded it (Anti-Entropy: Repairing Divergence Nobody Reported).
What still holds under failure
  • • During a partition, both sides remain available and divergence grows with partition duration times write rate.
  • • After healing, convergence takes at least one anti-entropy cycle and possibly many, depending on backlog and repair throughput.
  • • A replica offline past retention needs full state transfer, which is far more expensive than incremental catch-up and can itself destabilise a recovering cluster.
  • • If the merge is not a join, healing does not produce convergence — the system settles into permanent, repairing disagreement.
How it recovers
How you would know
  • • Divergent keys remaining after each completed anti-entropy pass — the single most important number, and the one most systems do not emit.
  • • Age of the oldest known divergence, which is the honest answer to "how stale can a read be".
  • • Anti-entropy cycle time and coverage: how long a full pass takes, and what fraction of the keyspace it actually reached.
  • • Repair rate over time; constant non-zero repair on a stable key set is the non-convergence signature.
  • • Tombstone GC watermark versus the slowest replica's progress, which predicts resurrections before they occur.
  • • An independent sampled consistency check, run from outside the system, as ground truth.
When it helps
  • • Any system claiming eventual consistency — this is the checklist that determines whether the claim is true.
  • • After an incident, to decide whether the system has actually recovered or has merely stopped erroring.
  • • When writing a guarantee for downstream consumers, to replace "eventually" with a bounded, conditional statement they can build on.
When it hurts
  • • For single-replica or strongly-consistent data, none of this machinery applies and adding it is cost with no benefit.
  • • Chasing convergence on a continuously hot key is often the wrong goal — the honest answer there is a bound on divergence, not the absence of it.
  • • Aggressive anti-entropy on a large keyspace can consume more resources than the workload; the tuning is real work.
Simpler alternatives

Three conditions, and convergence needs all three

Three conditions, and convergence needs all three
“Eventually consistent” is a conditional promise. Turn any one of these off and the system is still eventually consistent by the definition — and still never agrees.
✓ Condition 1 — Every update eventually reaches every replica
The open links connect all four nodes; 6 messages were delivered.
✓ Condition 2 — The merge is deterministic, commutative, associative and idempotent
The model resolves by version, and ties break on the value — a join. Order of arrival cannot change the outcome.
✓ Condition 3 — Updates stop for long enough that propagation catches up
One write, then quiet. Converged at step 6.
converged
step 6
messages delivered
6
messages dropped
0
groups that disagree
1
step01234567891011121314151617
av1v1v1v1v1v1v1v1v1v1v1v1v1v1v1v1v1v1
bv0v1v1v1v1v1v1v1v1v1v1v1v1v1v1v1v1v1
cv0v0v1v1v1v1v1v1v1v1v1v1v1v1v1v1v1v1
dv0v0v0v0v1v1v1v1v1v1v1v1v1v1v1v1v1v1
Converged
Converged at step 6 after 6 messages. Every node now serves "v1" — but a reader between step 0 and step 6 could observe any of the intermediate values, and nothing in this model told that reader which one it had.
Two things break convergence permanently rather than slowly, and both are quiet. Read repair only fixes keys that are read, so cold keys that diverged during an incident stay diverged until an anti-entropy pass compares them — which is what Merkle trees are for. And premature tombstone collection turns a delete into a resurrection that repair then spreads helpfully to every replica. Note also who can tell you whether the system has converged: nobody. A replica knows its own state and who it last exchanged with; "am I up to date?" is not a locally answerable question, so convergence must be measured by external comparison rather than reported by a node. Which is why "eventually consistent" without a stated window, partition behaviour and resolution rule is not a contract — it is a hope.
assumptionConditions 1 and 3 are demonstrated on a four-node propagation run. Condition 2 is demonstrated by delivering the same two updates in both orders, because a model whose merge is a join cannot exhibit a merge that is not — the divergence shown there is real, not decorative.

What people believe, and what is true

Claim

Eventually consistent means it catches up in a second or two.

Reality

It means there is no bound at all unless the system states one. Cold keys can stay divergent for months if only read repair is running.

Claim

If replication is working, the system converges.

Reality

Replication covers the fast path. Convergence additionally needs repair for what the fast path lost, and a merge that is order-independent.

Claim

More repair capacity fixes divergence.

Reality

Only when divergence is a backlog. If the merge is not a join, more repair means more oscillation on the same keys.

Claim

The system will tell us if replicas disagree.

Reality

No node can know. Disagreement is only visible to something comparing replicas from outside, which is a thing you have to build or enable.

Claim

Once the partition heals, we are consistent again.

Reality

You are consistent one anti-entropy cycle after healing, at best — and not at all if a tombstone was collected or the merge is defective.

Go deeper

Only the levels this lesson can honestly fill — a missing level is a claim nobody had.

Overview

Eventual consistency holds only if every update reaches every replica, the merge does not care about order, and writes pause long enough to catch up. Remove any one and replicas can disagree forever.

Practical

Run anti-entropy, not just read repair, and measure divergent keys after each pass, the age of the oldest divergence, and coverage. Property-test the merge. Keep tombstone GC behind the slowest replica. Promise a bounded window rather than "eventually".

Advanced

Convergence is liveness, so it is unfalsifiable by observation and can only be detected in the breach — which is why the operational stance is continuous comparison rather than a proof. Given a merge that is a join, repeated pairwise exchange drives replicas to the least upper bound of everything delivered, and the only remaining questions are delivery coverage and repair throughput versus write rate. When repair throughput is below the divergence-creation rate, the system is eventually consistent in theory and permanently divergent in practice — the distinction that matters to users and never appears in the guarantee.

Apply it

Build it, then break it
  • 🔧 Build an out-of-band checker that samples keys across replicas and reports divergence count and age. Run it for a week.
  • 🔧 Disable anti-entropy in a test environment, run a partition, and measure how long divergence on unread keys survives.
Reason about this
  • ⚡ A quarterly audit finds 8,000 keys differing between replicas, all last written during an incident nine months ago. Explain how this happened.
  • ⚡ After a partition heals, latency spikes again for twenty minutes. Nothing failed. What is happening?
  • ⚡ A vendor claims "strong eventual consistency". What three questions do you ask?
Interview questions
  • 💬 What are the preconditions for eventual consistency, and which one is usually left unstated?
  • 💬 Your divergent-key count after each anti-entropy pass is flat at about 120. What is wrong, and would more repair capacity help?
  • 💬 How would you measure whether your system is actually converging? Why can a node not tell you?
  • 💬 Write a guarantee for a downstream team that is more useful than "eventually consistent".
← CRDTs: Deterministic Merge, Not Correct Merge