Hybrid logical clocks: causal timestamps near physical time

A hybrid logical clock is a pair (l,c): a physical-time-like component and a logical counter. Its update rules keep timestamps close to physical time while preserving the one-way causal property e -> f => HLC(e) < HLC(f) under lexicographic comparison.

The converse is false. Concurrent events can have ordered HLC values because physical readings differ. HLCs support versioning and snapshots, but do not create linearizable reads, serializable transactions, bounded uncertainty, or consensus decisions.

Prerequisites and model

• Each process durably retains or safely reconstructs its last HLC state.
• Messages carry sender HLC; receives consider physical now, local HLC, and remote HLC.
• Counter width, skew bounds, rollback, and overflow behavior are explicit operational policies.

Correctness claims and invariants

• HLC-C1. A local/send event sets l=max(l,physicalNow) and increments c when physical time does not advance; otherwise it resets c.
• HLC-C2. Receive selects max of physical now, local l, and remote l, then computes c from which maxima tie.
• HLC-C3. Happens-before implies increasing HLC, but increasing HLC does not imply happens-before.
• HLC-C4. Clock rollback is absorbed by c so timestamps remain monotonic only if prior HLC state is retained.
• HLC-C5. A finite logical field needs a fail-safe overflow policy; silent wrap violates monotonicity.
• HLC-C6. HLC order supplies neither a TrueTime-style uncertainty interval nor commit/linearizability by itself.

What the scenarios prove

• Local HLC update (local-tick): Physical progress resets c; equal physical time increments it.

• Receive preserves causality (receive-causality): Receive dominates the remote send even when local physical time lags.

• Logical tie counter (logical-tie): Several events at one physical reading remain ordered locally.

• Physical rollback (backward-clock): A backward wall-clock step must not lower published HLC.

• Restart restores HLC (restart-state): Durable state prevents an earlier timestamp after restart.

• Ordered HLCs may be concurrent (concurrent-events): Independent events can have ordered HLC values without a causal path.

• Counter overflow fails safe (counter-overflow): A fixed-width c cannot silently wrap while l is pinned.

• Timestamp is not commit (linearizability-boundary): A separate protocol determines visibility of an HLC-stamped operation.

Failure, concurrency, and retry traps

• Persisting data but not last HLC can move versions backward after restart.
• Choosing the higher HLC as a causal winner loses concurrent conflicts.
• Large skew can pin l far ahead and exhaust the logical counter.
• Ordering timestamps cannot safely substitute for an expiry clock or commit protocol.

Boundaries and non-guarantees

• HLC is not a vector clock and cannot detect every concurrent pair.
• HLC is not TrueTime and has no uncertainty interval.
• A timestamp is metadata; a separate protocol decides success and visibility.

Related material

Primary sources

1. Kulkarni et al., Logical Physical Clocks and Consistent Snapshots
2. Lamport, Time, Clocks, and the Ordering of Events
3. Google Research: Spanner, Google’s Globally-Distributed Database