Lamport Clock
- Enforce causal relationship (happened before) between events
- Cannot imply (capture) happened before due to scalar value of Lamport clock
- Happened before is a partial order (vs. total order)
Shortcoming
- The important rule is only: a -> b => C(a) < C(b)
- The reverse is not guaranteed: C(a) < C(b) is not necessarily a -> b
A smaller timestamp doesn’t prove that one event caused or influenced the other.
Example: different timestamps, but no causality
P1 P2
a C(a)=1 x C(x)=1
|
y C(y)=2
|
z C(z)=3
There are no messages between P1 and P2.
We have:
C(a)=1 < C(z)=3
But a didn’t cause z and no information traveled from P1 to P2.
Therefore,
a || z even though C(a) < C(z)
This is the central limitation of Lamport clocks:
They preserve known causal order, but timestamp order by itself does not reveal whether causality exists.
Therefore,
a -> b => C(a) < C(b)
But C(a) < C(b) doesn’t necessarily imply a -> b; the events may instead be concurrent.
”Enforcing” causality vs “capturing” causality
This distinction is important.
Lamport clocks enforce causality
They make sure causal events are timestamepd in the correct direction:
If a caused b:
timestamp(a) < timestamp(b)
Lamport don’t capture causality
Given only:
timestamp(a) = 3
timestamp(b) = 8
You can’t determine which of these is true:
Possibility 1: a → b
Possibility 2: a || b
Becuase both situations can produce C(a) < C(b).
So a Lamport clock can answer:
“If I already know that a -> b, are their timestamps consistent?”
But it cannot reliably answer:
“Looking only at these timestamps, did a cause b?”
Higher Replica ID Wins (Artificial total ordering)
Lamport clocks can create a total order by adding a process ID.
Suppose:
Event a: timestamp (1, P1)
Event b: timestamp (1, P2)
If P1 < P2, the system declares:
(1, P1) < (1, P2)
and therefore places a before b, which results in a => b.
But that doesn’t mean: a -> b
The events may still be concurrent. The process ID merely breaks the tie so that every machine agrees on one ordering.
A total ordering can be helpful when merge resolution is required.
Here, => means:
“The system has chosen to place (a) before (b).”
In summary,
A Lamport clock records enough information to avoid violating causality, but not enough information to reconstruct causality. It cannot distinguish “a caused b” from “a and b were unrelated but happened to receive ordered clock values.”
Vector Clock
Instead of one number a Lamport clock utilizes, a vector clock stores one number per process.
For three processes:
V = [v1, v2, v3]
Each component represents the process’s knowledge of events from a particular process.
Suppose:
V(a) = [2, 0, 0]
and:
V(b) = [2, 3, 0]
Every component of V(a) is less than or equal to the corresponding component of V(b), and the vectors are different.
Therefore, V(a) < V(b)
With vector clocks, we can capture the causality: a -> b
But suppose:
V(a) = [2, 0, 0]
and:
V(b) = [0, 3, 0]
The first component is larger in V(a), but the second component is larger in V(b). Neither vector is smaller than the other.
Therefore they are incomparable:
V(a) || V(b)
This tells us that the events are concurrent.
Therefore, vector clcoks have stronger rules:
V(a) < V(b) => a -> b
and:
V(a) || V(b) => a || b
Final Comparision
| Observation | Lamport clock | Vector clock |
|---|---|---|
| If a -> b, timestamp of a is smaller | Yes | Yes |
| If timestamp of a is smaller, conclude(a -> b) | No | Yes |
| Detect concurrent events | No | Yes |
| Timestamp size | One integer | One integer per process |
| Can create a simple total order | Yes | Not naturally |