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

💡 Tip: Click dropdown to switch between languages

Python

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);
    }
}

TypeScript

Last-Write-Wins

class LWWRegister {
    private value: any;
    private timestamp: Date | null = null;

    write(value: any): void {
        this.value = value;
        this.timestamp = new Date();
    }

    merge(other: LWWRegister): LWWRegister {
        // Last write wins
        if (other.timestamp && (!this.timestamp || other.timestamp > this.timestamp)) {
            const merged = new LWWRegister();
            merged.value = other.value;
            merged.timestamp = other.timestamp;
            return merged;
        }
        const merged = new LWWRegister();
        merged.value = this.value;
        merged.timestamp = this.timestamp;
        return merged;
    }
}

C++

Last-Write-Wins

#include <chrono>
#include <optional>
#include <string>

class LWWRegister {
private:
    std::string value;
    std::optional<std::chrono::system_clock::time_point> timestamp;

public:
    void write(const std::string& val) {
        value = val;
        timestamp = std::chrono::system_clock::now();
    }

    LWWRegister merge(const LWWRegister& other) const {
        // Last write wins
        if (other.timestamp.has_value() &&
            (!timestamp.has_value() || other.timestamp.value() > timestamp.value())) {
            LWWRegister merged;
            merged.value = other.value;
            merged.timestamp = other.timestamp;
            return merged;
        }
        LWWRegister merged;
        merged.value = this->value;
        merged.timestamp = this->timestamp;
        return merged;
    }
};

C#

Last-Write-Wins

using System;

public class LWWRegister {
    private object value;
    private DateTime? timestamp;

    public void Write(object val) {
        value = val;
        timestamp = DateTime.UtcNow;
    }

    public LWWRegister Merge(LWWRegister other) {
        // Last write wins
        if (other.timestamp.HasValue &&
            (!timestamp.HasValue || other.timestamp.Value > timestamp.Value)) {
            return new LWWRegister {
                value = other.value,
                timestamp = other.timestamp
            };
        }
        return new LWWRegister {
            value = this.value,
            timestamp = this.timestamp
        };
    }
}

Vector Clock Implementation

💡 Tip: Click dropdown to switch between languages

Python

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);
    }
}

TypeScript

Vector Clock

class VectorClock {
    private nodeId: number;
    private clock: number[];

    constructor(nodeId: number, numNodes: number) {
        this.nodeId = nodeId;
        this.clock = new Array(numNodes).fill(0);
    }

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

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

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

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

C++

Vector Clock

#include <vector>
#include <algorithm>

class VectorClock {
private:
    int nodeId;
    std::vector<int> clock;

public:
    VectorClock(int nodeId, int numNodes) : nodeId(nodeId), clock(numNodes, 0) {}

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

    void update(const VectorClock& other) {
        // Merge: element-wise maximum
        for (size_t i = 0; i < clock.size(); i++) {
            clock[i] = std::max(clock[i], other.clock[i]);
        }
    }

    bool happenedBefore(const VectorClock& other) const {
        // Check if self happened before other
        bool allLe = true;
        bool anyLt = false;
        for (size_t i = 0; i < clock.size(); i++) {
            if (clock[i] > other.clock[i]) allLe = false;
            if (clock[i] < other.clock[i]) anyLt = true;
        }
        return allLe && anyLt;
    }

    bool concurrent(const VectorClock& other) const {
        // Check if concurrent (conflict)
        return !happenedBefore(other) && !other.happenedBefore(*this);
    }
};

C#

Vector Clock

using System;
using System.Linq;

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 bool HappenedBefore(VectorClock other) {
        // Check if self happened before other
        bool allLe = true;
        bool 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 bool Concurrent(VectorClock other) {
        // Check if concurrent (conflict)
        return !HappenedBefore(other) && !other.HappenedBefore(this);
    }
}

CRDT Implementation (G-Set)

💡 Tip: Click dropdown to switch between languages

Python

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);
    }
}

TypeScript

G-Set CRDT

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

    add(element: any): void {
        // Only addition allowed
        this.elements.add(element);
    }

    merge(other: GSet): GSet {
        // Merge: union of sets (commutative, associative)
        const merged = new GSet();
        merged.elements = new Set([...this.elements, ...other.elements]);
        return merged;
    }

    contains(element: any): boolean {
        return this.elements.has(element);
    }
}

C++

G-Set CRDT

#include <unordered_set>
#include <string>

class GSet {
    // Grow-Only Set CRDT - only allows additions
private:
    std::unordered_set<std::string> elements;

public:
    void add(const std::string& element) {
        // Only addition allowed
        elements.insert(element);
    }

    GSet merge(const GSet& other) const {
        // Merge: union of sets (commutative, associative)
        GSet merged;
        merged.elements = this->elements;
        merged.elements.insert(other.elements.begin(), other.elements.end());
        return merged;
    }

    bool contains(const std::string& element) const {
        return elements.find(element) != elements.end();
    }
};

C#

G-Set CRDT

using System;
using System.Collections.Generic;
using System.Linq;

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

    public void Add(object element) {
        // Only addition allowed
        elements.Add(element);
    }

    public GSet Merge(GSet other) {
        // Merge: union of sets (commutative, associative)
        var merged = new GSet();
        merged.elements = new HashSet<object>(elements);
        foreach (var element in other.elements) {
            merged.elements.Add(element);
        }
        return merged;
    }

    public bool 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

---

Real-World Examples

Example 1: Redis Cache (Last-Write-Wins)

Company: Twitter, GitHub, Stack Overflow

Scenario: Caching user session data, API responses, and frequently accessed data. Multiple cache servers update the same key simultaneously.

Implementation: Uses Last-Write-Wins (LWW) strategy:

Why LWW? Cache data is non-critical and can be regenerated. Simplicity and performance matter more than preserving all writes.

Real-World Impact:

• Twitter: Uses Redis with LWW for caching tweet metadata
• Performance: Sub-millisecond cache updates
• Data Loss: Acceptable since cache can be repopulated from database

---

Example 2: Slack/Discord Chat Messages (Vector Clocks)

Company: Slack, Discord, Microsoft Teams

Scenario: Chat messages must be delivered in causal order. If User A sends a message, and User B replies, the reply must appear after the original message, even if messages arrive out of order.

Implementation: Uses Vector Clocks to track causal relationships:

Why Vector Clocks? Chat applications need to preserve causality (replies after original messages) and detect concurrent edits. Users expect messages in logical order.

Real-World Impact:

• Slack: Uses vector clocks for message ordering across distributed servers
• Reliability: 99.9% correct message ordering even during network partitions
• User Experience: Messages appear in logical order, not arrival order

---

Example 3: Google Docs Collaborative Editing (CRDTs)

Company: Google, Notion, Figma

Scenario: Multiple users edit the same document simultaneously. Each character insertion/deletion must be preserved, and all users must see the same final document.

Implementation: Uses CRDTs (Operation-Based) for text editing:

Why CRDTs? Collaborative editing requires automatic conflict resolution. CRDTs ensure all replicas converge to the same state without manual conflict resolution.

Real-World Impact:

• Google Docs: Uses CRDTs (specifically, Operational Transformation) for collaborative editing
• Scalability: Supports 50+ simultaneous editors on the same document
• Consistency: All users see the same document state within seconds

---

Example 4: DynamoDB Conflict Resolution (Last-Write-Wins with Vector Clocks)

Company: Amazon DynamoDB

Scenario: Key-value store where multiple clients update the same key. System needs to detect conflicts and resolve them.

Implementation: Uses LWW-Register CRDT with vector clocks for conflict detection:

Why Hybrid Approach? DynamoDB uses vector clocks to detect conflicts, then applies LWW for resolution. This provides conflict detection (vector clocks) with simple resolution (LWW).

Real-World Impact:

• Amazon: DynamoDB handles millions of concurrent writes
• Conflict Rate: <0.01% of writes result in conflicts
• Performance: Sub-10ms conflict resolution latency

---

Example 5: Riak Distributed Database (CRDTs)

Company: Riak (Basho Technologies)

Scenario: Distributed key-value database where multiple nodes update the same key independently. System must converge to consistent state.

Implementation: Uses State-Based CRDTs (G-Set, PN-Counter, etc.):

Why State-Based CRDTs? Riak prioritizes automatic convergence and conflict-free replication. CRDTs ensure all nodes eventually see the same state without manual intervention.

Real-World Impact:

• Riak: Used by companies like GitHub, Comcast for distributed storage
• Convergence: All replicas converge within seconds of network healing
• Reliability: 99.99% data consistency guarantee

---

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?