Skip to content
Time, Clocks, and the Ordering of Events in a Distributed System 5 min

Leslie Lamport · Communications of the ACM 1978

Time, Clocks, and the Ordering of Events in a Distributed System

How can computers with imperfect clocks agree on what happened first? Lamport's answer: define order by cause and effect, then use a two-rule counter to stamp every event.

Read the original paper

Systems & Distributed · White Belt · Pro · 5 min read

Time, Clocks, and the Ordering of Events in a Distributed System

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 a→ba \to b for "a happened before b":

  1. If a and b are events in the same process and a comes first, then a→ba \to b.
  2. If a is a process sending a message and b is another process receiving that same message, then a→ba \to b.
  3. If a→ba \to b and b→cb \to c, then a→ca \to c.

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.

Time runs left to right. Arrows are messages. Event a happened before b because a message travels from a to b. Events c and d are concurrent: no chain of messages connects them, so neither could have affected the other.

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.

Keep reading with Pro

This paper is part of Pro. Pro and Architect open the full breakdown, with animated diagrams, interactive elements you can play with and a quiz. A few papers stay free to read in full.

Still to read

4 more sections, 1 more diagram and 2 interactive elements to play with

  • Logical clocks: two rules and a counter
  • One order everyone agrees on
  • The catch: events outside the system
  • Where this shows up in systems you will design

Found this breakdown useful?

Share it with someone else wrestling with this paper.

Discussion0

Join the Discussion

Sign in to leave comments, reply to others, or like insights.

Sign In to ScaleDojo

No comments yet. Be the first to start the thread!

Enjoyed this? Get more like it.

New paper breakdowns, levels, and one concept worth knowing, straight to your inbox.

No spam, ever. Unsubscribe in one click.

Enjoyed this content?

Your support keeps us creating free resources

We put a lot of hours into researching and writing these guides. If it helped you, consider buying us a coffee. Every bit goes toward keeping ScaleDojo's content free and growing.

$

One-time payment via Stripe. ScaleDojo account required.