We wanted timestamps to tell us what happened first. Then the clocks disagreed. The useful question turned out not to be “What time was it?” but “What could have caused what?”
"How distributed systems reason about time without a shared clock, from physical clock synchronization and NTP to Lamport clocks, happened-before, vector clocks, causal ordering, and concurrency."
Two processes perform two events.
We need to know which happened first.
This does not initially feel like a distributed-systems problem. It feels like a clock problem.
Record the time.
Compare the timestamps.
✨Done✨
Suppose X sends an email titled “meeting.” Y and Z receive it and each send a reply titled “Re: meeting.”
The causal story seems obvious:
X sends "meeting"
↓
Y receives it → Y replies
↓
Z receives it → Z replies
Now user A receives those messages through independent network paths.
Perhaps one reply arrives before the original message.
Perhaps Z’s reply arrives before Y’s.
Arrival order is not necessarily event order.
Fine.
Put timestamps on the messages and sort them.
The clock will rescue us.
That works beautifully until we ask a dangerous question:
Whose clock?
Every Machine Brings Its Own Version of Now
Processes in a distributed system run on different computers.
Each computer has a physical clock.
Those clocks are built from oscillators that count time, and physical oscillators are not perfectly identical.
One runs slightly fast.
Another runs slightly slow.
Temperature and hardware variation introduce small differences in their rates.
Those tiny differences accumulate.
The rate at which a clock moves away from an ideal clock is clock drift.
The instantaneous difference between two clocks is clock skew.
So Machine A might believe the time is: 10:00:00.100
while Machine B believes: 10:00:00.080
Nothing has crashed.
Nobody is lying.
Both clocks are simply doing their best with slightly different hardware.
And this is where our timestamp intuition becomes uncomfortable.
If event a on Machine A has timestamp 10:00:00.100 and event b on Machine B has timestamp 10:00:00.080 , can we safely conclude that b happened first?
Not unless we know how well those clocks agree.
The number printed on the event is only as trustworthy as the synchronization behind it.
The File Can Travel Backward in Time
The problem becomes wonderfully concrete with something as ordinary as make.
A build tool can decide whether a source file needs recompiling by comparing timestamps.
Suppose: output.c is edited on one machine.
Its corresponding: output.o was compiled on another.
Normally, if the source file is newer than the object file, make recompiles it.
Reasonable.
Now let the compiler machine’s clock run ahead of the editing machine’s clock.
The old output.o receives a timestamp that appears to be later than the newly edited output.c.
From the timestamp’s point of view:
Nothing to see here. The object file is newer.
So the modified source may not be recompiled.
The build system is behaving correctly according to the timestamps.
The timestamps are behaving correctly according to their local clocks.
And the result is wrong.
The system is not broken.
Our assumption that physical timestamps create a trustworthy global order is.
Fine. Synchronize the Clocks
The obvious repair is equally reasonable.
If independent clocks drift apart, synchronize them.
There are two broad goals.
With external synchronization , clocks are aligned with an external time standard such as UTC.
With internal synchronization , the machines may not know perfect real time, but they try to stay close to one another.
Now network communication enters the calculation.
Suppose one process sends its current clock value t to another.
If we knew that message transmission always took somewhere between: min
and: max
then the receiver would know that the sender’s time had advanced by somewhere inside that interval while the message travelled.
Setting the clock to: t + (max + min) / 2
minimizes the worst-case uncertainty to roughly half the transmission-time range.
That is workable under a synchronous distributed-system model , where useful upper and lower bounds exist for process execution, message delivery, and clock drift.
Then we move onto the Internet.
And the upper bound gets stage fright.
The Network Will Not Promise How Late It Can Be
An asynchronous distributed-system model assumes no known bounds on:
- process execution speed,
- message transmission delay,
- clock drift rate.
That model is much less comforting.
It is also much closer to the Internet.
A synchronization message takes some amount of time to travel.
There is a minimum physical cost.
Then there is everything else.
Queueing.
Congestion.
Scheduling delays.
Routing variation.
An inconveniently busy machine.
The receiver does not know exactly how much of the observed delay belongs to clock difference and how much belongs to the network being the network.
So perfect physical-clock synchronization becomes surprisingly expensive.
Protocols such as Network Time Protocol , or NTP, manage this uncertainty rather than eliminating it. NTP organizes time servers hierarchically, with primary servers synchronized to reference clocks traceable to UTC and lower strata synchronizing through upstream servers; it also uses measured network delay and filtering algorithms to improve clock synchronization over real networks.
That is extremely useful.
We absolutely still want physical time.
Logs need timestamps.
Certificates expire.
Users schedule meetings.
Billing periods end.
But a new realization has appeared:
Perhaps accurate wall-clock time is not actually what we need to solve event ordering.
That changes the problem.
Stop Asking “What Time?” for a Moment
Consider a single process.
If event a occurs, then event b occurs afterward in that same process, their order is unambiguous.
We can say: a --> b
Now suppose process P sends a message m to process Q.
The send must happen before the receive.
So: send(m) --> receive(m)
No synchronized physical clocks were required to establish either fact.
We know them from the structure of the computation itself.
Leslie Lamport took these simple observations and generalized them into the happened-before relation , a partial ordering of events in a distributed system. His 1978 work formalized this causal view of distributed events and introduced logical clocks to represent it.
The rules are beautifully small.
If two events occur in the same process and a occurs before b : a --> b
If a message is sent at a and received at b : a --> b
And if: a --> b
and: b --> c
then: a --> c
That last rule gives us transitivity.
Now we have a way to talk about order without pretending every machine shares one physical clock.
We are no longer measuring time.
We are measuring potential causality.
Some Events Refuse to Be Ordered
This model gives us something physical timestamps made easy to overlook.
Suppose event a occurs in Process 1.
Event e occurs independently in Process 3.
No message connects them.
No chain of events connects them.
Neither: a --> e nor: e --> a is true.
Then the events are concurrent : a || e
This does not necessarily mean they happened at precisely the same physical instant.
It means something more useful:
We have no causal relationship that requires one to precede the other.
This is a subtle shift.
Our original instinct wanted every pair of events arranged on one giant timeline.
The distributed system is telling us:
Some events genuinely do not need an order.
A partial order is enough to describe causality.
That is less information than a universal timeline.
It is also more honest.
Lamport Gives Causality a Number
Reasoning directly with arrows is useful.
Algorithms would prefer something numerical.
So each process maintains a Lamport logical clock.
It is not a wall clock.
It does not know T_uesday_.
It does not know 14:37.
It is just a monotonically increasing software counter.
Each process Pi keeps a logical clock: Li
Before recording an event: Li = Li + 1
When Pi sends a message, it attaches its current logical timestamp to that message.
Suppose the message arrives at Pj carrying timestamp t.
The receiving process updates its logical clock using:
Lj = max(Lj, t); Lj = Lj + 1;
before timestamping the receive event.
This simple rule makes the receiving process acknowledge something important:
If this message came from another event, my receive event cannot logically exist before that event.
The clocks are not trying to stay equal.
They are trying to preserve causality.
And they give us a powerful guarantee: e --> e' ==> L(e) < L(e')
If one event happened-before another, its Lamport timestamp will be smaller.
The clocks finally give us order without asking the quartz crystals to agree.
Then We Read the Equation Backward
This is where Lamport timestamps become dangerously seductive.
We know: e --> e' ==> L(e) < L(e')
It is very tempting to conclude: L(e) < L(e') ==> e --> e'
No.
That implication does not hold.
Two concurrent events can still receive different Lamport timestamps.
For example: L(b) = 5 L(e) = 8
does not prove that: b --> e
The events might have no causal relationship whatsoever.
Lamport clocks guarantee that causality is respected by the numbers.
They do not guarantee that every numerical ordering represents causality.
The clock can say:
5 comes before 8.
It cannot necessarily say:
Event 5 caused, influenced, or preceded Event 8 through the distributed computation.
The counter has enough information to preserve causal order.
It does not have enough information to reconstruct all causal relationships.
The distinction looks tiny on paper.
It is the reason we eventually need another clock.
But first, Lamport’s weaker guarantee turns out to be surprisingly useful.
Sometimes We Really Do Need Everyone to Pick an Order
Consider a bank account database replicated in Place A and Place B.
The Origami Software Engineer has: $ 1,000.00
He deposits: $ 100.00
At approximately the same time, banking application applies: 1% interest
Both updates must eventually reach both replicas.
Now communication delay changes their arrival order.
Place A applies the deposit first: (1000 + 100) x 1.01 = 1111
Place B **applies the interest first: (1000 + 100) + 100 = 1110**
Every operation was valid.
Every replica received both operations.
They still disagree.
The problem was order.
For replicas to remain consistent, both updates must be applied in the same order everywhere.
So now we need more than causal relationships.
We need a total order.
Lamport timestamps can be extended for this purpose.
If two events have the same logical timestamp, include the process identifier as a deterministic tie-breaker: (Ti, i)
Then compare by logical time first and process ID second.
The process IDs have no deep physical meaning.
That is fine.
We are not trying to discover universal truth.
We are trying to ensure everybody makes the same deterministic choice.
Totally Ordered Multicast Turns Time Into Coordination
That leads naturally to totally ordered multicast.
The requirement is simple to state:
Every receiving process must deliver multicast messages in the same order.
Not merely receive them eventually.
Not merely preserve each sender’s local order.
The receivers must agree on one delivery sequence.
A Lamport-based solution gives each multicast message a logical timestamp.
Every process stores received multicasts in a queue ordered by timestamp.
Acknowledgements are themselves timestamped.
A process only delivers the message at the head of the queue after it knows, through acknowledgements, that no smaller timestamped message is still going to arrive and take its place.
The logical clocks have become coordination machinery.
And notice what happened.
We originally wanted clocks because we thought we needed to know the actual time.
Now their most important job is ensuring that independent machines make compatible decisions about ordering.
Wall-clock accuracy has become almost irrelevant.
Consistency is the thing we were _really _chasing.
Lamport’s Clock Knows That Something Came Before, but Not Why
Then another question appears.
Suppose we have two events with: L(a) < L(b)
Are they _causally _related?
We already know we cannot tell.
That limitation matters when the system needs to distinguish:
“This event depends on that one.”
from:
“These events happened independently.”
A scalar Lamport timestamp has compressed too much information.
Each process keeps only one number.
When it receives information from another process, it moves that number forward.
The history gets summarized.
Useful causal detail disappears.
So the next step is almost forced.
If one number does not preserve enough information about what each process knows…
keep more than one number.
Vector Clocks Remember Who Knows What
A vector clock gives each process a vector rather than one scalar counter.
For three processes: [0, 0, 0]
Each position represents one process.
Process 1 tracks its knowledge like: [P1, P2, P3]
When Process 1 performs an event, it increments its own component.
When it sends a message, it includes the entire vector.
When another process receives that message, it merges the received knowledge with its own by taking the component-wise maximum , then updates its own entry.
So if a process currently knows: [3, 1, 0]
and receives: [2, 4, 1]
the merged knowledge becomes: [3, 4, 1]
The vector is effectively saying:
Here is how much of each process’s history I know about.
Vector clocks were developed to capture causal relationships more completely than Lamport’s scalar clocks; they preserve enough per-process information to distinguish causal precedence from concurrency.
Now something important becomes possible.
The Arrow Finally Works Both Ways
With Lamport timestamps: e --> e' ==> L(e) < L(e')
but: L(e) < L(e') =/=> e --> e'
With vector clocks,
the relationship becomes stronger: e --> e' <==> V(e) < V(e')
The arrow now works in both directions.
To compare vectors: V <= V'
when every component in V is less than or equal to the corresponding component in V'.
And: V < V'
when: V <= V'
and: V =/= V'
If neither vector is less than or equal to the other, the events are concurrent.
For example: V(a) = 2, 1, 0] V(b) = [1, 0, 3)
The first vector knows more about Process 1 and Process 2.
The second knows more about Process 3.
Neither dominates the other.
So: a || b
Now the timestamps do not merely force a convenient numerical sequence.
They capture the difference between:
This came before that
and:
These happened independently.
We paid for that information with larger timestamps.
One scalar became a vector whose size grows with the number of processes.
More knowledge costs more state.
Distributed systems rarely let us keep both the simplicity and the information.
We Never Needed One Perfect Clock
Look back at where this started.
We wanted to answer:
Which event happened first?
So we reached for physical time.
Then clocks drifted.
We synchronized them.
Then message delays introduced uncertainty.
We built protocols such as NTP to keep physical clocks usefully aligned across networks.
But perfect physical synchronization still was not necessary for many of the problems we actually cared about.
So the question changed.
Instead of:
What was the exact global time of this event?
we asked:
What events could have influenced this event?
That gave us happened-before.
Lamport clocks encoded that ordering numerically.
Then scalar timestamps lost too much information to infer causality in reverse.
So vector clocks kept a richer record of distributed knowledge.
The progression is almost annoyingly logical once the hidden constraint is visible.
Physical clocks answer questions about real time.
Lamport clocks help preserve logical order.
Vector clocks reveal causal order and concurrency.
These are different questions.
Trying to force one clock to answer all of them is where the confusion begins.
Time Was Never the Only Thing We Were Measuring
A distributed system does not possess one shared observation point.
There is no single process watching every event occur.
No perfect global clock quietly labels reality in a universally trustworthy order.
Each process sees its own events.
Then messages carry fragments of knowledge between them.
That is the deeper model.
A timestamp is not automatically truth.
It is a statement about what the clock is capable of knowing.
A physical timestamp says:
According to my approximation of real time, this happened then.
A Lamport timestamp says:
My logical history has progressed this far, and I will never place a causal predecessor after its consequence.
A vector timestamp says:
This is what I know about the progress of every process represented in my vector.
Once we understand that, distributed time stops looking like a failed attempt to build a perfect clock.
It becomes something much more useful:
A way to encode relationships between events when no observer can see the whole system at once.
We began by trying to synchronize clocks.
Then we discovered that for many distributed problems, what mattered was synchronizing our understanding of order.
That’s not failure.
That’s evolution.
The “I liked this” Starter Pack:
Don’t let your fingers get lazy now.
- Like : It tells me this was worth writing.
- A Comment: Tell me your thoughts, your favorite snack, or a better title for this blog.
- Boost it: Especially with that one developer who definitely needs this.
Thanks for being here. It genuinely helps more than you know!
— Aaroophan Varatharajan
Find me elsewhere:
- Professional stuff: linkedin.com/in/Aaroophan
- Code stuff: github.com/Aaroophan
- UI stuff: aaroophan.dev/Aaroophan
- Life stuff: instagram.com/Aaroophan
Top comments (0)