Combine a physical component with a causal tie-break
Apply hybrid logical clock updates while distinguishing causal monotonicity, physical-clock assumptions, and finite representation limits.
On this page
The question for today
What you’ll understand
- Update the physical and logical components for local and receive events.
- Interpret tuple order without treating it as proof of causality or elapsed duration.
- Explain why skew bounds, overflow, and restart rules remain operational requirements.
A logical counter preserves known dependencies but can be difficult to correlate with an approximate calendar time. A physical timestamp is recognizable to operators but can move backward or disagree across hosts. Hybrid logical clocks combine a physical-time-like component with a logical tie-break. The combination is useful precisely when its promises remain separate: it can preserve causal timestamp order while closeness to physical time depends on additional clock assumptions. It does not turn uncertain clocks into a globally exact timeline.
Two fields carry different meanings
Represent a hybrid timestamp as a pair (l, c). The first field is a physical-clock-like value; the second counts causal ordering steps when the first field does not advance. Compare pairs lexicographically: compare l first, and compare c only when l matches. Do not add the fields as if both were milliseconds. An implementation might pack them into one integer, but packing is a representation choice requiring enough range for both components. The logical component provides ordering information within a repeated physical value, not a calibrated fractional interval between those events.
For a local or send event, choose the new physical-like component as the maximum of its previous value and the current physical reading. If that choice equals the previous component, increment the logical counter; if physical time has moved strictly ahead, reset the counter to zero. Consequently a backward physical adjustment does not force the hybrid tuple backward. The tuple can continue advancing logically while the physical reading catches up. This is an ordering property, not evidence that the physical clock reading was correct or that an event occurred at the first field's apparent calendar instant.
Merge a remote tuple without dropping its history
On receiving a message, first choose the maximum of the previous local l, the message's l, and the current physical reading. Then choose the counter according to which maximum supplied the value. When both old local and remote l equal the chosen value, increment the maximum of their counters. If only the old local component matches, increment its counter; if only the remote component matches, increment the remote counter. If a strictly newer physical reading wins over both, use zero. Keeping these cases explicit avoids losing a message dependency at equal physical components.
Correct updates ensure that happened-before implies a strictly increasing hybrid tuple. The converse still fails, just as it does for scalar Lamport clocks: two independent events can have different physical-like components without any causal relationship. Equal tuples are possible for concurrent events, so an application needing unique identifiers must add a separately justified uniqueness mechanism. Hybrid clocks also do not encode the full participant-indexed history of vector clocks. Choose them for the ordering and approximate-time properties a protocol actually needs, rather than assuming a compact timestamp can answer every concurrency or conflict question.
Bound physical interpretation and finite counters
A hybrid timestamp can inherit an advanced physical component from a remote host. Bounding how far it differs from local physical time therefore requires synchronization assumptions about the participating clocks and valid inputs. An algorithm cannot promise arbitrary physical accuracy when those assumptions disappear. Operational implementations need a policy for excessive forward readings, restart state, counter exhaustion, and upgrades that change encoding. Silently wrapping a finite logical field to zero at unchanged l violates strict local order. Blindly accepting a far-future component can also leave later timestamps ahead of physical time for an unexpectedly long interval.
Use the modular instrument to inspect only the exhaustion hazard. Reset, set both modulus m=4 and additive step a=1, predict what follows residue three, then Play or Step. The orbit returns to zero at its fourth addition; a fresh comparison requires Reset and re-setting both controls. A real hybrid clock cannot treat that wrapped field as an ordinary increasing counter at the same l. This instrument implements modular addition, not physical readings, receive cases, or a hybrid-clock overflow policy. Use its clear failure of monotonic numerical order to motivate testing the representation alongside the abstract update rules.
Work it through
Keep order through equal and advancing physical values
A host has hybrid state(1000, 4), receives message(1000, 7), and currently reads physical time 999 ms. It next makes a local event at physical 1001 ms, then receives message(1050, 2) at physical 1002 ms. Treat first components as integer milliseconds in one illustrative epoch.
For the first receive, the maximum physical-like component is 1000 and both local and message components match. The new counter is max(4, 7)+1=8, yielding(1000, 8).
At the local event, physical 1001 is newer than local 1000. The new pair is(1001, 0), which is lexicographically later despite its smaller counter.
For the final receive, remote 1050 exceeds local 1001 and physical 1002. Increment the remote counter to 3, producing(1050, 3). The advanced first component reflects learned remote time, not a new proof of physical accuracy.
The resulting pairs are(1000, 8), (1001, 0), and(1050, 3). The counter resets only when a newer first component makes that reset compatible with tuple order.
The living notebook
Explore the model
Interactive lab · modular
A wrapped tie-break is no longer increasing
Reset, set both m=4 and additive step a=1, predict the residue after three, then Play or Step through four additions. Playback is modular addition with n=floor(2t); each Step advances one addition. It does not implement hybrid clocks or receive-message updates.
- Residue r0
- 0
- Orbit period · m/gcd(m,a)
- 12
- Distinct residues visited
- 1 of 12
Addition modulo m starts at zero: rₙ = na mod m. Playback advances two additions per second. The orbit has period m/gcd(m,a), including period one for a = 0. This is not a cryptographic security test or a primality algorithm. Parameter changes pause playback and recompute the model at the current elapsed time. Reset restores both parameters and returns time to zero. Playback starts paused. Adjust either parameter, then choose Play or Step.
Look forA finite field needs an explicit exhaustion policy. Wrapping a logical tie-break to zero while leaving the first component unchanged would violate ordinary lexicographic monotonicity.
Pause & reason
Check your understanding
Your turn
Try it yourself
A receiver has(500, 6), a message carries(500, 2), and physical time reads 499. Compute the receive pair. Would tuple comparison alone detect whether a separate event(490, 0) was concurrent?
Take a moment to make a prediction or work it out on paper. Open a hint when you need one.
Give me a hint
Use the equal-maximum receive branch and remember what scalar-like clock ordering forgets.
Compare with the solution
The pair becomes(500, 7), since max(6, 2)+1=7. A separate smaller tuple does not establish a causal path; its event could be concurrent. Full causal-history inference needs stronger metadata and an appropriate model.
Keep the idea
Take it with you
- Hybrid tuples preserve known dependencies while keeping a physical-time-like component.
- Receive updates must account for both local and remote counters at equal maxima.
- Physical accuracy, uniqueness, restart handling, and overflow remain separate contracts.
Read further
Original sources and deeper explanations to follow at your own pace.
Optional progress, saved in this browser when available. Revisit any lesson at any time.
Lesson not marked complete.