Concepts
Clocks, skew, and monotonic time
Intuition
Imagine two colleagues in different offices, each with a wall clock set by hand: the two never show exactly the same time, and every now and then someone readjusts theirs, sometimes even backwards. If each one writes 'finished at 10:03' on a note, comparing the notes to find out who finished first is unreliable, and since a clock can go back, even measuring how long a task took is not safe. To measure duration, use a stopwatch that only moves forward, which is no use for comparing across offices; to order the notes, number the steps in the order in which one influenced the other ('my note comes after the one I read') or admit 'it was between 10:02 and 10:04' and wait for the doubt to pass before asserting any order.
How it works
Each machine has its own wall-clock, which diverges from the others (skew, because of drift) and is corrected by synchronization, which can make it jump backward; a monotonic clock, on the other hand, only moves forward and is good for measuring durations and timeouts on the same machine, but its values are not comparable across machines. Lamport starts from the fact that, in a distributed system, message delay is not negligible compared to the time between events and physical clocks are not perfectly accurate; so he defines the happened-before relation as the smallest relation that satisfies three conditions (events in the same process follow execution order; sending a message precedes receiving it; and transitivity), which yields only a partial order in which events with no causal path between them are concurrent. The logical clock implements this order with a counter per process: it is incremented on every event and sent along with the message, and the receiver sets its own to a value greater than the one received and not smaller than its current one (in common implementations, the larger of the two plus one), with ties broken by a fixed arbitrary order among processes (for example, the identifier) to form a total order. The condition holds in only one direction: if A happened before B, A's timestamp is smaller, but a smaller timestamp does not prove that A happened before B; in addition, the order cannot see causality that flows through an external channel and can contradict the order users perceive, which the paper calls anomalous behavior. Spanner takes the other path and exposes the physical clock's uncertainty with the TrueTime API, in which TT.now() returns an interval [earliest, latest] guaranteed to contain absolute time; the reference time comes from time masters with GPS and atomic clocks, which a daemon polls periodically (every 30 seconds, with an applied drift of 200 microseconds per second, values from the paper's era); between polls, the applied drift makes the uncertainty grow from 0 to about 6 ms, the communication delay to the time masters adds about 1 ms more, and in production it typically varied in a sawtooth between about 1 and 7 ms, averaging about 4 ms most of the time. To guarantee external consistency (if T1 commits before T2 starts, T1's timestamp is smaller), the coordinator picks a commit timestamp no smaller than TT.now().latest, computed after the commit request arrives at it (Start rule), and only releases the transaction's data when TT.after(timestamp) is true (Commit Wait). If the uncertainty grows, Spanner simply waits longer: it gets slower, but stays correct as long as the uncertainty bound advertised by TrueTime is valid.
In practice
To measure duration, set timeouts, or track how long something took, use the machine's own monotonic clock, because the wall clock can jump after a synchronization. To decide the order of events across machines, do not trust the wall-clock time of different nodes: when it is enough to respect causality, use Lamport-style logical counters, remembering that a smaller timestamp does not prove that one event came before the other, since the two may be concurrent. When the order must respect real time as seen from the outside, as in transactions with external consistency, it is necessary to bound the clock uncertainty and pay the wait at commit, as Spanner does with TrueTime.
Use it in a design
Practice the cases that rely on this concept in the System Design school.