We use analytics cookies.We use cookies to analyze site traffic and improve your experience.
Loading...
2 system design questions lean on this idea. Each walks through the full answer.
System Design Masterclass · Distributed Systems Core
Free preview: the first 2 parts of this 9-part lesson.
Already bought the course? Sign in to read the whole lesson.
this lesson is part of
System Design Masterclass
Unlock this lesson and the 751 other paid lessons
$25 once, by PayPal
See the System Design courseread the rest of this lesson in
System Design Masterclass
Unlock this lesson and the 751 other paid lessons
$25 once, by PayPal
See the System Design coursein Distributed Systems Core
This lesson is part of the full System Design Masterclass. Unlock it along with 769 other lessons for a one-time payment.
One-time payment by card or PayPal
Get Lifetime AccessOne-time payment: UPI, card or netbanking
Get Lifetime Access18 Foundation lessons are free, no payment needed. Try them now
It is easy and good
“It is really nice and good Please join the course”
In the last lesson, you learned that Lamport timestamps tell you: if A happened-before B, then timestamp(A) < timestamp(B). But the reverse isn't true. If timestamp(A) < timestamp(B), you can't tell whether A actually caused B or whether they were completely independent events on different nodes.
Why does that matter? Consider an e-commerce system. User Alice updates her address from New York to Boston on Node A. Simultaneously (truly simultaneously, no causal connection), user Bob updates his address from London to Manchester on Node B. Lamport timestamps will assign an arbitrary ordering to these events. But they're not causally related at all. Ordering them is meaningless and potentially misleading.
Now consider a different scenario: Alice places an order on Node A, and the inventory system on Node B decrements stock in response. These events are causally related, the order caused the stock decrement. Here, ordering matters.
Vector clocks let you distinguish between these two scenarios. They tell you not just "A < B" but whether A caused B, B caused A, or neither caused the other (they're concurrent). This distinction is essential for conflict resolution in systems like DynamoDB, Riak, and any multi-master scheme.
Colin Fidge and Friedemann Mattern independently invented vector clocks in 1988, a decade after Lamport timestamps. They're more expensive (an array of N integers instead of one), but they give you the complete causal picture.
Instead of one counter per node, each node maintains an array of N counters, one per node in the system.
Node A maintains: [A's count, B's count, C's count] Node B maintains: [A's count, B's count, C's count] Node C maintains: [A's count, B's count, C's count]
The rules mirror Lamport timestamps, but operate on vectors:
Rule 1 (local event): Increment your own position in the vector.
Rule 2 (send): Increment your own position, attach the vector to the message.
Rule 3 (receive): Take the element-wise maximum of your vector and the received vector, then increment your own position.
Comparing vectors:
| Comparison | Meaning | Example |
|---|---|---|
| [2,1,0] < [2,2,0] | First happened before second | Causal: event 1 influenced event 2 |
| [2,1,0] || [1,2,0] | Concurrent | Independent: neither influenced the other |
| [2,2,1] < [3,2,1] | First happened before second | Causal chain |