Concepts and theorems · Intermediate

Logical clocks: use integers to respect causal order

Calculate Lamport timestamps along a message trace and distinguish clock order from proof of causality.

Ask Logeia about this articleTry the three questionsReview your answers

Updated

On this page
  1. Order events rather than measure elapsed time
  2. Calculate a message trace
  3. The implication is only one way
  4. A tie-breaker adds order, not consensus
  5. Ask Logeia about this articleCheck your understanding

Order events rather than measure elapsed time

Logical clocks express ordering rules for distributed events instead of accurately measuring physical seconds. The happened-before relation includes earlier and later events within a process, a message send before its corresponding receive, and transitive combinations of those relationships. A Lamport clock assigns numbers that respect this relation. It does not directly reveal a universal current time or message latency in milliseconds. Before interpreting timestamped logs, identify which clock produced the value and what relation it is intended to preserve. A larger logical number is not by itself a longer elapsed duration.

Calculate a message trace

Start each process at zero and increment before a local or sending event. A sends its first message with timestamp one. B, still at zero, receives it and sets its clock to max(0, 1) + 1 = 2. B then sends a reply at three. If A has meanwhile performed a local event and advanced to two, receiving the reply advances A to max(2, 3) + 1 = 4. Taking the maximum preserves both local history and received information. This is a worked ordering trace, not a measurement of network duration or a claim about how many seconds passed.

The implication is only one way

If a happened before b, Lamport timestamps satisfy C(a) < C(b). The converse does not follow. Two independent processes can have different counter values simply because one has performed more events. A smaller timestamp therefore does not prove that a causal path exists to the larger one. Vector clocks retain more information and, under their model, can help distinguish causal order from concurrency. They also introduce state and membership costs. Increasing the number of bits in a scalar counter does not turn it into the causal information represented by a vector.

A tie-breaker adds order, not consensus

A process identifier can break equal-timestamp ties, giving a total order on pairs of timestamp and identifier. That chooses an ordering compatible with causal precedence; it does not invent causality between independent events. Nor does a clock alone ensure that every participant received the same event set or agreed on a decision. Log sorting, conflict explanation and replica versioning still need their delivery and decision protocols. Keep physical-clock synchronization, causal information and consensus responsibilities separate. Each solves a different part of interpreting or coordinating a distributed execution.

Reading and practice are recorded separately in this browser, for each language.

Learn this in order

Understand the systems behind the web · STEP 16

Choose a learning path