Skip to content
sysgeeks

Conflict resolution and convergence

When replicas accept concurrent changes, a deterministic rule must merge them so every replica ends in the same state without losing intent.

Concurrency

Start the lessonExplain it in your own words

Learn it

0 of 1 checks done

  1. Two people type into the same sentence at once; a phone edits a note offline while a laptop edits it online. Both changes were made against the same starting state and both are legitimate. Applied naively one after the other, the text can be garbled or one change silently dropped.

    A convergent merge rule makes every replica end in the same state.

  2. Three approaches:

    • Last writer wins (LWW): keep the change with the latest timestamp or version. Simple and convergent, but it discards the other change. Fine for a profile photo; wrong for a shared paragraph.
    • Operational transformation (OT): clients send operations tagged with the revision they were based on. A central sequencer transforms each against the ops it missed ("3 characters were inserted before position 12, so this is now 15"), then broadcasts it.
    • CRDTs: operations commute: any order gives the same result. Each character gets a stable identity, so "insert after (alice, 41)" means the same everywhere. No central authority is needed, which suits offline editing; the cost is metadata.

  3. Check

    Text is "abc". Alice inserts "X" at position 0; concurrently Bob deletes position 2 ("c"). With OT, after Alice's insert is applied first, what does Bob's delete become?

Quick reference

The same ideas, condensed for revision.

How it goes wrong

LWW on rich content
One user's paragraph silently disappears.
Non-convergence
A transformation bug or missed operation leaves replicas permanently different; detect with periodic checksums.
Unbounded metadata
CRDT tombstones accumulate for documents with long histories.

Instead, consider

Locking (one editor at a time)
Concurrent editing is rare, and simplicity and predictability matter more than fluid collaboration.
Manual merge (git-style)
Changes are large and infrequent, and users can review conflicts.

In practice

ShareDB, ot.js
OT with a central server.
Yjs, Automerge
Sequence and map CRDTs with sync protocols.
LWW registers
Per-field last-writer-wins, common in mobile sync products.

It assumes

  • Every replica eventually receives every operation (delivery is reliable, possibly duplicated).
  • Operations are applied idempotently. Duplicates are detected by operation ID.
  • For OT: a single authority orders operations per document.

Explain it in your own words

Write at least 60 characters (0 so far). Write it as you would say it in a design review. You will compare it against the points a strong answer makes.

Where you practise it

Further reading

Engineers describing it in systems they run.

Related concepts

  • Ordering

    There is no global 'now' in a distributed system. Order exists only where something assigns it, so decide which order you need and who assigns it.

  • Append-only logs

    Recording changes as an ordered, immutable sequence of facts, from which current state, history and replicas can be derived.

  • Idempotency

    Designing an operation so that performing it twice has the same effect as performing it once, which is what makes retries safe.

  • Replication

    Keeping copies of data on several machines for durability, read capacity and locality, and living with copies that briefly disagree.