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

Vector Clock Implementation

CRDT Implementation (G-Set)

---

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?