A Beginner’s Guide to Clocks, Causality, and Ordering in Distributed Systems

Why does something as simple as reading the time become a hard problem for distributed systems?

On a single computer, every event can be measured against one clock, so the order of the events is never in doubt. However, a distributed system, where work is spread across many independent machines, lacks a shared reference. Each machine can read time from its own hardware clock, but those clocks do not stay aligned. Network Time Protocol (NTP) tries to bring the clocks together, but it cannot eliminate the problem.

This becomes a real problem whenever correctness depends on the order in which things happened. If events on different machines are ordered by comparing timestamps, a small difference in the wrong direction can change the result. For example:

• An update that happened later can be discarded in favor of an earlier one, because clock differences gave the earlier write the larger timestamp, and the newer data disappears with no error raised.

• Logs gathered from several machines can place an effect before its cause, which makes tracing a problem much harder.

• An operation that depends on a correct order, such as granting access only after the change that authorized it, can act on stale information.

In this article, we look at these ideas in detail:

• Why a machine’s own clock is a poor basis for ordering events, and how close synchronization can realistically get

• What it means for one event to have happened before another, and why some pairs of events have no defined order

• Logical clocks and vector clocks, and what each one can and cannot determine

• Why the order of events matters in practice, for replication, auditing, and debugging

• Hybrid logical clocks and the problem they were designed to solve

• How a globally distributed database such as Google Spanner approaches ordering at scale

Clock Drift...