Conflict Resolution and CRDTs

Introduction

Have you ever…

• Edited the same Google Doc paragraph with a teammate at the same time?

• Left an Apple Notes comment while offline, then seen it appear later without errors?

• Changed your smart light’s color via phone while someone else did it from a wall switch?

If so, you’ve witnessed conflict resolution in action—without ever realizing the complex dance happening under the hood. This blog will teach you:

1. What conflicts and convergence really mean, with simple examples.

2. Why local‑first and offline‑first matter.

3. Naïve fixes like Last‑Write‑Wins (LWW) and why they fail.

4. Operational Transformation (OT)—the early industry standard.

5. CRDTs—Conflict‑Free Replicated Data Types—and how they work (with math & pseudocode).

6. Real‑world CRDT applications beyond editors, including CRDT databases.

Let’s start at the beginning.

1. Conflict & Convergence

1.1 What Is a Conflict?

A conflict occurs when two actors (users or devices) make different updates to the same piece of data at the same time, without knowledge of each other’s change.

Example: Shared Shopping List

1. Alice and Bob both have the same list on their phones.

2. Alice goes offline and deletes “milk.”

3. Bob (also offline) adds “eggs.”

4. Both come online simultaneously.

Question: What should the merged list show? Both “eggs” and “no milk,” or only one of these?

A robust system must reconcile both edits—preserving each user’s intention.

1.2 What Is Convergence?

Convergence means all replicas (copies) of the data end up in the same state, regardless of the order or timing of updates.

• If Alice’s device eventually sees the same list as Bob’s device, they have converged.

• Convergence is critical: without it, users get “split‑brain,” seeing different data.

2. Local‑First & Offline‑First: Why We Can’t Always Go Online

2.1 Local‑First

A local‑first app writes changes immediately to your local device, then syncs to others. This gives instant feedback and zero perceived lag.

2.2 Offline‑First

An offline‑first app continues to work when you lose connectivity—reads and writes still work locally.

Example: Note‑Taking on a Plane

• You highlight a sentence in Apple Notes at 35,000 ft (no Wi‑Fi).

• Later, you add a bullet point.

• Upon landing, your device reconnects and syncs—all your edits appear on your other devices without conflict.

If your notes app used a naïve strategy (e.g., require online write), you’d be stuck midflight when you are disconnected from internet.

3. Naïve Conflict Resolution: Last‑Write‑Wins (LWW)

3.1 How LWW Works

• Each update carries a timestamp.

• When two updates conflict, the one with the later timestamp “wins.”

Pseudocode

function mergeLWW(localValue, localTime, remoteValue, remoteTime):
    if localTime >= remoteTime:
        return localValue, localTime
    else:
        return remoteValue, remoteTime

3.2 Why LWW Often Fails

• Clock skew: Devices’ clocks aren’t perfectly synchronized.

• Data loss: Losing valid updates just because they arrived “late.”

• User confusion: Edits vanish with no warning.

Example Failure: Alice sets thermostat to 20 °C at 10:00:00. Bob sets it to 22 °C at 10:00:00.500 on a clock 1 second fast. Bob’s change “wins”—Alice’s preference is lost.

4. Operational Transformation (OT): The Early Hero

4.1 OT in a Nutshell

• Represent each edit as an operation (e.g., insert “x” at position 5).

• When two ops arrive out of order, transform one against the other so they can both apply.

Simplified Example

• Op A: Insert “A” at index 2

• Op B: Delete character at index 4

If B arrives before A, OT adjusts indexes so that both ops make sense.

Pseudocode Sketch

function transform(op1, op2):
    if op1.pos <= op2.pos and op2.type == 'delete':
        return op1
    else if op1.pos > op2.pos and op2.type == 'delete':
        op1.pos -= 1
    // ...and so on
    return op1

4.2 OT Pros & Cons

• Pros: Works well for text, preserves complex edit intent.

• Cons:

  • Complexity grows quickly with data types.

  • Assumes near‑real‑time connectivity.

  • Hard to support offline‑first without elaborate buffering.

5. CRDTs: Embrace the Conflict, Then Merge

CRDTs are data types that let replicas apply updates in any order and still converge.

5.1 Two Flavors of CRDTs

1. State‑based (CvRDTs):

   • Each replica holds a state (e.g., a set).

   • To sync, you merge states with a deterministic function.

2. Operation‑based (CmRDTs):

   • Each update is an operation broadcast to all replicas.

   • Each replica applies ops in any order; ops are designed to commute.

5.2 Math Behind a Simple CRDT: G‑Counter

A Grow‑Only Counter lets you only increment. Each replica keeps a vector of per‑replica counts.

• Replica i has vector v = [v₁, v₂, …, vₙ]

• Increment at i: v[i] += 1

• Merge two vectors: elementwise maximum:
  merge(v, w) = [max(v_1, w_1),max(v_2, w_2), …,]

• Value is sum of elements: value(v) = sum(v)

Pseudocode

class GCounter:
    constructor(id, replicaCount):
        this.id = id
        this.v = [0] * replicaCount
    increment():
        this.v[this.id] += 1
    merge(other):
        for i in range(replicaCount):
            this.v[i] = max(this.v[i], other.v[i])
    value():
        return sum(this.v)

5.3 Example: Smart Thermostat with PN‑Counter

A PN‑Counter combines two G‑Counters: one for increments (P), one for decrements (N).

• Set to 22 °C → increment P by Δ

• Set to 20 °C → decrement N by Δ

• Current temp = sum(P) – sum(N)

Each device can adjust locally; merging is just two vector maxes.

6. More Powerful CRDTs: Sets & Maps

6.1 OR‑Set (Observed‑Remove Set)

Supports adds and removes without losing elements mistakenly:

• Add “x” tags it with a unique ID.

• Remove “x” records all tag IDs seen so far.

• Merge: union of adds minus union of removes.

Pseudocode Sketch

class ORSet:
    constructor():
        this.adds = {}    // element → set of tagIDs
        this.removes = {} // element → set of tagIDs
    add(x):
        tag = generateUniqueTag()
        this.adds[x].add(tag)
    remove(x):
        this.removes[x].update(this.adds.get(x, {}))
    merge(other):
        for x in other.adds:
            this.adds[x] |= other.adds[x]
        for x in other.removes:
            this.removes[x] |= other.removes[x]
    value():
        return {x | at least one tag in adds[x] not in removes[x]}

7. Real‑World CRDT Use Cases Beyond Editors

7.1 CRDT‑Backed Database: Riak KV

Riak KV exposes CRDT data types (counters, sets, maps) so your app simply reads/writes CRDT objects—no custom merge code.

7.2 Example: Smart Home Device State

Devices (app, wall switch, automation) update a CRDT Map:

{
  desired_temp: LWW-Register(22°C, timestamp),
  mode: LWW-Register('heat', timestamp),
  schedule: OR-Set{('6am', 'heat', tag1), ('10pm','eco',tag2)}
}

Whenever devices reconnect, Riak merges states automatically:

• mode and desired_temp pick the latest timestamp.

• schedule unions all rules minus tombstones.

No lost updates. No manual merge.

8. Bringing It All Together

1. Conflicts & convergence define the problem and goal.

2. Local‑first/offline‑first demands immediate writes and later sync.

3. LWW is simple but unsafe.

4. OT works for text but grows complex and assumes live connectivity.

5. CRDTs guarantee convergence by design—merge state or operations in any order.

6. CRDT databases like Riak and AntidoteDB let you build resilient, always‑available apps with zero merge logic.

Further Reading & Diagrams

• Paper: Shapiro et al., “Conflict‑Free Replicated Data Types,” PDF

Your next step: pick a CRDT library (e.g. Yjs, Automerge, or Riak KV), experiment with a toy app (a shared to‑do list or thermostat), and see these merge rules in action.

Happy building!