Vector Clocks in TypeScript for Causal Ordering

From a Single Counter to a Vector

The problem with Lamport clocks stems from the fact that they collapse all causality information into a single integer. When a node receives a message, it updates its clock to max(local_time, received_time) + 1, effectively forgetting which node's history it just incorporated. It only knows that something happened before.

Vector clocks solve this by maintaining a separate counter for each node in the system. Instead of a single integer, each node stores a vector (or a map in our implementation) of integers. Let's say we have three nodes: Alice, Bob, and Carol. A vector clock would look something like [c_alice, c_bob, c_carol].

The rule is simple: the i-th entry in the vector counts the number of events that have occurred at node i. When a node has a vector clock like [3, 1, 0], it means it knows about 3 events from the first node, 1 event from the second, and 0 from the third.

The Vector Clock Algorithm

The algorithm for updating these vectors is just as straightforward as Lamport's, but it preserves much more information. There are two main rules for updating the clock:

1. For a local event: A node increments its own counter in the vector. For example, if Alice (node P1) performs an action, her clock [1,0,0] becomes [2,0,0].

2. For a send/receive event:

   • A node sends a message with its current vector clock attached.
   • Upon receiving a message, the receiving node first updates its clock by taking the element-wise maximum of its own clock and the clock from the message.
   • Then, it increments its own counter in the resulting vector to account for the receive event itself.

Let's look at a diagram that illustrates this process across three nodes.

Trace the arrows and clocks in the diagram:

• P1 starts with a local event, moving its clock to [1,0,0]. Another local event moves it to [2,0,0].
• P1 sends its clock [2,0,0] to P2.
• P2 receives it. P2's clock was [0,1,0]. The element-wise maximum of [0,1,0] and [2,0,0] is [2,1,0]. P2 then increments its own entry (the second one) for the receive event, resulting in [2,2,0].
• Notice the event at P2 with clock [2,3,1]. This tells us that this event is causally dependent on 2 events from P1, 3 events from P2, and 1 event from P3.

From Theory to Implementation in TypeScript

Your experience architecting frontend applications has likely given you a strong intuition for managing state. A vector clock is simply a piece of state that precisely tracks the causal history between distributed components.

Let's translate the algorithm into a TypeScript class.

Based on the resource, we can define our VectorClock class. Here, we'll use a Map to store the clock, which is more flexible than a fixed-size array as it doesn't require knowing all nodes in advance.

// A unique identifier for each client/node.
type NodeID = string;

export class VectorClock {
  // The clock is a map from NodeID to its latest event counter.
  private clock: Map<NodeID, number>;
  public readonly nodeId: NodeID;

  constructor(nodeId: NodeID) {
    this.nodeId = nodeId;
    this.clock = new Map<NodeID, number>();
    // Initialize its own clock to 0. It will be incremented on the first event.
    this.clock.set(this.nodeId, 0);
  }

  // Called for any local event or before sending a message.
  // It increments the local node's counter.
  tick(): void {
    const current = this.clock.get(this.nodeId) || 0;
    this.clock.set(this.nodeId, current + 1);
  }

  // Called upon receiving a message. It merges the received clock
  // and then ticks for the receive event.
  merge(receivedClock: Map<NodeID, number>): void {
    for (const [nodeId, timestamp] of receivedClock.entries()) {
      const localTimestamp = this.clock.get(nodeId) || 0;
      this.clock.set(nodeId, Math.max(localTimestamp, timestamp));
    }
  }

  // Helper to get a clone of the clock for sending.
  getClock(): Map<NodeID, number> {
    return new Map(this.clock);
  }

  // For display
  toString(): string {
    const entries = Array.from(this.clock.entries())
      .sort()
      .map(([k, v]) => `"${k}":${v}`);
    return `{${entries.join(",")}}`;
  }
}

Now, let's run a simulation similar to the one in the diagram.

// --- Simulation ---

// 1. Initialize clocks for three different clients
const alice = new VectorClock("alice");
const bob = new VectorClock("bob");
const charlie = new VectorClock("charlie");

// 2. Alice performs a local action
alice.tick();
console.log(`Alice's local event. Clock: ${alice.toString()}`); // {"alice":1}

// 3. Alice sends a message to Bob
alice.tick(); // Event for sending the message
const aliceClockOnSend = alice.getClock();
console.log(`Alice sends a message. Clock: ${alice.toString()}`); // {"alice":2}

// Bob receives the message from Alice.
bob.merge(aliceClockOnSend);
bob.tick(); // Event for receiving the message
console.log(`Bob receives from Alice. Clock: ${bob.toString()}`); // {"alice":2, "bob":1}

// 4. Bob and Charlie have concurrent events
bob.tick();
console.log(`Bob's second local event. Clock: ${bob.toString()}`); // {"alice":2, "bob":2}

charlie.tick();
console.log(`Charlie's concurrent event. Clock: ${charlie.toString()}`); // {"charlie":1}

// 5. Bob sends a message to Charlie
bob.tick(); // Event for sending
const bobClockOnSend = bob.getClock();
console.log(`Bob sends to Charlie. Clock: ${bob.toString()}`); // {"alice":2, "bob":3}

// Charlie receives the message from Bob.
charlie.merge(bobClockOnSend);
charlie.tick(); // Event for receiving
console.log(`Charlie receives from Bob. Clock: ${charlie.toString()}`); // {"alice":2, "bob":3, "charlie":2}

/*
Expected Output:
Alice's local event. Clock: {"alice":1}
Alice sends a message. Clock: {"alice":2}
Bob receives from Alice. Clock: {"alice":2,"bob":1}
Bob's second local event. Clock: {"alice":2,"bob":2}
Charlie's concurrent event. Clock: {"charlie":1}
Bob sends to Charlie. Clock: {"alice":2,"bob":3}
Charlie receives from Bob. Clock: {"alice":2,"bob":3,"charlie":2}
*/

Run this code yourself and trace how the merge and tick operations build up the final state {"alice":2,"bob":3,"charlie":2} at Charlie's node, which correctly reflects that his state depends on 2 events from Alice and 3 from Bob.

The Payoff: Detecting Concurrency

So, we have these vectors. What do they buy us? The real power comes from comparing them. The relationship between vector clocks perfectly mirrors the "happens-before" relationship.

As Kleppmann explains, for any two vector clocks V and W:

• V < W if and only if V happened before W. This is true if V[i] <= W[i] for all nodes i, and V != W.
• V and W are concurrent if and only if neither V < W nor W < V. This happens when V is "bigger" in some dimensions and W is "bigger" in others.

Let's look at our simulation again.

• Bob's clock after his second local event was {"alice":2, "bob":2}.
• Charlie's clock after his concurrent event was {"charlie":1}.

Let's compare them, filling in implicit zeros: V_bob = {"alice":2, "bob":2, "charlie":0} and V_charlie = {"alice":0, "bob":0, "charlie":1}.

• Is V_bob < V_charlie? No, because V_bob["alice"] > V_charlie["alice"].
• Is V_charlie < V_bob? No, because V_charlie["charlie"] > V_bob["charlie"].

Since neither is less than the other, the events are concurrent. A Lamport timestamp would have given them an arbitrary order (L(bob) = 2, L(charlie) = 1) and hidden this fact. Vector clocks reveal the truth.

Conclusion

This lesson marks a major step forward. We've moved beyond simple ordering and now have a tool that precisely captures the causal structure of events in a distributed system.

Here are the key takeaways:

• Vector clocks use a vector (or map) of counters, one for each node, to track events.
• The merge rule (element-wise max) ensures that a node's clock always reflects all the events that causally preceded it.
• Most importantly, comparing vector clocks gives us an "if and only if" relationship with causality. We can now definitively tell if one event happened before another, or if they were concurrent.

You have now implemented the core data structure that underpins many optimistic replication and conflict-resolution systems. You have the tick and merge functions working. In our next lesson, we will complete our VectorClock class by implementing the compare method and using it to explicitly detect concurrent operations—the first and most critical step in handling conflicts in your collaborative app.