Vector Clocks

Vector Clocks

Lamport clocks tell us event ordering, but not causality in both directions. Vector clocks solve this: they can determine whether two events are causally related or concurrent (neither caused the other).

How It Works

Each process maintains a vector — an array of counters, one per process. For N processes, each process i has a vector [c₀, c₁, ..., cₙ₋₁].

Rules:

1. On internal event: increment your own counter: vc[i]++.
2. Before sending: increment your counter, then attach your vector.
3. On receiving: merge by taking the element-wise max, then increment your own counter.

class VectorClock {
  constructor(id, n) {
    this.id = id;       // this process's index
    this.vc = new Array(n).fill(0);
  }

  tick() {
    this.vc[this.id]++;
    return [...this.vc];
  }

  send() {
    this.vc[this.id]++;
    return [...this.vc];
  }

  receive(remoteVc) {
    for (let i = 0; i < this.vc.length; i++) {
      this.vc[i] = Math.max(this.vc[i], remoteVc[i]);
    }
    this.vc[this.id]++;
    return [...this.vc];
  }
}

Comparing Vectors

Given two vectors A and B:

• A happened-before B if every A[i] <= B[i] and at least one A[i] < B[i].
• A and B are concurrent if neither happened-before the other.

This is exactly what systems like DynamoDB and Riak use to detect write conflicts.

Your Task

Implement a VectorClock class for a system of n processes. Process id (0-indexed) maintains the vector.