Vector Clocks Fundamentals
You'll learn how vector clocks use an array of logical counters—one per process—to capture causality and detect when events truly happen concurrently.
The Problem with Lamport Timestamps
Lamport timestamps let us order events, but they have a critical limitation: if event A has a smaller timestamp than event B, we can't be sure whether A caused B or they happened concurrently. We can only say "A might have caused B."
How Vector Clocks Work
A vector clock is an array of counters, one for each process in the system. Each process maintains its own vector that tracks:
- Its own event count (in its position)
- What it knows about every other process's event count
Think of it like each friend in a group chat keeping a tally: "I've sent 5 messages, Alice has sent 3 that I've seen, Bob has sent 7 that I've seen..."
Key Operations
- Local event: Increment your own counter
- Send message: Increment your counter, attach entire vector to message
- Receive message: Take the element-wise maximum of your vector and received vector, then increment your own counter
Detecting Causality and Concurrency
Vector clocks let us compare two events definitively:
- Event A happened before B if every counter in A's vector ≤ B's vector (and at least one is strictly less)
- Events are concurrent if neither vector is less-than-or-equal to the other
This is like comparing version histories: if you've seen everything I have (plus more), you're "ahead." If we each have changes the other hasn't seen, we're concurrent.
Key Takeaway: Vector clocks represent the causal history of each event as a vector of counters (one per process), enabling precise detection of causality and true concurrency—solving the ambiguity Lamport timestamps leave behind.