Systems · Distributed

Who Caused What.

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.

1

Local event: bump your own entry

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

2

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.

3

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 / 44 Labs done

Explore the topic

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

More Labs