Conflict Resolution

Conflicts are inevitable in multi-leader and leaderless replication scenarios—where two nodes write to the same key simultaneously. From the blunt "Last-Write-Wins" approach to tracking causality with version vectors, and finally to CRDTs using mathematical properties (associativity, commutativity, idempotency) to guarantee automatic merging, the stronger the conflict resolution scheme, the higher the cost.

The cost of multi-leader and leaderless replication is that conflicts are inevitable—two nodes receive different writes for the same key simultaneously, and their order cannot be determined via a happens-before relationship.

Last-Write-Wins (LWW)

Decides based on timestamps: the latest timestamp wins, and the older value is discarded. It is simple and efficient but may result in data loss:

Node A: write(x="Alice")  ts=1000
Node B: write(x="Bob")    ts=1001
→ "Bob" wins, "Alice" is overwritten
If these two writes are concurrent (no causal dependency), LWW discards "Alice"—resulting in data loss

LWW is the default strategy in Cassandra, and optional in Riak. The cost is "potential data loss"—which is unacceptable for counters (e.g., like counts).

Version Vectors

Instead of relying on physical time, version vectors use logical clocks from each node to determine happens-before relationships (see 01-02). When version vectors are incomparable, they are marked as concurrent conflicts and handed off to the application layer or an automatic merge process.

Dynamo's approach: read operations return all incomparable versions (siblings), and the client must merge them itself (e.g., merging shopping carts: a user adds different items on different devices simultaneously → the client displays the union of both). If the client does not merge and writes directly, the server will also store multiple siblings.

CRDT (Conflict-free Replicated Data Types)

Mathematically guarantees that concurrent operations are commutative—ensuring automatic convergence without requiring the application layer to handle conflicts.

G-Counter (Grow-only Counter)

Each node maintains an independent counter[N]:
  node_i's Increment(): counter[i] += 1
  Value = sum(counter[0..N])   ← Always correct total (since it only increases, no conflicts)

merge(self, other): for each i: counter[i] = max(self[i], other[i])
→ During merge, take the maximum value for each node (since increments are local, other nodes might not have received the latest value)

PN-Counter (Positive-Negative Counter)

Supports both increment and decrement operations:

Each node maintains two G-Counters: P[i] (positive) and N[i] (negative)
  Increment(): P[i] += 1
  Decrement(): N[i] += 1
  Value = sum(P[0..N]) - sum(N[0..N])

OR-Set (Observed-Remove Set)

A set supporting add and remove operations:

Assign a unique tag (e.g., UUID) to each element when added
  add(e): generate tag t; S = S ∪ {(e, t)}
  remove(e): for all tags of e in S, record them in tombstones
  Value = {e | (e,t) in S and t is not in tombstones}

merge(self, other): S = self.S ∪ other.S (set union), tombstones = self.T ∪ other.T
→ As long as a tag is not marked as "removed", the element exists
→ Concurrent add(e) and remove(e): add has tag t, remove records tombstones containing t → result is correct

Application Selection

References

• Paper: "A Comprehensive Study of Convergent and Commutative Replicated Data Types" (Shapiro et al, 2011)
• Actual Implementations: github.com/automerge/automerge, docs.yjs.dev

Keywords: LWW, version vector, CRDT, G-Counter, PN-Counter, OR-Set, causal consistency, concurrent writes