Conflict Resolution Strategies
The Conflict Problem
Section titled “The Conflict Problem”In distributed systems, conflicts happen when multiple nodes update the same data simultaneously without coordination.
Strategy 1: Last-Write-Wins (LWW)
Section titled “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
Section titled “How LWW Works”Key Characteristic: Uses timestamps to determine the winner. The write with the latest timestamp wins.
LWW Example: Document Editing
Section titled “LWW Example: Document Editing”Problems with LWW
Section titled “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 |
Strategy 2: Vector Clocks
Section titled “Strategy 2: Vector Clocks”Vector clocks track causal relationships between events. They help detect conflicts and preserve logical ordering.
How Vector Clocks Work
Section titled “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
Section titled “Vector Clock Example: Chat Messages”Key Insight: Vector clocks detect concurrent events (conflicts) vs causally related events (ordered).
Vector Clock Comparison
Section titled “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)
Section titled “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
Section titled “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
Section titled “CRDT Types”Type 1: Operation-Based CRDTs (op-based)
Section titled “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)
Section titled “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
Section titled “CRDT Examples”Example 1: Counter (PN-Counter)
Section titled “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)
Section titled “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)
Section titled “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
Section titled “LLD ↔ HLD Connection”How conflict resolution affects your class design:
Last-Write-Wins Implementation
Section titled “Last-Write-Wins Implementation”1from datetime import datetime2from typing import Optional3
4class LWWRegister:5 def __init__(self, value=None):6 self.value = value7 self.timestamp: Optional[datetime] = None8
9 def write(self, value):10 self.value = value11 self.timestamp = datetime.now()12
13 def merge(self, other: 'LWWRegister') -> 'LWWRegister':14 # Last write wins15 if other.timestamp and (not self.timestamp or other.timestamp > self.timestamp):16 return LWWRegister(other.value, other.timestamp)17 return LWWRegister(self.value, self.timestamp)1import java.time.LocalDateTime;2
3public class LWWRegister {4 private Object value;5 private LocalDateTime timestamp;6
7 public void write(Object value) {8 this.value = value;9 this.timestamp = LocalDateTime.now();10 }11
12 public LWWRegister merge(LWWRegister other) {13 // Last write wins14 if (other.timestamp != null &&15 (timestamp == null || other.timestamp.isAfter(timestamp))) {16 return new LWWRegister(other.value, other.timestamp);17 }18 return new LWWRegister(value, timestamp);19 }20}Vector Clock Implementation
Section titled “Vector Clock Implementation”1from typing import Dict, List2
3class VectorClock:4 def __init__(self, node_id: int, num_nodes: int):5 self.node_id = node_id6 self.clock = [0] * num_nodes7
8 def tick(self):9 # Increment own timestamp10 self.clock[self.node_id] += 111
12 def update(self, other: 'VectorClock'):13 # Merge: element-wise maximum14 for i in range(len(self.clock)):15 self.clock[i] = max(self.clock[i], other.clock[i])16
17 def happened_before(self, other: 'VectorClock') -> bool:18 # Check if self happened before other19 all_le = all(self.clock[i] <= other.clock[i] for i in range(len(self.clock)))20 any_lt = any(self.clock[i] < other.clock[i] for i in range(len(self.clock)))21 return all_le and any_lt22
23 def concurrent(self, other: 'VectorClock') -> bool:24 # Check if concurrent (conflict)25 return not self.happened_before(other) and not other.happened_before(self)1import java.util.*;2
3public class VectorClock {4 private int nodeId;5 private int[] clock;6
7 public VectorClock(int nodeId, int numNodes) {8 this.nodeId = nodeId;9 this.clock = new int[numNodes];10 }11
12 public void tick() {13 // Increment own timestamp14 clock[nodeId]++;15 }16
17 public void update(VectorClock other) {18 // Merge: element-wise maximum19 for (int i = 0; i < clock.length; i++) {20 clock[i] = Math.max(clock[i], other.clock[i]);21 }22 }23
24 public boolean happenedBefore(VectorClock other) {25 // Check if self happened before other26 boolean allLe = true;27 boolean anyLt = false;28 for (int i = 0; i < clock.length; i++) {29 if (clock[i] > other.clock[i]) allLe = false;30 if (clock[i] < other.clock[i]) anyLt = true;31 }32 return allLe && anyLt;33 }34
35 public boolean concurrent(VectorClock other) {36 // Check if concurrent (conflict)37 return !happenedBefore(other) && !other.happenedBefore(this);38 }39}CRDT Implementation (G-Set)
Section titled “CRDT Implementation (G-Set)”1from typing import Set2
3class GSet:4 """Grow-Only Set CRDT - only allows additions"""5 def __init__(self):6 self.elements: Set = set()7
8 def add(self, element):9 # Only addition allowed10 self.elements.add(element)11
12 def merge(self, other: 'GSet') -> 'GSet':13 # Merge: union of sets (commutative, associative)14 merged = GSet()15 merged.elements = self.elements.union(other.elements)16 return merged17
18 def contains(self, element) -> bool:19 return element in self.elements1import java.util.*;2
3public class GSet {4 // Grow-Only Set CRDT - only allows additions5 private Set<Object> elements = new HashSet<>();6
7 public void add(Object element) {8 // Only addition allowed9 elements.add(element);10 }11
12 public GSet merge(GSet other) {13 // Merge: union of sets (commutative, associative)14 GSet merged = new GSet();15 merged.elements = new HashSet<>(elements);16 merged.elements.addAll(other.elements);17 return merged;18 }19
20 public boolean contains(Object element) {21 return elements.contains(element);22 }23}Choosing a Strategy
Section titled “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
Section titled “Key Takeaways”What’s Next?
Section titled “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.