Conflict Resolution Strategies

The Conflict Problem

In distributed systems, conflicts happen when multiple nodes update the same data simultaneously without coordination.

The Challenge

Conflicts are inevitable in distributed systems. When nodes can’t coordinate (due to partitions or performance), they’ll make independent updates. The system must decide: which update wins, or how to merge them?

---

Strategy 1: Last-Write-Wins (LWW)

Last-Write-Wins (LWW) is the simplest conflict resolution strategy: the most recent write (by timestamp) wins.

How LWW Works

Key Characteristic: Uses timestamps to determine the winner. The write with the latest timestamp wins.

LWW Example: Document Editing

Problems with LWW

Problem	Description	Example
Data Loss	Simultaneous writes lose one	User A’s edit is lost
Clock Skew	Wrong timestamp wins	Slow clock makes old write win
No Causal Order	Ignores dependencies	Reply might appear before original message

When to Use LWW

LWW is simple but risky. Use it only when:

• Data loss is acceptable (e.g., cache values)
• Writes are independent (no dependencies)
• You have synchronized clocks

Avoid LWW for critical data, collaborative editing, or when preserving all updates matters.

---

Strategy 2: Vector Clocks

Vector clocks track causal relationships between events. They help detect conflicts and preserve logical ordering.

How Vector Clocks Work

A vector clock is a vector of logical timestamps, one per node. Each node increments its own timestamp when it performs an operation.

Vector Clock Example: Chat Messages

Key Insight: Vector clocks detect concurrent events (conflicts) vs causally related events (ordered).

Vector Clock Comparison

Comparison Algorithm:

• V1 < V2 if all components of V1 ≤ V2 and at least one is less than
• V1 || V2 (concurrent) if neither V1 < V2 nor V2 < V1
• V1 == V2 if all components are equal

---

Strategy 3: CRDTs (Conflict-free Replicated Data Types)

CRDTs (Conflict-free Replicated Data Types) are data structures designed to never conflict. They use mathematical properties to ensure all replicas converge to the same state.

The CRDT Principle

Key Property: CRDTs use commutative and associative operations, so order doesn’t matter. All replicas converge to the same state automatically.

---

CRDT Types

Type 1: Operation-Based CRDTs (op-based)

Operation-based CRDTs replicate operations (e.g., “increment counter”, “add element to set”).

Example: Counter CRDT

• Operations: increment(), decrement()
• Merge: Apply all operations (order doesn’t matter)
• Result: All nodes converge to same count

---

Type 2: State-Based CRDTs (state-based)

State-based CRDTs replicate entire state and merge using a merge function.

Example: Set CRDT (G-Set)

• State: Set of elements
• Merge: Union of sets
• Result: All nodes converge to union of all additions

---

CRDT Examples

Example 1: Counter (PN-Counter)

A PN-Counter (Positive-Negative Counter) tracks increments and decrements separately.

Merge: Element-wise maximum of increments and decrements vectors.

---

Example 2: Set (G-Set, 2P-Set)

G-Set (Grow-Only Set): Only allows additions, never removals.

2P-Set (Two-Phase Set): Tracks additions and removals separately.

---

Example 3: Register (LWW-Register)

LWW-Register uses last-write-wins with timestamps.

Note: LWW-Register is a CRDT but still loses data (same problem as LWW strategy).

---

LLD ↔ HLD Connection

How conflict resolution affects your class design:

Last-Write-Wins Implementation

Python

Last-Write-Wins

from datetime import datetime
from typing import Optional

class LWWRegister:
    def __init__(self, value=None):
        self.value = value
        self.timestamp: Optional[datetime] = None

    def write(self, value):
        self.value = value
        self.timestamp = datetime.now()

    def merge(self, other: 'LWWRegister') -> 'LWWRegister':
        # Last write wins
        if other.timestamp and (not self.timestamp or other.timestamp > self.timestamp):
            return LWWRegister(other.value, other.timestamp)
        return LWWRegister(self.value, self.timestamp)

Java

Last-Write-Wins

import java.time.LocalDateTime;

public class LWWRegister {
    private Object value;
    private LocalDateTime timestamp;

    public void write(Object value) {
        this.value = value;
        this.timestamp = LocalDateTime.now();
    }

    public LWWRegister merge(LWWRegister other) {
        // Last write wins
        if (other.timestamp != null &&
            (timestamp == null || other.timestamp.isAfter(timestamp))) {
            return new LWWRegister(other.value, other.timestamp);
        }
        return new LWWRegister(value, timestamp);
    }
}

Vector Clock Implementation

Python

Vector Clock

from typing import Dict, List

class VectorClock:
    def __init__(self, node_id: int, num_nodes: int):
        self.node_id = node_id
        self.clock = [0] * num_nodes

    def tick(self):
        # Increment own timestamp
        self.clock[self.node_id] += 1

    def update(self, other: 'VectorClock'):
        # Merge: element-wise maximum
        for i in range(len(self.clock)):
            self.clock[i] = max(self.clock[i], other.clock[i])

    def happened_before(self, other: 'VectorClock') -> bool:
        # Check if self happened before other
        all_le = all(self.clock[i] <= other.clock[i] for i in range(len(self.clock)))
        any_lt = any(self.clock[i] < other.clock[i] for i in range(len(self.clock)))
        return all_le and any_lt

    def concurrent(self, other: 'VectorClock') -> bool:
        # Check if concurrent (conflict)
        return not self.happened_before(other) and not other.happened_before(self)

Java

Vector Clock

import java.util.*;

public class VectorClock {
    private int nodeId;
    private int[] clock;

    public VectorClock(int nodeId, int numNodes) {
        this.nodeId = nodeId;
        this.clock = new int[numNodes];
    }

    public void tick() {
        // Increment own timestamp
        clock[nodeId]++;
    }

    public void update(VectorClock other) {
        // Merge: element-wise maximum
        for (int i = 0; i < clock.length; i++) {
            clock[i] = Math.max(clock[i], other.clock[i]);
        }
    }

    public boolean happenedBefore(VectorClock other) {
        // Check if self happened before other
        boolean allLe = true;
        boolean anyLt = false;
        for (int i = 0; i < clock.length; i++) {
            if (clock[i] > other.clock[i]) allLe = false;
            if (clock[i] < other.clock[i]) anyLt = true;
        }
        return allLe && anyLt;
    }

    public boolean concurrent(VectorClock other) {
        // Check if concurrent (conflict)
        return !happenedBefore(other) && !other.happenedBefore(this);
    }
}

CRDT Implementation (G-Set)

Python

G-Set CRDT

from typing import Set

class GSet:
    """Grow-Only Set CRDT - only allows additions"""
    def __init__(self):
        self.elements: Set = set()

    def add(self, element):
        # Only addition allowed
        self.elements.add(element)

    def merge(self, other: 'GSet') -> 'GSet':
        # Merge: union of sets (commutative, associative)
        merged = GSet()
        merged.elements = self.elements.union(other.elements)
        return merged

    def contains(self, element) -> bool:
        return element in self.elements

Java

G-Set CRDT

import java.util.*;

public class GSet {
    // Grow-Only Set CRDT - only allows additions
    private Set<Object> elements = new HashSet<>();

    public void add(Object element) {
        // Only addition allowed
        elements.add(element);
    }

    public GSet merge(GSet other) {
        // Merge: union of sets (commutative, associative)
        GSet merged = new GSet();
        merged.elements = new HashSet<>(elements);
        merged.elements.addAll(other.elements);
        return merged;
    }

    public boolean contains(Object element) {
        return elements.contains(element);
    }
}

---

Choosing a Strategy

Strategy	Pros	Cons	Use Cases
LWW	Simple	Data loss	Cache, non-critical data
Vector Clocks	Detects conflicts, preserves causality	Complex	Chat, comments, collaborative editing
CRDTs	No conflicts, automatic merge	Limited operations	Counters, sets, collaborative editing

---

Key Takeaways

Remember

• Conflicts happen when multiple nodes update simultaneously
• Last-Write-Wins is simple but loses data
• Vector clocks track causality and detect conflicts
• CRDTs use mathematical properties to avoid conflicts
• Operation-based CRDTs replicate operations
• State-based CRDTs replicate state and merge
• LLD implementation: Merge strategies, version vectors, CRDT data structures
• Choose based on requirements: Simple = LWW, Causality = Vector clocks, Automatic = CRDTs

---

What’s Next?

Congratulations! You’ve completed the Consistency & Distributed Transactions section. You now understand:

• Consistency models (strong, eventual, causal)
• CAP theorem (the fundamental trade-off)
• PACELC theorem (adding latency considerations)
• Distributed transactions (2PC, Saga pattern)
• Conflict resolution (LWW, vector clocks, CRDTs)

Next up: Explore how these concepts apply to Database & Storage Systems — Learn about ACID properties, isolation levels, and database scaling.

Practice Exercise

Design a conflict resolution strategy for a collaborative document editor. What CRDT would you use? How would you handle text insertions and deletions? What about formatting changes?