Distributed systems time, causality, and ordering explained
Learn happens before, Lamport and vector clocks, causal consistency, clock uncertainty, HLCs, and TrueTime style APIs.
The whole story in 15 lines
Distributed time is a toolbox: track causes logically, expose uncertainty physically, and pay for stronger order only when the promise...
- Happens before follows local sequence and messages while independent events stay concurrent.
- Partial order preserves only proven relationships while total order adds a deterministic sequence.
- Lamport clocks make every causal arrow point from a smaller scalar to a larger one.
- A larger Lamport value does not prove causation because concurrent events also receive different numbers.
- Vector clocks merge known history component by component and increment the local component.
- Opposing vector components prove that neither event contains the other event history.
- Exact causal comparison costs one vector component for every tracked participant.
- Version vectors discard dominated object versions and preserve concurrent siblings.
- Causal consistency records the dependencies an operation observed before creating an effect.
- A replica buffers a dependent effect until its local causal frontier satisfies every dependency.
- Bounded clock error turns one physical reading into an interval of possible real times.
- HLC pairs a near-wall-time value with a logical counter that advances on ties.
- When physical time retreats, the HLC logical part keeps causal timestamps moving forward.
- A TrueTime style API exposes bounds and waits out uncertainty before making a commit observable.
- Choose the weakest order that proves the product promise because stronger order costs coordination.
Setup
Imagine three replicas recording events without one perfect shared clock. Our mystery is how to recover the order that matters without pretending we know more than we do.
An event is one local action and “Happens before” means one event could affect another. Concurrent events have no path of cause and effect between them.
Logical time tracks causal progress and physical time estimates real clock time, and uncertainty tells us how far that estimate might be from reality.
We will build each kind of clock, then test its limits. This way, every clock gets one clear job instead of becoming a vague idea of time.
Each tool answers a different ordering question, so let us begin with the order that the execution itself can actually prove.
Happens Before
We separated cause from clock time, so now follow three lanes for replicas A, B, and C. Moving downward follows each replica's own program order.
Replica A edits some data and then sends a message. Because its program performs those actions in order, the edit happens before the send.
Replica B receives that message before editing its own copy. The message joins two lanes, creating a causal path from A's edit through B's edit.
Replica C edits while disconnected, leaving no message between its work and B's edit. Which relationship can the execution evidence actually support?
No order is provable because neither edit can reach the other through local steps or messages. The two open branches therefore represent genuine concurrent work.
Happens before gives us a partial order that keeps only proven causal influence. Next, we will compare it with a total order that forces every event into one sequence.
Partial vs Total Order
Happens before left one fork unresolved, so let us show the same events two ways. One view preserves causality while the other chooses a replay sequence.
The partial graph keeps every relationship we can prove. Its two open branches matter because those concurrent events may move forward independently without coordination.
Some protocols still need one exact replay sequence even when causality is silent. What extra relationship must they add between the concurrent tips?
The total order adds a policy edge between the branch tips. That edge gives every replica one deterministic replay, but it does not create new causal evidence.
Switch the Tie break control through both policies. Compare which branch enters the replay first while the original causal fork remains unchanged.
A total order gives us an extra replay guarantee by adding policy to causality. Next, we will build a small logical number that preserves every proven causal direction.
Lamport Clock Rules
The causal graph is accurate, but carrying the whole graph is bulky. A Lamport clock gives each replica one integer that rises for every local event.
Replica A labels its edit 1 and its send 2. The outgoing message carries timestamp 2, preserving evidence about the work that happened before it.
The message can arrive on either side of B's independent local work while still carrying timestamp 2. Transport time changes arrival, not the sender's recorded history.
Replica B's clock is 0 when timestamp 2 arrives. Which receive value will remain strictly later than the send event?
B takes the larger value, 2, and adds one. The receive becomes 3, then B's next local edit becomes 4, keeping the entire causal path increasing.
Switch the Message delay control between Short and Long. Watch the receive cross B's local work while the maximum plus one rule remains unchanged.
Lamport clocks guarantee that causes receive smaller values than their effects. Next, we will test the tempting reverse claim and discover what scalar timestamps cannot prove.
Lamport Clock Blind Spot
Lamport gave us a guarantee in one direction, from causality to increasing values. Here two events carry different scalars, so we ask what those numbers alone prove.
For a causal pair, the message path and scalar order agree. The path proves influence while the values merely preserve its direction in a compact form.
Now remove the message path but keep values 1 and 4. Does the smaller scalar prove that the first event caused the second?
The answer is no because scalar order survives after the causal path disappears. Lamport clocks therefore cannot distinguish concurrent events from causally related events.
Switch the Pair control between Causal and Concurrent. Compare the downstream verdict as the same scalar inequality gains or loses its causal path.
A scalar preserves causal direction but cannot recover the underlying causal structure. That missing distinction matters during conflict handling. Next, each replica gets its own vector component so opposing histories can remain distinguishable.
Building a Vector Clock
The Lamport blind spot came from compressing every history into one scalar. A vector keeps separate counters for A, B, and C, preserving who contributed each event.
A increments only its own component, so its edit becomes [1,0,0] and its send becomes [2,0,0]. The other cells remain zero because A has learned nothing from B or C.
B already has its own local vector when A's message arrives. Which merge rule keeps everything either side has already observed?
B takes the componentwise maximum and then increments B's cell. The resulting vector carries A's history forward while recording B's new receive event.
Switch the Message control between Delivered and Lost. Inspect B's result to see whether A's two events survive in the downstream history.
A vector is a compact causal history with one counter per participant. Next, we will compare two histories and let opposing components reveal concurrency directly.
Comparing Vector Clocks
★ If you remember one thing · Vector clocks expose concurrency that a scalar Lamport clock hides.
We built vectors by merging history, and now B's edit and C's edit use the same encoding. Their relationship can be compared one component at a time.
B knows about A and B while C knows only about itself. Neither vector contains the complete history stored by the other event.
A scalar clock still places one event first, but that sequence alone cannot expose the histories hidden inside both values.
Compare each matching vector cell before accepting the scalar order. What relationship will opposing component directions reveal?
One history leads in A and B while the other leads in C. Those opposing directions expose concurrency that the single scalar sequence hid.
Switch the Pair control between Concurrent and Causal. Compare whether opposing cells remain or one complete vector dominates the other.
Vectors recover exact causal comparison by preserving separate histories. Next, we will see why that accuracy costs more metadata as the participant set grows.
Vector Clock Cost
Exact causal knowledge is not free because each tracked participant needs a stable cell in every full vector timestamp. That identity mapping must remain consistent across replicas.
A single event increments one cell, but its timestamp still carries every known component. Another replica needs the complete set to compare both histories exactly.
Now imagine the participant set growing beyond three replicas. What happens to the timestamp attached to every event?
The timestamp widens linearly even though one event changes only one component. Exact comparison therefore charges every event for the size of its participant set.
Adjust the Participants control once, then inspect the metadata result. Notice when the vector crosses from compact history into a visibly wider causal record.
Vectors buy exact causality with metadata that grows alongside every tracked identity. Each message pays that size cost. Next, version vectors apply the same comparison to one replicated object and its conflicting values.
Version Vectors
Vector clocks label individual events, while a version vector labels one object's accumulated history. A replicated store can therefore compare values before discarding either one.
A creates [1,0,0], then B receives that history and edits it to [1,1,0]. B safely supersedes A because its vector contains every component from A.
C edits its isolated copy and creates [0,0,1] without learning the A to B branch. A network partition has allowed both histories to grow independently.
The replicas reconnect and compare the two branch tips. Which version can they discard without silently losing an edit?
Neither branch can be discarded because the versions are concurrent siblings. Keeping both values prevents the store from turning an unseen conflict into silent data loss.
Switch the Network control between Partitioned and Connected. Compare whether the result keeps concurrent siblings or collapses into one safe causal successor.
Version vectors preserve conflicting histories until application logic can reconcile their values. Next, we will turn one observed history into an explicit dependency between operations.
Causal Dependencies
Version vectors told us which histories contain others. Causal consistency begins when a new operation records the history its creator had already observed.
A publishes a post, then B reads it before writing a comment. The comment therefore depends on the post because that cause shaped the later effect.
Network paths may deliver the smaller comment before the larger post. Raw arrival order now disagrees with the dependency captured when B wrote the comment.
A reader requests the feed while only the comment has arrived. May the effect become visible before the cause it answers?
Causal delivery holds the comment until its post is visible. That short wait prevents a reader from observing an effect whose required cause is still missing.
Switch the Delivery control between Arrival order and Causal. Compare whether the downstream feed exposes an orphaned comment or preserves cause before effect.
A dependency records what must wait rather than ordering everything globally. Next, we will open the replica and see its causal frontier enforce that precise rule.
Causal Delivery
The last stage named a dependency, and now this replica tracks applied history in a frontier vector. The frontier summarizes everything currently safe for readers.
When the effect arrives first, its required A component is ahead of the frontier. The replica keeps that operation hidden inside a holding buffer.
The missing cause arrives and advances the frontier to satisfy every required component. What can the replica safely do next?
The dependency gate opens and the effect drains into the visible log. Concurrent operations remain free because the replica waited only for recorded causal history.
Switch the Arrival control between Effect first and Cause first. Compare whether the effect waits in the buffer or applies immediately after arrival.
Causal delivery precisely preserves dependencies without globally ordering unrelated concurrent work. Independent updates can still flow freely between replicas. Next, we will ask physical clocks to expose what they truly know about real time.
Clock Uncertainty
Causal clocks avoid wall time, but systems still need near-real timestamps for expiry, snapshots, and external ordering. Physical time answers a different operational question.
Replica clocks drift while synchronization messages take time. Each displayed reading is therefore an illustrative estimate placed around one shared real-time axis.
An honest clock API pairs every reading with plus or minus epsilon. That error bound describes all real times still compatible with the local estimate.
Two center points look ordered, but their uncertainty intervals overlap. Can these physical readings prove which event actually happened first?
The answer is no because either real order still fits the bounded evidence. Only separated intervals can prove that one physical event definitely preceded another.
Switch the Uncertainty control across Tight, Typical, and Wide. Notice when shrinking error separates the intervals and turns an unprovable order into physical evidence.
Uncertainty is useful because it states what a physical clock cannot prove. Next, we will build a fixed-size timestamp that stays near wall time and preserves causality.
Building an HLC
Clock intervals describe uncertainty, but many storage paths still need one sortable timestamp. A hybrid logical clock uses a wall value plus a logical counter.
When physical time advances, the wall component follows it and the logical component resets. The pair remains close enough to wall time for operational use.
Now a received timestamp matches the local wall component exactly. How can the next event remain strictly later than both known histories?
The logical component increments when physical time cannot advance. That second field prevents equal wall readings from collapsing distinct causal events into one timestamp.
Switch the Physical clock control between Advances and Ties. Compare whether the wall field or the logical field carries the resulting timestamp forward.
HLC stays near wall time while preserving causal monotonicity in one practical fixed-size pair. The pair remains sortable across replicas. Next, we will disturb the operating-system clock by moving it backward.
HLC Under Clock Jumps
We just built the two-part timestamp, and now A sends its HLC pair to B. This stage tests that same update rule under a disturbed physical clock.
A's local event and send follow physical time. The message carries the complete wall and logical pair across the network as causal evidence.
B receives that pair and first chooses the greatest wall component. It then updates the logical component according to every value tied at that maximum.
The operating system corrects B's wall clock backward after the receive. Will the next HLC timestamp retreat too?
The HLC timestamp does not retreat. Its wall part holds the greatest known value while the logical part rises, preserving order along the entire causal path.
Switch the Clock jump control between Stable and Backward. Compare whether wall time or logical repair keeps the downstream causal timestamp increasing.
HLC repairs causal progress inside a fixed-size timestamp, but it does not expose physical uncertainty. Next, an interval API will make that uncertainty available to transaction logic.
TrueTime Style APIs
HLC hides clock trouble inside a sortable pair, while a TrueTime-style API exposes uncertainty as [earliest, latest]. Transaction logic can now reason about those bounds directly.
Transaction one chooses the latest bound as its commit timestamp. That value may still be slightly ahead of real time because the interval has not collapsed.
Commit wait can keep the transaction hidden while the earliest possible current time remains behind its chosen timestamp. The system converts bounded uncertainty into bounded delay.
Transaction two starts after transaction one returns to its caller. What stops their possible timestamp intervals from crossing?
Commit wait keeps transaction one hidden until its timestamp is definitely past. Only then can a later caller begin beyond that timestamp and preserve external order.
Toggle the Commit wait control through both states, then solve the challenge. Compare overlapping intervals with the safely separated external-order result.
The API spends bounded waiting to guarantee external real-time order. Next, we will decide which product promises deserve metadata, coordination, or this uncertainty cost.
Choosing an Ordering Guarantee
We now have logical clocks and bounded physical time. The final design choice starts with the user-visible behavior that an application must actually guarantee.
Causal order protects dependencies, total order supports deterministic replay and replicated decisions, and external order follows real-time completion across transactions.
Stronger evidence costs metadata, coordination, or waiting. Should every system pay for external order when its product never exposes that promise?
The best choice is the least costly evidence that still proves the product promise. Stronger order cannot justify its coordination cost when users cannot observe it.
Switch the Guarantee control across Causal, One sequence, and External. Compare which downstream cost buys the evidence required by each distinct promise.
Ordering is a product design choice rather than one universal clock. The right evidence follows the promised user behavior. Now let us reconnect all fifteen technical lessons into one practical toolbox for real distributed systems.
Recap
We started with happens before and kept only relationships proven by local order or messages.
Then partial order preserved honest concurrency while total order inserted deterministic tie breaks for replay.
Lamport rules compressed causal direction into one rising scalar that travels cheaply with messages everywhere.
Its blind spot showed that unequal scalars alone do not prove a causal path between events.
Vector construction restored separate participant counters and merged known history carefully component by component again.
Vector comparison used opposing components to identify concurrent events honestly without inventing any artificial order.
The cost stage made one component per tracked participant appear as growing event metadata everywhere.
Version vectors applied causal comparison to object versions and preserved concurrent siblings without losing edits.
Causal dependencies recorded the complete history that an effect had already observed before its creation.
Causal delivery buffered an early effect until the visible frontier finally contained its required cause.
Clock uncertainty turned one suspicious physical point into an honest interval of possible real times.
HLC construction paired near-wall time with a logical counter that repairs equal physical readings.
HLC repair kept causal timestamps rising safely through a sudden backward operating-system clock jump.
A TrueTime-style API exposed physical bounds and waited until external transaction order became safe.
The final decision map chose causal, total, or external order from the actual product promise.
The unified lesson is simple: preserve causes, admit concurrency, expose uncertainty, and pay for stronger order only when users need it.
The whole story in 15 lines
Distributed time is a toolbox: track causes logically, expose uncertainty physically, and pay for stronger order only when the promise...
- Happens before follows local sequence and messages while independent events stay concurrent.
- Partial order preserves only proven relationships while total order adds a deterministic sequence.
- Lamport clocks make every causal arrow point from a smaller scalar to a larger one.
- A larger Lamport value does not prove causation because concurrent events also receive different numbers.
- Vector clocks merge known history component by component and increment the local component.
- Opposing vector components prove that neither event contains the other event history.
- Exact causal comparison costs one vector component for every tracked participant.
- Version vectors discard dominated object versions and preserve concurrent siblings.
- Causal consistency records the dependencies an operation observed before creating an effect.
- A replica buffers a dependent effect until its local causal frontier satisfies every dependency.
- Bounded clock error turns one physical reading into an interval of possible real times.
- HLC pairs a near-wall-time value with a logical counter that advances on ties.
- When physical time retreats, the HLC logical part keeps causal timestamps moving forward.
- A TrueTime style API exposes bounds and waits out uncertainty before making a commit observable.
- Choose the weakest order that proves the product promise because stronger order costs coordination.