Ask two computers in different cities which of two events happened first, and each will glance at its own clock and give you an answer. The two answers will often disagree, because no two clocks tick at exactly the same speed. In 1978 Leslie Lamport pointed out something more unsettling: even with perfect clocks, in a distributed system it is sometimes meaningless to say which event came first.
His way out was to stop asking what time it is and start asking what could have caused what. That one change gives us the logical clock, a counter that is cheap, needs no special hardware, and still lets a whole cluster agree on a single order of events. The idea sits underneath version vectors in Dynamo, term numbers in Raft, and the ordering guarantees in almost every replicated database.
Do not trust wall clocks to order events across machines. Define order by cause and effect (the happened-before relation), then use a simple counter rule to stamp every event so the stamps respect that order. Ties are broken by process ID, and everyone ends up with the same total order.
Order without a clock: happened-before
Think of three people sending letters. If Ana mails a letter and Ben replies after reading it, Ana's mailing clearly came before Ben's reply. But if Carla in another city writes a letter the same afternoon, you cannot say whether hers came before or after Ana's, and it does not matter, because neither could have influenced the other.
Lamport turned this into a precise rule with three clauses. Write for "a happened before b":
- If a and b are events in the same process and a comes first, then .
- If a is a process sending a message and b is another process receiving that same message, then .
- If and , then .
Two events that are not connected by any chain like this are called concurrent. The relation is only a partial order: some pairs of events simply have no order at all.
Read "a happened before b" as "a could have caused b." Information can only travel along process lines and message arrows, so if no path of arrows leads from a to b, a cannot have affected b. That is the entire definition. Physical time never appears in it.
