Vector Clocks and Conflict Resolution: Detecting Concurrent Writes in Distributed State

Why You Need This in Real Life

Two users updating a shared shopping cart at the exact same millisecond can trigger silent data loss in distributed NoSQL databases like Amazon Dynamo or Apache Cassandra.

User A on Node 1 adds a “Laptop” to their cart. Almost simultaneously, User B on Node 2 adds a “Mouse” to the same cart. Neither node is aware of the other’s concurrent update.

If the storage system uses simple scalar timestamps or Last-Write-Wins (LWW), the database will overwrite one update with the other. Either the “Laptop” or the “Mouse” vanishes from the cart, frustrating the user and dropping revenue.

To preserve both updates during concurrent network partitions, master-master distributed databases use Vector Clocks. Instead of silently overwriting data, Vector Clocks detect that the two writes occurred concurrently, branching the record into siblings so the application layer can merge them safely later.

Part 1: What is a Vector Clock?

A Vector Clock is an array (vector) of logical clock counters—one counter for every node in the cluster.

For a cluster of $N$ nodes, a Vector Clock $V$ is represented as:

$V = [V[1], V[2], \dots, V[N]]$

Where $V[i]$ represents the logical clock value of node $i$ as observed by the current node.

Key: "cart_42"
Value: "Item: Laptop"
Vector Clock: { NodeA: 2, NodeB: 1 }

Part 2: Vector Clock Rules & Algorithm

Algorithm Execution Rules

Initialization: Each node starts with a vector filled with zeroes: $V = [0, 0, \dots, 0]$ .
Local Mutation: Before a node $S_i$ writes or updates a record, it increments its own entry in the vector: $V_i[i] = V_i[i] + 1$
Message Attachment: Node $S_i$ attaches its updated vector $V_i$ to the data object payload sent over the network.
Merge Upon Receipt: When node $S_j$ receives a data object with vector $V_{msg}$ , it updates its local vector by taking the component-wise maximum of both vectors: $V_j[k] = \max(V_j[k], V_{msg}[k]) \quad \text{for all } k$ And then increments its own entry $V_j[j] = V_j[j] + 1$ .

Node A (Initial)            Node B (Initial)
VC_A = {A:0, B:0}           VC_B = {A:0, B:0}

1. Node A writes "Cart: [Laptop]"
   VC_A = {A:1, B:0}

2. Node A replicates to Node B
   Node B merges: VC_B = max({A:0, B:0}, {A:1, B:0}) = {A:1, B:0}

3. Node B updates "Cart: [Laptop, Mouse]"
   VC_B[B]++ -> VC_B = {A:1, B:1}

Part 3: Determining Causality vs Concurrency

Given two vector timestamps $V_1$ and $V_2$ :

Causal Dominance ( $V_1 \rightarrow V_2$ ): $V_1$ happened before $V_2$ if and only if:
- Every element in $V_1$ is less than or equal to the corresponding element in $V_2$ : $\forall k, \quad V_1[k] \le V_2[k]$
- At least one element in $V_1$ is strictly less than in $V_2$ : $\exists k, \quad V_1[k] < V_2[k]$
Concurrent Conflict ( $V_1 \parallel V_2$ ): $V_1$ and $V_2$ are concurrent if neither vector dominates the other.
- Example: $V_1 = \{A:2, B:1\}$ and $V_2 = \{A:1, B:2\}$ .
- In $V_1$ , Node A is ahead ( $2 > 1$ ). In $V_2$ , Node B is ahead ( $2 > 1$ ).
- Neither write knew about the other! This is a concurrent write conflict!

           Vector A: { Node1: 2, Node2: 1 }
           Vector B: { Node1: 1, Node2: 2 }
                         \       /
                          v     v
                 CONCURRENT CONFLICT DETECTED!
            Create Siblings: [Cart_A, Cart_B]

Part 4: Runnable Java Vector Clock Implementation

package com.example.clock;

import java.util.*;

public class VectorClock {

    private final Map<String, Integer> clockMap = new HashMap<>();

    public VectorClock() {}

    public VectorClock(Map<String, Integer> initialMap) {
        this.clockMap.putAll(initialMap);
    }

    // Increment local node counter
    public synchronized void increment(String nodeId) {
        clockMap.put(nodeId, clockMap.getOrDefault(nodeId, 0) + 1);
    }

    // Merge remote vector clock
    public synchronized void merge(VectorClock remoteClock) {
        for (Map.Entry<String, Integer> entry : remoteClock.clockMap.entrySet()) {
            String nodeId = entry.getKey();
            int remoteValue = entry.getValue();
            int localValue = clockMap.getOrDefault(nodeId, 0);
            clockMap.put(nodeId, Math.max(localValue, remoteValue));
        }
    }

    // Determine relation: DOMINATES, DOMINATED_BY, or CONCURRENT
    public VectorComparison compareTo(VectorClock other) {
        boolean hasGreater = false;
        boolean hasLesser = false;

        Set<String> allNodes = new HashSet<>(this.clockMap.keySet());
        allNodes.addAll(other.clockMap.keySet());

        for (String node : allNodes) {
            int v1 = this.clockMap.getOrDefault(node, 0);
            int v2 = other.clockMap.getOrDefault(node, 0);

            if (v1 > v2) hasGreater = true;
            if (v1 < v2) hasLesser = true;
        }

        if (hasGreater && !hasLesser) return VectorComparison.DOMINATES; // This happened AFTER other
        if (hasLesser && !hasGreater) return VectorComparison.DOMINATED_BY; // This happened BEFORE other
        if (!hasGreater && !hasLesser) return VectorComparison.EQUAL;
        return VectorComparison.CONCURRENT; // Conflict! Needs Application Merge!
    }

    public enum VectorComparison {
        EQUAL, DOMINATES, DOMINATED_BY, CONCURRENT
    }

    public Map<String, Integer> getClockMap() {
        return Collections.unmodifiableMap(clockMap);
    }

    @Override
    public String toString() {
        return clockMap.toString();
    }
}

Part 5: Production Challenges: Vector Truncation & Sibling Explosions

While Vector Clocks prevent silent data loss, they introduce two production challenges:

1. Vector Size Growth

In large dynamic clusters where nodes join and leave frequently, vector maps can grow indefinitely, consuming memory.

Solution: Truncate old vector entries using a threshold (e.g., retain only the 10 most recent nodes or prune entries older than 7 days).

2. Sibling Branch Explosions

If network partitions persist for long periods while heavy concurrent writes occur, a record can branch into dozens of sibling versions.

Solution: Implement client-side or server-side merge resolvers (e.g., unioning set elements in shopping carts or using Conflict-Free Replicated Data Types - CRDTs).

Next Steps

Now that we understand distributed foundations, time, and vector clocks, we will enter Module 2 (Scalable Data Partitioning & Routing): starting with Consistent Hashing and Virtual Nodes in Part 4.

References & Further Reading

DeCandia, G., et al. (2007). Dynamo: Amazon’s Highly Available Key-value Store. Proceedings of ACM SOSP ‘07, 205–220.
Vogels, W. (2009). Eventually Consistent. Communications of the ACM, 52(1), 40–44.
Kleppmann, M. (2017). Designing Data-Intensive Applications (Chapter 5: Replication). O’Reilly Media.