System Design (HLD)Conflict Resolution Strategies

Conflict Resolution Strategies

LevelAdvanced

Duration120 mins

TopicConflict Resolution Strategies

3 / 5

Vector Clocks for Causality

Tracking The Flow of Causality

Last-Write-Wins tells us which value to keep, but not why the values diverged or whether they could have influenced each other. Vector clocks solve a different problem: they tell us whether two operations are causally related or genuinely concurrent.

This distinction matters enormously. If operation B saw the result of operation A before proceeding, then B is not in conflict with A—it supersedes it. But if A and B happened independently, neither knew about the other, they are genuinely concurrent, and we have a real conflict that requires resolution.

Vector clocks give us the tools to make this determination, enabling smarter conflict handling than simple timestamp comparison.

What You Will Learn

By the end of this page, you will understand the mathematical foundation of vector clocks, how to implement and compare them, how they detect true concurrency versus causal ordering, their practical applications in distributed databases, and their limitations in real-world systems.

The Limitation of Scalar Timestamps

Before diving into vector clocks, let's understand why scalar (single-value) timestamps are insufficient for distributed conflict detection.

Lamport timestamps (single counters) guarantee that if A happened before B, then timestamp(A) < timestamp(B). But the converse is not true: if timestamp(A) < timestamp(B), we cannot conclude that A happened before B. The events might be concurrent.

Converting Mermaid diagram...

The Gap in Lamport Clocks:

Relationship	Lamport Guarantee
A → B (A happened before B)	ts(A) < ts(B) ✓
ts(A) < ts(B)	Maybe A → B, maybe concurrent (?)
ts(A) = ts(B)	Concurrent or same event (?)

We need a clock that can definitively answer: Were these events concurrent, or did one causally precede the other?

Vector clocks provide exactly this capability. By tracking the knowledge each node has about other nodes' progress, we can determine causal relationships—or their absence.

Happens-Before Refresher

Event A 'happens before' B (written A → B) if: (1) A and B are on the same node and A occurred first, OR (2) A is a send and B is the corresponding receive, OR (3) there exists an event C where A → C and C → B (transitivity). Events are 'concurrent' (A || B) if neither A → B nor B → A.

Vector Clock Fundamentals

A vector clock is an array of counters, one for each node (or actor) in the distributed system. Each node maintains its own vector clock and updates it according to specific rules.

Structure:

For a system with N nodes, a vector clock is: VC = [c₁, c₂, c₃, ..., cₙ]

Where cᵢ represents the number of events that have occurred at node i, as known by the node holding this vector clock.

Rules:

On local event: Increment your own counter
On send: Include your vector clock with the message
On receive: Update your vector clock to max(yours, received) for each position, then increment your own counter

vector-clock.ts
TypeScript
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
interface VectorClock {
    [nodeId: string]: number;
}
 
/**
 * Vector Clock implementation for distributed causality tracking.
 */
class VectorClockManager {
    private clock: VectorClock;
    private nodeId: string;
    
    constructor(nodeId: string, knownNodes: string[] = []) {
        this.nodeId = nodeId;
        this.clock = {};
        
        // Initialize all known nodes to 0
        for (const node of knownNodes) {
            this.clock[node] = 0;
        }
        this.clock[nodeId] = 0;
    }
    
    /**
     * Increment clock for a local event.
     */
    tick(): VectorClock {
        this.clock[this.nodeId] = (this.clock[this.nodeId] ?? 0) + 1;
        return this.getClock();
    }
    
    /**
     * Prepare clock to send with a message (tick first).
     */
    send(): VectorClock {
        return this.tick();  // Local event: sending
    }
    
    /**
     * Update clock on receiving a message.
     */
    receive(remoteClock: VectorClock): VectorClock {
        // Merge: take component-wise maximum
        const allNodes = new Set([
            ...Object.keys(this.clock),
            ...Object.keys(remoteClock),
        ]);
        
        for (const node of allNodes) {
            const local = this.clock[node] ?? 0;
            const remote = remoteClock[node] ?? 0;
            this.clock[node] = Math.max(local, remote);
        }
        
        // Then increment our own counter (receiving is a local event too)
        this.clock[this.nodeId] = (this.clock[this.nodeId] ?? 0) + 1;
        
        return this.getClock();
    }
    
    getClock(): VectorClock {
        return { ...this.clock };
    }
}
 
// Example: Three-node system
const nodeA = new VectorClockManager('A', ['A', 'B', 'C']);
const nodeB = new VectorClockManager('B', ['A', 'B', 'C']);
const nodeC = new VectorClockManager('C', ['A', 'B', 'C']);
 
// Node A performs a local event
const vc1 = nodeA.tick();
console.log('After A event:', vc1);  // { A: 1, B: 0, C: 0 }
 
// Node A sends to B
const msgToB = nodeA.send();
console.log('A sends:', msgToB);  // { A: 2, B: 0, C: 0 }
 
// Node B receives from A
const vc2 = nodeB.receive(msgToB);
console.log('B after receive:', vc2);  // { A: 2, B: 1, C: 0 }

Intuition:

Each node's vector clock represents its knowledge horizon—what it knows about the progress of all nodes. When Node B receives a message from Node A containing A's vector clock, B learns about all events that A knew about when it sent the message. By taking the maximum, B incorporates A's knowledge into its own.

Comparing Vector Clocks

The power of vector clocks lies in their comparison semantics. Given two vector clocks VC₁ and VC₂, we can determine their causal relationship.

Vector Clock Comparison Rules
Condition	Relationship	Interpretation
VC₁[i] ≤ VC₂[i] for all i, and VC₁ ≠ VC₂	VC₁ < VC₂ (VC₁ happened before VC₂)	Event 1 causally precedes Event 2
VC₁[i] ≥ VC₂[i] for all i, and VC₁ ≠ VC₂	VC₁ > VC₂ (VC₂ happened before VC₁)	Event 2 causally precedes Event 1
VC₁[i] = VC₂[i] for all i	VC₁ = VC₂ (equal)	Same event or identical state
Neither VC₁ ≤ VC₂ nor VC₁ ≥ VC₂	VC₁ \|\| VC₂ (concurrent)	Genuinely concurrent events!

vector-clock-compare.ts
TypeScript
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
interface VectorClock {
    [nodeId: string]: number;
}
 
type VectorComparison = 
    | 'BEFORE'      // VC1 happened before VC2 (VC1 < VC2)
    | 'AFTER'       // VC1 happened after VC2 (VC1 > VC2)
    | 'EQUAL'       // Identical clocks
    | 'CONCURRENT'; // Neither dominates - true conflict!
 
function compareVectorClocks(
    vc1: VectorClock, 
    vc2: VectorClock
): VectorComparison {
    const allNodes = new Set([
        ...Object.keys(vc1),
        ...Object.keys(vc2),
    ]);
    
    let vc1LessOrEqual = true;   // All vc1[i] <= vc2[i]
    let vc2LessOrEqual = true;   // All vc2[i] <= vc1[i]
    let anyDifferent = false;
    
    for (const node of allNodes) {
        const v1 = vc1[node] ?? 0;
        const v2 = vc2[node] ?? 0;
        
        if (v1 > v2) vc1LessOrEqual = false;
        if (v2 > v1) vc2LessOrEqual = false;
        if (v1 !== v2) anyDifferent = true;
    }
    
    if (!anyDifferent) {
        return 'EQUAL';
    }
    
    if (vc1LessOrEqual && !vc2LessOrEqual) {
        return 'BEFORE';  // vc1 < vc2
    }
    
    if (vc2LessOrEqual && !vc1LessOrEqual) {
        return 'AFTER';   // vc1 > vc2
    }
    
    // Neither dominates the other
    return 'CONCURRENT';
}
 
// Examples:
// Causal relationship: e1 happened before e2
const e1: VectorClock = { A: 2, B: 1, C: 0 };
const e2: VectorClock = { A: 3, B: 2, C: 1 };
console.log(compareVectorClocks(e1, e2));  // 'BEFORE'
 
// Concurrent events: neither happened before the other
const e3: VectorClock = { A: 2, B: 1, C: 0 };
const e4: VectorClock = { A: 1, B: 2, C: 0 };
console.log(compareVectorClocks(e3, e4));  // 'CONCURRENT' - True conflict!
 
// e3 has A:2 > A:1, so e3 is not <= e4
// e4 has B:2 > B:1, so e4 is not <= e3
// Neither dominates → CONCURRENT

Why Concurrency Detection Matters

When two operations are concurrent, LWW would pick one and discard the other. But vector clocks reveal that both operations are 'equally valid'—neither knew about the other. This information enables smarter resolution: perhaps both values should be kept as siblings, or merged using application logic, rather than arbitrarily discarding one.

Visual Walkthrough

Let's trace through a detailed example of vector clocks detecting concurrent writes in a three-node system.

Converting Mermaid diagram...

Step-by-Step Analysis:

Time	Event	A's Clock	B's Clock	C's Clock
T1	A writes x=1	[1,0,0]	[0,0,0]	[0,0,0]
T2	A syncs to B	[1,0,0]		[0,0,0]
T3	B receives	[1,0,0]	[1,1,0]	[0,0,0]
T4	B writes x=2	[1,0,0]	[1,2,0]	[0,0,0]
T4'	C writes x=3 (concurrent!)	[1,0,0]	[1,2,0]	[0,0,1]

At T4/T4':

B's clock: [1,2,0] — B knows about A's first event and its own two events
C's clock: [0,0,1] — C only knows about its own event

Comparison:

[1,2,0] vs [0,0,1]
Position A: 1 > 0 → B's clock is not ≤ C's
Position C: 0 < 1 → B's clock is not ≥ C's
Result: CONCURRENT — True conflict detected!

The Resolution Decision

Vector clocks only DETECT concurrency—they don't resolve it. When concurrent versions are discovered, the system must choose: (1) Return both versions to the application for manual resolution, (2) Apply a deterministic merge function, (3) Use LWW as a fallback, or (4) Invoke application-specific logic. The 'right' choice depends on your domain.

Vector Clocks in Production Databases

Several distributed databases use vector clocks (or variants) for conflict detection. Understanding their implementations illuminates practical considerations.

Riak's Vector Clocks

Riak was one of the most prominent users of vector clocks for conflict detection. Each object stores a vector clock with its value.

How Riak Uses Vector Clocks:

On Write: Client includes the vector clock from their last read
On Receive: Riak compares incoming clock with stored clock
If Sequential: The new version replaces the old
If Concurrent: Both versions are kept as 'siblings'
On Read: If siblings exist, all are returned to the client for resolution

The Sibling Problem:

When conflicts occur, Riak keeps ALL concurrent versions (siblings). This is correct but creates overhead:

Storage grows with sibling count
Read latency increases (must return all siblings)
Applications must handle resolution

Client-Side Resolution Pattern:

riak-siblings.ts
TypeScript
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
// Riak-style sibling resolution (pseudocode)
interface RiakObject<T> {
    values: T[];           // All sibling values
    vclock: VectorClock;   // Vector clock for the read
}
 
async function readWithResolution<T>(
    key: string,
    resolver: (siblings: T[]) => T
): Promise<T> {
    const obj = await riak.get(key);
    
    if (obj.values.length === 1) {
        // No conflict
        return obj.values[0];
    }
    
    // Conflict detected! Multiple siblings.
    console.log(`${obj.values.length} siblings detected for ${key}`);
    
    // Application resolves
    const resolved = resolver(obj.values);
    
    // Write resolved value back with parent's vector clock
    await riak.put(key, resolved, obj.vclock);
    
    return resolved;
}
 
// Example resolver for shopping cart: union of all items
function cartResolver(carts: Cart[]): Cart {
    const allItems = new Map<string, CartItem>();
    for (const cart of carts) {
        for (const item of cart.items) {
            const existing = allItems.get(item.id);
            if (!existing || item.quantity > existing.quantity) {
                allItems.set(item.id, item);
            }
        }
    }
    return { items: Array.from(allItems.values()) };
}

Practical Limitations of Vector Clocks

While theoretically elegant, vector clocks have practical challenges in production systems.

Vector Clock Challenges

•Size Growth — Vector clocks grow with the number of actors/nodes. In a 1000-node cluster, each value carries a 1000-element vector. For per-client clocks, the size can grow unbounded.
•Garbage Collection — When can old entries be removed? A naive removal might cause a 'forgotten' node's writes to appear concurrent with everything.
•Client vs Server Clocks — Should each client have a slot (accurate but huge) or should servers proxy (smaller but loses precision)? Both approaches have trade-offs.
•Dynamic Membership — Adding/removing nodes complicates vector clock maintenance. What happens to Node X's slot when Node X is decommissioned?
•Sibling Explosion — Without careful client behavior, concurrent updates can create many siblings that never get resolved, causing storage and latency bloat.
•Application Complexity — Exposing conflicts to applications requires application developers to handle resolution—many prefer automatic (if lossy) resolution.

Vector Clock Size: A Concrete Example

System Configuration	Vector Size per Object
5-node cluster	5 × 8 bytes = 40 bytes
100-node cluster	100 × 8 bytes = 800 bytes
Per-client (10K clients)	10,000 × 8 bytes = 80 KB
Per-client (1M clients)	Infeasible

This is why systems like Dynamo used 'server-side' vector clocks (one slot per server, not per client), accepting reduced precision for practical size bounds.

Mitigation Strategies:

Server-Side Clocks: Limit slots to servers, not clients
Clock Pruning: Remove entries below a threshold after sufficient time
Version Vectors with Bounds: Limit maximum slots, merge old entries
Dotted Version Vectors: More compact representation of causal history

Version Vectors vs Vector Clocks

The terms 'vector clock' and 'version vector' are often used interchangeably, but there are subtle distinctions in their application.

Vector Clocks

•Track events/operations
•Increment on every event
•Capture full event history
•Research/theoretical focus
•Lamport's original concept

Version Vectors

•Track data versions
•Increment on data write
•Capture version lineage
•Practical/database focus
•Adapted for replication

In Practice:

The distinction is often academic. What matters is that both provide:

Partial ordering — Determine if A happened before B, or if they're concurrent
Merge semantics — Take component-wise maximum when syncing
Concurrency detection — Identify when neither version dominates

When reading database documentation, treat 'vector clock' and 'version vector' as roughly equivalent. The implementation details vary, but the core purpose—tracking causality for conflict detection—remains the same.

Terminology in Production Systems

Riak calls them 'vector clocks,' Cassandra's documentation refers to 'version vectors,' CouchDB uses 'revision trees.' The concepts overlap significantly. Focus on understanding the semantics (causal tracking for conflict detection) rather than getting hung up on terminology.

Implementing Vector Clock Resolution

When vector clocks detect concurrency, the system (or application) must resolve the conflict. Here's a complete implementation pattern.

vector-clock-store.ts
TypeScript
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
interface VectorClock {
    [nodeId: string]: number;
}
 
interface VersionedValue<T> {
    value: T;
    vclock: VectorClock;
}
 
type ConflictResolution<T> = 
    | { type: 'resolved'; value: T }
    | { type: 'merged'; value: T }
    | { type: 'keep_both'; values: T[] };
 
interface ConflictResolver<T> {
    /**
     * Called when concurrent versions are detected.
     * @param versions All concurrent versions
     * @returns Resolution decision
     */
    resolve(versions: VersionedValue<T>[]): ConflictResolution<T>;
}
 
/**
 * Vector clock-based conflict-detecting store.
 */
class VectorClockStore<T> {
    private data: Map<string, VersionedValue<T>[]> = new Map();
    private resolver: ConflictResolver<T>;
    
    constructor(resolver: ConflictResolver<T>) {
        this.resolver = resolver;
    }
    
    /**
     * Write a value. Detects conflicts with existing versions.
     */
    write(key: string, value: T, vclock: VectorClock): void {
        const existing = this.data.get(key) ?? [];
        
        // Determine relationship with each existing version
        const dominated: VersionedValue<T>[] = [];
        const concurrent: VersionedValue<T>[] = [];
        
        for (const version of existing) {
            const comparison = this.compare(vclock, version.vclock);
            
            if (comparison === 'AFTER') {
                // New version supersedes this one
                dominated.push(version);
            } else if (comparison === 'CONCURRENT') {
                // Genuine conflict
                concurrent.push(version);
            }
            // If BEFORE, the existing version supersedes new (reject new)
            // If EQUAL, same version (skip)
        }
        
        // If new version is dominated by any existing, reject it
        const dominated_by_existing = existing.some(
            v => this.compare(vclock, v.vclock) === 'BEFORE'
        );
        
        if (dominated_by_existing) {
            console.log('Write rejected: superseded by existing version');
            return;
        }
        
        const newVersion: VersionedValue<T> = { value, vclock };
        
        if (concurrent.length === 0) {
            // No conflicts: new version replaces dominated ones
            this.data.set(key, [newVersion]);
        } else {
            // Conflicts detected! Use resolver
            const allVersions = [...concurrent, newVersion];
            const resolution = this.resolver.resolve(allVersions);
            
            switch (resolution.type) {
                case 'resolved':
                case 'merged':
                    // Single resolved value with merged clock
                    const mergedClock = this.mergeClock(allVersions.map(v => v.vclock));
                    this.data.set(key, [{ 
                        value: resolution.value, 
                        vclock: mergedClock 
                    }]);
                    break;
                case 'keep_both':
                    // Store as siblings for later resolution
                    this.data.set(key, allVersions);
                    break;
            }
        }
    }
    
    /**
     * Read value(s). May return multiple if unresolved siblings exist.
     */
    read(key: string): VersionedValue<T>[] {
        return this.data.get(key) ?? [];
    }
    
    private compare(vc1: VectorClock, vc2: VectorClock): string {
        // (Implementation from earlier)
        const allNodes = new Set([...Object.keys(vc1), ...Object.keys(vc2)]);
        let v1Le = true, v2Le = true, anyDiff = false;
        
        for (const node of allNodes) {
            const v1 = vc1[node] ?? 0;
            const v2 = vc2[node] ?? 0;
            if (v1 > v2) v1Le = false;
            if (v2 > v1) v2Le = false;
            if (v1 !== v2) anyDiff = true;
        }
        
        if (!anyDiff) return 'EQUAL';
        if (v1Le) return 'BEFORE';
        if (v2Le) return 'AFTER';
        return 'CONCURRENT';
    }
    
    private mergeClock(clocks: VectorClock[]): VectorClock {
        const result: VectorClock = {};
        for (const clock of clocks) {
            for (const [node, count] of Object.entries(clock)) {
                result[node] = Math.max(result[node] ?? 0, count);
            }
        }
        return result;
    }
}
 
// Example: Shopping cart merge resolver
const cartResolver: ConflictResolver<CartItems> = {
    resolve(versions) {
        // Merge strategy: union of all carts
        const merged: CartItems = { items: [] };
        const itemMap = new Map<string, CartItem>();
        
        for (const version of versions) {
            for (const item of version.value.items) {
                const existing = itemMap.get(item.id);
                if (!existing || item.addedAt > existing.addedAt) {
                    itemMap.set(item.id, item);
                }
            }
        }
        
        merged.items = Array.from(itemMap.values());
        return { type: 'merged', value: merged };
    }
};

Summary: Vector Clocks for Causality

Vector clocks provide the theoretical foundation for detecting true concurrency in distributed systems. Unlike LWW, they tell us when we have a real conflict versus a simple ordering. Let's consolidate the key insights:

Key Takeaways

•Causal tracking, not just ordering — Vector clocks determine if events are causally related (one influenced the other) or genuinely concurrent (independent).
•Structure: array of counters — One counter per node, updated on local events and message receives.
•Comparison yields four outcomes — BEFORE, AFTER, EQUAL, or CONCURRENT. CONCURRENT means true conflict.
•Detection, not resolution — Vector clocks identify conflicts; resolution requires additional strategy (merge, LWW fallback, etc.).
•Real-world adaptations — Production systems use variants (dotted version vectors, revision trees) to address practical challenges.
•Size is a concern — Clocks grow with node count; mitigation strategies include pruning, server-side clocks, and bounded vectors.
•Enables smarter resolution — Knowing 'this is a genuine conflict' allows more intelligent handling than blindly picking a timestamp winner.

What's Next:

Vector clocks detect conflicts, but when a real conflict occurs, we need a strategy to resolve it. The next page explores Application-Level Merge—how to write domain-specific resolution logic that combines conflicting values intelligently, preserving as much user intent as possible.

Page Complete

You now understand vector clocks comprehensively—their structure, comparison semantics, production implementations, and practical limitations. You can reason about causal relationships in distributed systems and detect true concurrency.

3 / 5

Loading learning content...

Conflict Resolution Strategies - Page 3 of 5 | OneNoughtOne

System Design (HLD)Conflict Resolution Strategies

Conflict Resolution Strategies

LevelAdvanced

Duration120 mins

TopicConflict Resolution Strategies

3 / 5

Vector Clocks for Causality

Tracking The Flow of Causality

Vector clocks give us the tools to make this determination, enabling smarter conflict handling than simple timestamp comparison.

What You Will Learn

The Limitation of Scalar Timestamps

Before diving into vector clocks, let's understand why scalar (single-value) timestamps are insufficient for distributed conflict detection.

Converting Mermaid diagram...

The Gap in Lamport Clocks:

Relationship	Lamport Guarantee
A → B (A happened before B)	ts(A) < ts(B) ✓
ts(A) < ts(B)	Maybe A → B, maybe concurrent (?)
ts(A) = ts(B)	Concurrent or same event (?)

We need a clock that can definitively answer: Were these events concurrent, or did one causally precede the other?

Vector clocks provide exactly this capability. By tracking the knowledge each node has about other nodes' progress, we can determine causal relationships—or their absence.

Happens-Before Refresher

Vector Clock Fundamentals

A vector clock is an array of counters, one for each node (or actor) in the distributed system. Each node maintains its own vector clock and updates it according to specific rules.

Structure:

For a system with N nodes, a vector clock is: VC = [c₁, c₂, c₃, ..., cₙ]

Where cᵢ represents the number of events that have occurred at node i, as known by the node holding this vector clock.

Rules:

On local event: Increment your own counter
On send: Include your vector clock with the message
On receive: Update your vector clock to max(yours, received) for each position, then increment your own counter

vector-clock.ts
TypeScript
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
interface VectorClock {
    [nodeId: string]: number;
}
 
/**
 * Vector Clock implementation for distributed causality tracking.
 */
class VectorClockManager {
    private clock: VectorClock;
    private nodeId: string;
    
    constructor(nodeId: string, knownNodes: string[] = []) {
        this.nodeId = nodeId;
        this.clock = {};
        
        // Initialize all known nodes to 0
        for (const node of knownNodes) {
            this.clock[node] = 0;
        }
        this.clock[nodeId] = 0;
    }
    
    /**
     * Increment clock for a local event.
     */
    tick(): VectorClock {
        this.clock[this.nodeId] = (this.clock[this.nodeId] ?? 0) + 1;
        return this.getClock();
    }
    
    /**
     * Prepare clock to send with a message (tick first).
     */
    send(): VectorClock {
        return this.tick();  // Local event: sending
    }
    
    /**
     * Update clock on receiving a message.
     */
    receive(remoteClock: VectorClock): VectorClock {
        // Merge: take component-wise maximum
        const allNodes = new Set([
            ...Object.keys(this.clock),
            ...Object.keys(remoteClock),
        ]);
        
        for (const node of allNodes) {
            const local = this.clock[node] ?? 0;
            const remote = remoteClock[node] ?? 0;
            this.clock[node] = Math.max(local, remote);
        }
        
        // Then increment our own counter (receiving is a local event too)
        this.clock[this.nodeId] = (this.clock[this.nodeId] ?? 0) + 1;
        
        return this.getClock();
    }
    
    getClock(): VectorClock {
        return { ...this.clock };
    }
}
 
// Example: Three-node system
const nodeA = new VectorClockManager('A', ['A', 'B', 'C']);
const nodeB = new VectorClockManager('B', ['A', 'B', 'C']);
const nodeC = new VectorClockManager('C', ['A', 'B', 'C']);
 
// Node A performs a local event
const vc1 = nodeA.tick();
console.log('After A event:', vc1);  // { A: 1, B: 0, C: 0 }
 
// Node A sends to B
const msgToB = nodeA.send();
console.log('A sends:', msgToB);  // { A: 2, B: 0, C: 0 }
 
// Node B receives from A
const vc2 = nodeB.receive(msgToB);
console.log('B after receive:', vc2);  // { A: 2, B: 1, C: 0 }

Intuition:

Comparing Vector Clocks

The power of vector clocks lies in their comparison semantics. Given two vector clocks VC₁ and VC₂, we can determine their causal relationship.

Vector Clock Comparison Rules
Condition	Relationship	Interpretation
VC₁[i] ≤ VC₂[i] for all i, and VC₁ ≠ VC₂	VC₁ < VC₂ (VC₁ happened before VC₂)	Event 1 causally precedes Event 2
VC₁[i] ≥ VC₂[i] for all i, and VC₁ ≠ VC₂	VC₁ > VC₂ (VC₂ happened before VC₁)	Event 2 causally precedes Event 1
VC₁[i] = VC₂[i] for all i	VC₁ = VC₂ (equal)	Same event or identical state
Neither VC₁ ≤ VC₂ nor VC₁ ≥ VC₂	VC₁ \|\| VC₂ (concurrent)	Genuinely concurrent events!

vector-clock-compare.ts
TypeScript
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
interface VectorClock {
    [nodeId: string]: number;
}
 
type VectorComparison = 
    | 'BEFORE'      // VC1 happened before VC2 (VC1 < VC2)
    | 'AFTER'       // VC1 happened after VC2 (VC1 > VC2)
    | 'EQUAL'       // Identical clocks
    | 'CONCURRENT'; // Neither dominates - true conflict!
 
function compareVectorClocks(
    vc1: VectorClock, 
    vc2: VectorClock
): VectorComparison {
    const allNodes = new Set([
        ...Object.keys(vc1),
        ...Object.keys(vc2),
    ]);
    
    let vc1LessOrEqual = true;   // All vc1[i] <= vc2[i]
    let vc2LessOrEqual = true;   // All vc2[i] <= vc1[i]
    let anyDifferent = false;
    
    for (const node of allNodes) {
        const v1 = vc1[node] ?? 0;
        const v2 = vc2[node] ?? 0;
        
        if (v1 > v2) vc1LessOrEqual = false;
        if (v2 > v1) vc2LessOrEqual = false;
        if (v1 !== v2) anyDifferent = true;
    }
    
    if (!anyDifferent) {
        return 'EQUAL';
    }
    
    if (vc1LessOrEqual && !vc2LessOrEqual) {
        return 'BEFORE';  // vc1 < vc2
    }
    
    if (vc2LessOrEqual && !vc1LessOrEqual) {
        return 'AFTER';   // vc1 > vc2
    }
    
    // Neither dominates the other
    return 'CONCURRENT';
}
 
// Examples:
// Causal relationship: e1 happened before e2
const e1: VectorClock = { A: 2, B: 1, C: 0 };
const e2: VectorClock = { A: 3, B: 2, C: 1 };
console.log(compareVectorClocks(e1, e2));  // 'BEFORE'
 
// Concurrent events: neither happened before the other
const e3: VectorClock = { A: 2, B: 1, C: 0 };
const e4: VectorClock = { A: 1, B: 2, C: 0 };
console.log(compareVectorClocks(e3, e4));  // 'CONCURRENT' - True conflict!
 
// e3 has A:2 > A:1, so e3 is not <= e4
// e4 has B:2 > B:1, so e4 is not <= e3
// Neither dominates → CONCURRENT

Why Concurrency Detection Matters

Visual Walkthrough

Let's trace through a detailed example of vector clocks detecting concurrent writes in a three-node system.

Converting Mermaid diagram...

Step-by-Step Analysis:

Time	Event	A's Clock	B's Clock	C's Clock
T1	A writes x=1	[1,0,0]	[0,0,0]	[0,0,0]
T2	A syncs to B	[1,0,0]		[0,0,0]
T3	B receives	[1,0,0]	[1,1,0]	[0,0,0]
T4	B writes x=2	[1,0,0]	[1,2,0]	[0,0,0]
T4'	C writes x=3 (concurrent!)	[1,0,0]	[1,2,0]	[0,0,1]

At T4/T4':

B's clock: [1,2,0] — B knows about A's first event and its own two events
C's clock: [0,0,1] — C only knows about its own event

Comparison:

[1,2,0] vs [0,0,1]
Position A: 1 > 0 → B's clock is not ≤ C's
Position C: 0 < 1 → B's clock is not ≥ C's
Result: CONCURRENT — True conflict detected!

The Resolution Decision

Vector Clocks in Production Databases

Several distributed databases use vector clocks (or variants) for conflict detection. Understanding their implementations illuminates practical considerations.

Riak's Vector Clocks

Riak was one of the most prominent users of vector clocks for conflict detection. Each object stores a vector clock with its value.

How Riak Uses Vector Clocks:

On Write: Client includes the vector clock from their last read
On Receive: Riak compares incoming clock with stored clock
If Sequential: The new version replaces the old
If Concurrent: Both versions are kept as 'siblings'
On Read: If siblings exist, all are returned to the client for resolution

The Sibling Problem:

When conflicts occur, Riak keeps ALL concurrent versions (siblings). This is correct but creates overhead:

Storage grows with sibling count
Read latency increases (must return all siblings)
Applications must handle resolution

Client-Side Resolution Pattern:

riak-siblings.ts
TypeScript
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
// Riak-style sibling resolution (pseudocode)
interface RiakObject<T> {
    values: T[];           // All sibling values
    vclock: VectorClock;   // Vector clock for the read
}
 
async function readWithResolution<T>(
    key: string,
    resolver: (siblings: T[]) => T
): Promise<T> {
    const obj = await riak.get(key);
    
    if (obj.values.length === 1) {
        // No conflict
        return obj.values[0];
    }
    
    // Conflict detected! Multiple siblings.
    console.log(`${obj.values.length} siblings detected for ${key}`);
    
    // Application resolves
    const resolved = resolver(obj.values);
    
    // Write resolved value back with parent's vector clock
    await riak.put(key, resolved, obj.vclock);
    
    return resolved;
}
 
// Example resolver for shopping cart: union of all items
function cartResolver(carts: Cart[]): Cart {
    const allItems = new Map<string, CartItem>();
    for (const cart of carts) {
        for (const item of cart.items) {
            const existing = allItems.get(item.id);
            if (!existing || item.quantity > existing.quantity) {
                allItems.set(item.id, item);
            }
        }
    }
    return { items: Array.from(allItems.values()) };
}

Practical Limitations of Vector Clocks

While theoretically elegant, vector clocks have practical challenges in production systems.

Vector Clock Challenges

•Size Growth — Vector clocks grow with the number of actors/nodes. In a 1000-node cluster, each value carries a 1000-element vector. For per-client clocks, the size can grow unbounded.
•Garbage Collection — When can old entries be removed? A naive removal might cause a 'forgotten' node's writes to appear concurrent with everything.
•Client vs Server Clocks — Should each client have a slot (accurate but huge) or should servers proxy (smaller but loses precision)? Both approaches have trade-offs.
•Dynamic Membership — Adding/removing nodes complicates vector clock maintenance. What happens to Node X's slot when Node X is decommissioned?
•Sibling Explosion — Without careful client behavior, concurrent updates can create many siblings that never get resolved, causing storage and latency bloat.
•Application Complexity — Exposing conflicts to applications requires application developers to handle resolution—many prefer automatic (if lossy) resolution.

Vector Clock Size: A Concrete Example

System Configuration	Vector Size per Object
5-node cluster	5 × 8 bytes = 40 bytes
100-node cluster	100 × 8 bytes = 800 bytes
Per-client (10K clients)	10,000 × 8 bytes = 80 KB
Per-client (1M clients)	Infeasible

This is why systems like Dynamo used 'server-side' vector clocks (one slot per server, not per client), accepting reduced precision for practical size bounds.

Mitigation Strategies:

Server-Side Clocks: Limit slots to servers, not clients
Clock Pruning: Remove entries below a threshold after sufficient time
Version Vectors with Bounds: Limit maximum slots, merge old entries
Dotted Version Vectors: More compact representation of causal history

Version Vectors vs Vector Clocks

The terms 'vector clock' and 'version vector' are often used interchangeably, but there are subtle distinctions in their application.

Vector Clocks

•Track events/operations
•Increment on every event
•Capture full event history
•Research/theoretical focus
•Lamport's original concept

Version Vectors

•Track data versions
•Increment on data write
•Capture version lineage
•Practical/database focus
•Adapted for replication

In Practice:

The distinction is often academic. What matters is that both provide:

Partial ordering — Determine if A happened before B, or if they're concurrent
Merge semantics — Take component-wise maximum when syncing
Concurrency detection — Identify when neither version dominates

Terminology in Production Systems

Implementing Vector Clock Resolution

When vector clocks detect concurrency, the system (or application) must resolve the conflict. Here's a complete implementation pattern.

vector-clock-store.ts
TypeScript
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
interface VectorClock {
    [nodeId: string]: number;
}
 
interface VersionedValue<T> {
    value: T;
    vclock: VectorClock;
}
 
type ConflictResolution<T> = 
    | { type: 'resolved'; value: T }
    | { type: 'merged'; value: T }
    | { type: 'keep_both'; values: T[] };
 
interface ConflictResolver<T> {
    /**
     * Called when concurrent versions are detected.
     * @param versions All concurrent versions
     * @returns Resolution decision
     */
    resolve(versions: VersionedValue<T>[]): ConflictResolution<T>;
}
 
/**
 * Vector clock-based conflict-detecting store.
 */
class VectorClockStore<T> {
    private data: Map<string, VersionedValue<T>[]> = new Map();
    private resolver: ConflictResolver<T>;
    
    constructor(resolver: ConflictResolver<T>) {
        this.resolver = resolver;
    }
    
    /**
     * Write a value. Detects conflicts with existing versions.
     */
    write(key: string, value: T, vclock: VectorClock): void {
        const existing = this.data.get(key) ?? [];
        
        // Determine relationship with each existing version
        const dominated: VersionedValue<T>[] = [];
        const concurrent: VersionedValue<T>[] = [];
        
        for (const version of existing) {
            const comparison = this.compare(vclock, version.vclock);
            
            if (comparison === 'AFTER') {
                // New version supersedes this one
                dominated.push(version);
            } else if (comparison === 'CONCURRENT') {
                // Genuine conflict
                concurrent.push(version);
            }
            // If BEFORE, the existing version supersedes new (reject new)
            // If EQUAL, same version (skip)
        }
        
        // If new version is dominated by any existing, reject it
        const dominated_by_existing = existing.some(
            v => this.compare(vclock, v.vclock) === 'BEFORE'
        );
        
        if (dominated_by_existing) {
            console.log('Write rejected: superseded by existing version');
            return;
        }
        
        const newVersion: VersionedValue<T> = { value, vclock };
        
        if (concurrent.length === 0) {
            // No conflicts: new version replaces dominated ones
            this.data.set(key, [newVersion]);
        } else {
            // Conflicts detected! Use resolver
            const allVersions = [...concurrent, newVersion];
            const resolution = this.resolver.resolve(allVersions);
            
            switch (resolution.type) {
                case 'resolved':
                case 'merged':
                    // Single resolved value with merged clock
                    const mergedClock = this.mergeClock(allVersions.map(v => v.vclock));
                    this.data.set(key, [{ 
                        value: resolution.value, 
                        vclock: mergedClock 
                    }]);
                    break;
                case 'keep_both':
                    // Store as siblings for later resolution
                    this.data.set(key, allVersions);
                    break;
            }
        }
    }
    
    /**
     * Read value(s). May return multiple if unresolved siblings exist.
     */
    read(key: string): VersionedValue<T>[] {
        return this.data.get(key) ?? [];
    }
    
    private compare(vc1: VectorClock, vc2: VectorClock): string {
        // (Implementation from earlier)
        const allNodes = new Set([...Object.keys(vc1), ...Object.keys(vc2)]);
        let v1Le = true, v2Le = true, anyDiff = false;
        
        for (const node of allNodes) {
            const v1 = vc1[node] ?? 0;
            const v2 = vc2[node] ?? 0;
            if (v1 > v2) v1Le = false;
            if (v2 > v1) v2Le = false;
            if (v1 !== v2) anyDiff = true;
        }
        
        if (!anyDiff) return 'EQUAL';
        if (v1Le) return 'BEFORE';
        if (v2Le) return 'AFTER';
        return 'CONCURRENT';
    }
    
    private mergeClock(clocks: VectorClock[]): VectorClock {
        const result: VectorClock = {};
        for (const clock of clocks) {
            for (const [node, count] of Object.entries(clock)) {
                result[node] = Math.max(result[node] ?? 0, count);
            }
        }
        return result;
    }
}
 
// Example: Shopping cart merge resolver
const cartResolver: ConflictResolver<CartItems> = {
    resolve(versions) {
        // Merge strategy: union of all carts
        const merged: CartItems = { items: [] };
        const itemMap = new Map<string, CartItem>();
        
        for (const version of versions) {
            for (const item of version.value.items) {
                const existing = itemMap.get(item.id);
                if (!existing || item.addedAt > existing.addedAt) {
                    itemMap.set(item.id, item);
                }
            }
        }
        
        merged.items = Array.from(itemMap.values());
        return { type: 'merged', value: merged };
    }
};

Summary: Vector Clocks for Causality

Key Takeaways

•Causal tracking, not just ordering — Vector clocks determine if events are causally related (one influenced the other) or genuinely concurrent (independent).
•Structure: array of counters — One counter per node, updated on local events and message receives.
•Comparison yields four outcomes — BEFORE, AFTER, EQUAL, or CONCURRENT. CONCURRENT means true conflict.
•Detection, not resolution — Vector clocks identify conflicts; resolution requires additional strategy (merge, LWW fallback, etc.).
•Real-world adaptations — Production systems use variants (dotted version vectors, revision trees) to address practical challenges.
•Size is a concern — Clocks grow with node count; mitigation strategies include pruning, server-side clocks, and bounded vectors.
•Enables smarter resolution — Knowing 'this is a genuine conflict' allows more intelligent handling than blindly picking a timestamp winner.

What's Next:

Page Complete

3 / 5