Systems · Distributed

Who Caused What.

Q: What is a vector clock?

A vector clock is a mechanism for capturing the causal ("happened-before") ordering of events in a distributed system without a shared physical clock. Each of n processes maintains a vector of n counters; a process bumps its own counter on each event, attaches its vector to outgoing messages, and merges incoming vectors by taking the element-wise maximum. Comparing two vectors reveals whether one event causally precedes another or whether they are concurrent.

Q: How do vector clocks differ from Lamport clocks?

A Lamport clock is a single counter that guarantees if A happened-before B then A’s timestamp is less than B’s — but the converse fails: a smaller timestamp does not prove causality, and Lamport clocks cannot detect concurrency. Vector clocks fix this: A happened-before B if and only if A’s vector is ≤ B’s in every entry, and if neither dominates, the events are provably concurrent. The cost is O(n) space per timestamp instead of O(1).

Q: What are vector clocks used for?

Detecting conflicting concurrent updates in eventually-consistent databases (Amazon Dynamo and Riak use vector clocks — actually version vectors — to flag write conflicts that need reconciliation), ordering messages in distributed protocols, causal consistency in replicated systems, debugging and snapshots in distributed tracing, and as the basis for many conflict-free replicated data type (CRDT) designs.

Q: What is the downside of vector clocks?

Each timestamp is O(n) in the number of processes, so with many processes the vectors grow large, and in systems with dynamic membership (nodes joining and leaving) the vectors can accumulate stale entries. Practical systems use variants like version vectors (per-replica rather than per-client), dotted version vectors, or interval tree clocks to bound the overhead while keeping the causality-tracking benefit.

In a distributed system there is no single clock everyone agrees on, so “which event happened first?” is genuinely ambiguous. Vector clocks give a precise, decentralized answer for the events that do have a cause-and-effect relationship. Each of the n processes keeps a length-n vector counting events. Three rules: on a local event, bump your own entry; when you send a message, attach your vector; when you receive one, merge by taking the element-wise max, then bump your own entry. Compare two vectors afterward: if one is ≤ the other everywhere, the first “happened-before” the second; if neither dominates, the events are truly concurrent. Step through a scenario and watch causality light up.

happened-before without a global clock · merge by element-wise max · detect concurrency

vector clock

A per-process length-n array counting events each process has observed.

local event

A process does something on its own → it increments its own entry.

send / receive

Send attaches your vector; receive merges by element-wise max, then bumps self.

happened-before

A → B iff A’s vector ≤ B’s everywhere; if neither ≤, they are concurrent.

vectorclock.js — max on receive, bump on event

Ready

Three processes P0, P1, P2 on their own timelines, no shared clock. Each event shows the process’s vector clock. Messages (arrows) carry a vector; receiving merges it by max. Step through the events.

0/7

events

–

last kind

–

concurrent pairs

How it works

The element-wise max on receive is the whole trick. Your vector entry V[j] means “the number of events at process j that I know about.” When you receive a message, the sender knew about some events you didn’t, so you adopt the larger count for every process — max — folding their knowledge into yours; then you bump your own entry for the receive event itself. Now the comparison is exact: A → B (A happened-before B, i.e. A could have caused B) precisely when every entry of A’s vector is ≤ the corresponding entry of B’s. If some entry of A is bigger and some entry of B is bigger, neither could have known about the other, so they are concurrent — no causal order exists. This is strictly more informative than a single Lamport counter, which can order concurrent events but can’t tell you they were concurrent.

Local event: bump your own entry

When a process does something locally, it increments only its own position in its vector. Nothing else changes.

Send: attach your vector

Sending a message counts as a local event (bump your entry), and the message carries a copy of your updated vector to the receiver.

Receive: merge by max, then bump

On receive, set each entry to the max of your value and the message’s value (adopting everything the sender knew), then bump your own entry for the receive.

✓

Compare to order events

A happened-before B iff A’s vector ≤ B’s in every entry. If neither vector dominates the other, the two events are concurrent — there is no causal relationship between them.

Detects

happened-before

Detects

concurrency

Merge rule

element-wise max

vs Lamport

more precise

The code

# vector clock at process p (of n processes) V = [0] * n def local_event(): V[p] += 1 # bump own entry def send(): V[p] += 1 return list(V) # attach vector to message def receive(msg_V): for i in range(n): V[i] = max(V[i], msg_V[i]) # adopt sender's knowledge V[p] += 1 # A -> B (caused) iff all(A[i] <= B[i]); else concurrent

Quick check

1. What does a process do to its vector on a local event?

2. How does a process update its vector when it receives a message?

3. Two events have vectors [2,1,0] and [1,0,2]. What is their relationship?

FAQ

What is a vector clock?

A mechanism for capturing the causal (happened-before) ordering of events with no shared clock. Each of n processes keeps a vector of n counters, bumps its own on each event, attaches it to messages, and merges incoming vectors by element-wise max. Comparing vectors reveals causal precedence or concurrency.

How do vector clocks differ from Lamport clocks?

A Lamport clock is one counter: A→B implies timestamp(A)

What are vector clocks used for?

Detecting conflicting concurrent writes in eventually-consistent stores (Dynamo, Riak use version vectors to flag conflicts for reconciliation), ordering messages, enforcing causal consistency, distributed debugging/snapshots, and as a basis for many CRDT designs.

What is the downside of vector clocks?

Each timestamp is O(n) in the number of processes, so vectors grow large at scale and can accumulate stale entries with dynamic membership. Practical systems use variants — version vectors, dotted version vectors, interval tree clocks — to bound the overhead while keeping causality tracking.

Keep going

Finished this one? 0 / 61 Labs done

Explore the topic

See this alongside everything else on the same subject — handbooks, system designs, challenges and tools, in one place.

Distributed Systems

Who Caused What.

How it works

Local event: bump your own entry

Send: attach your vector

Receive: merge by max, then bump

Compare to order events

The code

Quick check

FAQ

Keep going

Explore the topic

More Labs

Explore more from Vibe Engines

How it works

Local event: bump your own entry

Send: attach your vector

Receive: merge by max, then bump

Compare to order events

The code

Quick check

FAQ

Keep going

CRDT Merge →

Gossip Simulator →

CP vs AP Databases →

Consensus & Coordination →

Explore the topic

More Labs

Explore more from Vibe Engines