Logical clocks

A timestamp can lie about order

Suppose service A records an event at 10:00:05 and service B records a related event at 10:00:04. Sorting those values says B came first. That conclusion is unsafe when the machines' physical clocks differ. Physical clocks are not perfectly accurate, and clock synchronization can make nonmonotonic updates.

The order a distributed program can observe comes from its events and messages. If A sends a request and B receives it, the send occurred before the receive even when their wall-clock values suggest otherwise.

Wrong "The smaller wall-clock timestamp identifies the earlier distributed event."

Right A physical timestamp is useful only with the clock assumptions that surround it. Causal order can be defined without physical time.

The happens-before relation

The happens-before relation has three rules:

1. Earlier events in one process happen before later events in that process.
2. Sending a message happens before receiving that same message.
3. The relation is transitive. If a happens before b, and b happens before c, then a happens before c.

Two events are concurrent when neither happens before the other. Here, concurrent means causally unordered. It does not mean the events occurred at the same physical instant.

If A creates an order and then sends a message that causes B to reserve stock, the create event happens before the reservation. Two local events on different processes with no causal path in either direction are concurrent under this definition.

Lamport clocks count logical progress

A Lamport clock is a counter, not a physical clock. Each process advances its counter between successive events. A message carries the sender's counter. On receipt, the receiver advances its counter beyond both its local value and the received value.

One common integer form is:

local or send event: clock = clock + 1
receive timestamp t: clock = max(clock, t) + 1

This gives the clock condition:

if a happens before b, then timestamp(a) < timestamp(b)

The converse is false. A smaller Lamport timestamp does not prove that one event caused another. Independent events still receive numbers, and those numbers can differ.

Wrong "Lamport timestamp 7 is less than 12, so event 7 caused event 12."

Right The timestamps put the events in a consistent logical order. Evidence of causality still comes from the happens-before relation.

Lamport clocks solve an ordering problem. They do not measure elapsed time, recover exact wall time, or identify every concurrent pair.

Why Lamport time has only one implication

The happens-before relation is the smallest relation containing local process order and message send-to-receive order, plus every edge implied by transitivity. It is a partial order because some event pairs have no causal path in either direction.

A Lamport clock preserves every causal edge:

a happens before b  =>  L(a) < L(b)

It compresses a distributed history into one integer per event. That compression loses information. If L(a) < L(b), the events may be causally related, or they may be concurrent events that happened to receive different counter values.

Wrong "Comparing two Lamport timestamps answers whether the events are concurrent."

Right Lamport comparison is consistent with causality but cannot recover causality. The reverse implication does not hold.

Extending a partial order to a total order

Some protocols need every participant to make the same deterministic choice between all events, including concurrent ones. Lamport's construction compares logical timestamps first and uses a fixed process ordering to break ties:

event key = (lamport timestamp, process identifier)
compare keys lexicographically

This creates a total order that extends happens-before. If a happens before b, a remains before b in the total order. The order selected for concurrent events is an arbitrary protocol choice. A tie-breaker does not reveal a missing causal relationship.

That distinction matters when reviewing a design. A deterministic conflict winner may need a total order. A debugger asking whether one event could have influenced another needs causal information.

Vector clocks retain causal structure

In Mattern's foundational fixed-process construction, a vector clock has one component per process. A process increments its own component at every event. Messages carry the resulting vector. On receipt, the receiver takes the componentwise maximum of its incremented local vector and the message vector.

at every event on process i: V[i] = V[i] + 1
after that increment on receipt: V[k] = max(V[k], M[k]) for every k

Compare vectors component by component. V < W when every component of V is less than or equal to the matching component of W, and at least one component is smaller.

[2, 1] < [3, 1]
[2, 0] and [0, 2] are incomparable

For the vector-clock model, V(a) < V(b) if and only if a happens before b. Incomparable vectors identify causally concurrent events.

Wrong "Sort vectors by their first different component, like version strings."

Right Vector order is componentwise. A lexicographic sort would invent an order between [2, 0] and [0, 2] and discard the concurrency signal.

The extra information has a cost. Mattern's construction uses vectors whose length is the number of processes, and each message carries a timestamp vector. A scalar Lamport clock stays compact but cannot answer the same causal query.

Physical time answers a different question

Logical clocks establish relationships among observed system events. They do not say that Lamport ticks 20 and 25 are five milliseconds apart. If a requirement depends on user-observed real-time order or a time window, the protocol needs explicit physical-clock assumptions or another mechanism that supplies them.

Ordering guarantees must be named separately

The happens-before relation contains local process order, the order from a message send to its receipt, and the transitive edges implied by those rules. Two events are causally concurrent when neither happens before the other.

Four claims often get compressed into "the timestamps are ordered":

• causally related events receive increasing timestamps
• every pair of events has a deterministic order
• timestamps expose whether two events are concurrent
• timestamp order matches physical real-time order

These are different guarantees. Lamport clocks provide the first. A tie-breaker extends them with the second. Vector clocks provide the first and can test the third under their process model. Physical-clock order needs assumptions about synchronization and accuracy.

Wrong "A total order is stronger, so it contains more causal information than a partial order."

Right A total order makes a choice for every pair. For concurrent events, that extra order is invented. Vector time preserves the incomparability that represents causal independence.

Hybrid logical clocks

A hybrid logical clock (HLC) combines a physical-time-derived value l with a logical counter c. The HLC paper keeps l at the maximum physical-clock value learned so far. The counter distinguishes causally ordered events while l is unchanged. Timestamps compare lexicographically as (l, c).

For a local or send event at node j, the paper's algorithm is:

oldL = l
l = max(oldL, physicalTime)
if l == oldL:
  c = c + 1
else:
  c = 0
timestamp = (l, c)

On receipt, the node also considers the message's (messageL, messageC):

oldL = l
l = max(oldL, messageL, physicalTime)

if l == oldL and l == messageL:
  c = max(c, messageC) + 1
else if l == oldL:
  c = c + 1
else if l == messageL:
  c = messageC + 1
else:
  c = 0

The construction preserves the logical-clock property:

e happens before f  =>  HLC(e) < HLC(f)

It also keeps logical time close to the physical clock under the paper's bounded clock-synchronization assumption. "Close" is the operative word. An HLC timestamp is not proof of the exact physical instant at which an event occurred.

What HLC does not inherit from vector time

HLC timestamps are compact ordered pairs rather than one component per process. That makes them suitable for uses such as database version timestamps and snapshot reads. It also means a comparison does not provide the vector-clock equivalence between timestamp order and happens-before.

Wrong "If HLC(a) < HLC(b), then a caused b; equal HLC values identify concurrency."

Right Causality forces increasing HLC timestamps. Increasing HLC timestamps alone do not prove causality, because independent events can still receive ordered scalar timestamps.

The choice is concrete. Vector clocks retain enough structure to detect causal concurrency, with metadata that has one entry per process in the foundational model. HLCs retain causal timestamp order and physical-time proximity in a compact representation, but they do not answer every causal-comparability query.

The database still owns its clock assumptions

Adopting HLC does not erase the surrounding protocol. CockroachDB uses HLC values for transaction timestamps and MVCC versions, passes local HLC timestamps in requests, and updates a receiver with the supplied timestamp. Its current documentation also requires moderate clock synchronization. It warns that skew outside the configured bound can violate single-key linearizability between causally dependent transactions, even though serializable isolation is maintained under its stated conditions.

So "uses HLC" is not a complete consistency argument. A design review must identify which guarantees come from logical timestamp propagation, which come from transaction or consensus protocols, and which depend on a bound on physical clock offset.