← The Books

Ordering Without Clocks

If no two machines agree on the time, how can they agree on what happened first? And when two things happen far apart, how can anyone tell whether one led to the other or neither knew of the other?

We find out by exploring how ancient Greek trading houses kept the order of trades when sundials became useless on cloudy days.

After Leslie Lamport, Time, Clocks, and the Ordering of Events in a Distributed System, 1978 · Colin J. Fidge, Timestamps in Message-Passing Systems That Preserve the Partial Ordering, 1988 · Friedemann Mattern, Virtual Time and Global States of Distributed Systems, 1988

Before a columned portico a scribe writes a number on a slip beside a stone sundial that casts no shadow, while three messengers jog one behind another along the road
Where this book sits
Draws on
This book retells
Leads to

Each link is an idea one paper took from another. Point at one, or tap it, to read how.

a paper this book retells a paper retold in another book a paper outside the series

First, in machine terms

Many computers, no shared clock

Computers that work together must often agree on the order in which things happened: which of two writes came first, or whose request is served next.

A clock on the wall would settle it. But every machine has a clock of its own, the clocks disagree, and no message tells how long it took to arrive. Two ideas get an order without a shared clock.

  • Logical clocks (Lamport, 1978): a counter on each machine, sent along with every message, numbers events so that a cause always has a smaller number than its effect.
  • Vector clocks (Fidge and Mattern, 1988): one counter per machine tells exactly which events could have affected which.

The first gives every machine the same order of events. The second also tells which events could have known of which. We tell it with three trading houses on an island whose sundials have gone dark.

Three machines, three clocks

What happened
Sorted by timestamp

Each machine trusts its own clock. Press the button.

A narrow road cut into a sea cliff, with loaded mules walking one behind another between dry-stone walls and olive trees
The ring road of Arche

Three houses, one narrow road

House 1, House 2 and House 3 stand round the coast of Arche with a mountain between them. Word passes between them only on written slips, carried by messengers along the one road.

No passingBy the law of the road no messenger may pass another, so slips from one house to another arrive in the order they were sent.
No longest journeyEvery slip arrives, but after a time that nobody can bound.
No common hourIn the trading season cloud silences the sundials, and each counting room's water-clock keeps its own time.*
The question

Which request was placed first?

House 3 has grain in its storehouse, enough for one of the other houses, and both need it. House 2 sends a messenger with a request for it. House 1, knowing nothing of this, sends a messenger with a request of its own.

The houses have agreed that the request placed first is filled first, so House 3 must find out which one that was. The plain way is to see whose messenger reaches the gate first.

Two messengers meet before House 3's portico, each holding out a slip toward the gate

The gate of House 3 who gets there first?

House 2 always writes its request first here. Choose whose messenger has the quicker legs.

The gate rewards the house with the quicker messenger, whichever house wrote first. House 3 could instead ask each house the hour its request was written, and it would get two readings of two water-clocks that were never set together. Every way of settling it asks for a clock the island does not have.

The houses need not give up filling the first request first. They have been asking a question that nobody on Arche can answer, and beside it lies a narrower one that every house can.

A narrower question

What could have led to what

The narrower question came from House 1's accountant. Which of two requests the sun saw first is something no house can see, and trade needs less than that: a request should never be filled before one that could have led to it.

What could have led to what is something every house can see, because news moves on Arche only by slip. The accountant set it down in three rules. One event came before another in exactly these three cases.

Rule one

Same house, higher up the scroll

Both happened in one house, and its account scroll has the first written above the second.

Rule two

Sending comes before receiving

The first is a house sending a slip, and the second is another house receiving that same slip.

Rule three

Chains count

The first came before some third event, which came before the second.

Here is one morning's business at the three houses. Choose any two entries, and the rules say whether one came before the other.

One morning on Arche click two entries

Each line is one house, at one moment after another. Each dot is an entry in its scroll. Each arc is a slip on the road.

Choose any two dots. Did one come before the other?

If none of the three rules joins two events, they are unrelated. That does not mean they happened at the same moment. It means neither could have known of the other, since no chain of slips joins them. The sun may have seen one before the other, and nothing the houses hold can say which.

Three rules make a definition, and a clerk needs something to calculate with. For that the accountant gave every counting room a number.

A number that respects every chain

The tally

The number is the tally. Every counting room keeps one, writes it on every slip it sends, and raises it by two mechanical rules. Scroll slowly, and the picture moves with you.

Before House 1's portico under low cloud, the accountant hands a narrow slip to a messenger
1 · Start

The same morning, without numbers

Ten entries in three scrolls, and three slips on the road. No entry has a number yet.

2 · Rule one

Every entry raises the tally

A house advances its tally by at least one between any two entries in its own scroll. Sending a slip is an entry too.

3 · Rule two

The tally rides on the slip

House 1 writes its current tally, 2, on the slip it sends to House 2.

4 · Rule two

The receiver jumps past it

House 2 stood at 1. The slip says 2. So House 2 sets its tally higher than the slip, to 3, before entering the arrival. A tally is never lowered.

5 · On it goes

Each slip drags the next house forward

House 3 stood at 2 and receives a slip marked 4, so its entry is 5. House 1 stood at 2 and receives a slip marked 6, so its entry is 7.

6 · The promise

Along any chain, the numbers only rise

Follow the red chain from house to house: 1, 2, 3, 4, 5, 6, 7. Whatever could have led to an entry has a smaller tally than that entry.

7 · The catch

A smaller number is not an earlier event

Look at the two ringed entries. No chain joins them. House 3's entry lies further out, later by the sun, yet it carries 2 and House 2's carries 3. The tally puts a sequence where nature left none.

So the tally respects every chain of slips, and it says nothing true about two entries that no chain joins. The two requests for House 3's grain are exactly such a pair, and House 3 still has to fill one of them first.

One sequence for everyone

Breaking ties

House 3 may know that the two requests are unrelated and still not know whose to fill. The houses need a sequence that decides between every pair, that every house works out alike, and that never contradicts a chain of slips.

House 1's accountant got one by the plainest means there are. The rule of precedence: compare tallies, and where they are equal the lower house number goes first, House 1 before House 2 before House 3. The six entries below reached the three houses in different orders.

Three houses, six entries as each heard of them

House 1's list
House 2's list
House 3's list

Precedence does not find out which of two unrelated requests was really first, and nothing the houses hold could. It replaces the question with an answer every house reads the same way. The answer is fair in the one sense the houses can check: where one request led to another, they are filled in that sequence, and no house wins by owning a quicker messenger.

The houses can now agree on a sequence without a clock. A harder test is something that only one house may use at a time, with no master to hand out the turns.

Proof · precedence is a total order that extends coming-before

Write a → b when event a came before event b, and C(a) for the tally of a. The two rules of the tally give the Clock Condition: a → b implies C(a) < C(b). For a at house i and b at house j, precedence a ⇒ b holds if (1) C(a) < C(b), or (2) C(a) = C(b) and i < j. Claim. ⇒ is a total order, and a → b implies a ⇒ b.

  1. Total comparability. For any two distinct events a and b: if their tallies differ, clause (1) decides. If their tallies are equal and they occurred at the same house, rule (1) of the tally already gave the later one a higher tally, so they must belong to different houses, whose numbers differ, and clause (2) decides.
  2. Antisymmetry and transitivity. Compare by the pair (C(e), house). This is the standard lexicographical ordering of pairs drawn from two total orders, which is strictly total and transitive.
  3. Consistency with causality. If a → b, then by the Clock Condition C(a) < C(b) strictly. Precedence places a earlier by clause (1) alone; house numbers are never consulted. Hence a → b ⟹ a ⇒ b.∎
Putting the sequence to work

One storehouse, no porter

The island's common storehouse is such a thing. It is cut into the rock beside the road, and only one house may load from it at a time.

A porter at the door who let in whoever asked first would be fooled as House 3's gate was, because a request can reach the door ahead of one sent earlier over a longer stretch of road. So there is no porter. Each house keeps its own queue of requests, in order of precedence, and follows five rules. Scroll to watch two houses ask at once.

1 · Quiet

Three queues, all empty

Every house holds a queue of its own. Nobody is asking for the storehouse.

2 · To request

Two houses ask at once

House 1 writes a request under its tally, 2, puts it in its own queue and sends it to both other houses. House 3, knowing nothing of this, does the same under its own tally, also 2.

3 · Not yet

First in your own queue is not enough

House 3's request stands first in House 3's queue, and still House 3 may not load. An older request may be on the road right now, in a messenger's pouch.

4 · On receiving a request

Every queue comes out the same

Each house enters the request it receives. The tallies tie at 2, so House 1's goes first by house number, in all three queues.

5 · The answer

Each house sends an answer back

A house that receives a request advances its tally and sends an answer. Every answer carries a tally above 2.

6 · To enter

House 1 loads

House 1's request stands first in its queue, and it has heard from both other houses with tallies above 2. Both halves of the rule hold. House 3 has heard from everyone too, but stands second, and waits.

7 · To release

House 1 is done

House 1 removes its request from its own queue and sends a release to both other houses.

8 · On receiving a release

House 3 loads

Each house strikes House 1's request. House 3 now stands first, and has long since heard from everyone.

9 · Why it is safe

Never two houses at once

To load early, House 3 needed a slip from House 1 with a tally above 2. On a road where no messenger passes another, that slip arrives after House 1's request. So the request was already in House 3's queue, ahead of its own.

The houses now share a storehouse by a sequence they all agree on, with no clock and no master. The sequence is their own, though, and it can part from what the sun saw. One way across Arche shows how far.

Proof · two houses never hold the storehouse at once

Ri is the request of house i, and C(Ri) the tally it was written under. Rule 5: house i enters when Ri stands first in its queue, ordered by ⇒, and it has received from every other house a message carrying a tally greater than C(Ri). Messages from one house to another arrive in the order sent. Claim. No two houses hold the storehouse at the same time.

  1. Suppose for contradiction that House 1 and House 3 both hold the storehouse at once, on requests R₁ and R₃. Precedence is total, so one is earlier; assume R₁ ⇒ R₃.
  2. By Rule 5, when House 3 entered, it had received from House 1 some message carrying a tally T > C(R₃).
  3. House 1 dispatched R₁ to House 3 under tally C(R₁) before dispatching any message with tally T. Because nobody overtakes on the coastal road, slips from House 1 to House 3 arrive in FIFO order.
  4. Therefore, House 3 received R₁ before receiving the message with tally T. So R₁ was already in House 3's queue when House 3 entered.
  5. Since R₁ ⇒ R₃, R₃ did not stand first in House 3's queue. Rule 5 was violated, and House 3 could not have entered.∎
Mount Phyle from the air: a steep wooded crag with a ruined wall on top and the trading towns far below on the coast
What the tally cannot see

Over the mountain

The way across is over the mountain. A goatherd who knows the smugglers' tracks can cross it in a couple of hours, with luck. The same goatherd may take two days, or never come down, which is why no house sends its business that way.*

News can still travel with a goatherd, who carries no slip. Suppose a trader at House 3 concludes a sale and pays a goatherd to take word of it to House 1, while the official slip goes round by the road.

A sale at House 3 and a lucky goatherd

House 3 has had a busy morning. House 1 has had a quiet one.

By its own rules the tally has done nothing wrong. The rules touch only slips, and the goatherd carried none. As far as the houses' scrolls can tell, the sale and the request are unrelated, though one caused the other as surely as if a messenger had carried the news.

The goatherd is one thing the tally misses. The clerk of House 2 has found another, and this one lies on the road itself.

Joined, or made in ignorance?

One number for each house

The clerk of House 2 has a doubt that the tally cannot settle. Two entries carry 4 and 5. One may have led to the other, or each may have been made knowing nothing of the other, and the two numbers read the same either way.

A single number cannot say which, because it mixes together everything a house has heard. When House 2 raises its tally past a slip, it forgets whose number it was raised past. Remembering takes one number for each house. So each house keeps a column of three rows: row by row, the latest count of each house's entries that it has heard of. Three rules keep the column.

Rule one

Count your own entries

On every entry of its own, a sent slip included, a house adds one to its own row.

Rule two

Send the whole column

Every slip is stamped with the sender's full column, as it stands after that entry.

Rule three

Keep the larger of each row

On receiving a slip, a house takes the larger number in each row, then adds one to its own row.

The same morning, with columns click two entries

The dots show tallies. Choose two entries to compare their columns. Try the 2 on House 3's line and the 3 on House 2's.

Comparing two columns row by row settles the clerk's doubt. One entry came before another exactly when its column is no greater in every row, and the two columns differ. Two entries are unrelated exactly when neither column is at least the other. Where the tally could only fail to rule out a connection, the column finds it or rules it out.

Only what never went by slip is left unseen, and that brings back the goatherd.

Proof · the column detects coming-before and unrelatedness exactly

House i keeps a vector Vi with one component for each house. Rule 1: on every event of its own, a send included, it increments Vi[i]. Rule 2: a message carries the sender's vector as it stands after that increment. Rule 3: on receiving a vector U, house j sets Vj[k] to max(Vj[k], U[k]) for every k, then increments Vj[j]. V(a) is the vector at event a; V(a) ≤ V(b) means no component is greater, and < means ≤ and not equal. Claim. a → b if and only if V(a) < V(b); and a ∥ b (unrelated) if and only if neither V(a) ≤ V(b) nor V(b) ≤ V(a).

  1. If a occurs at house i with timestamp V(a) and a → b, there is a causal chain of local events and messages from a to b. By Rules 1–3, every step non-strictly increases all components and strictly increases the component of the executing process. Thus V(a)[i] ≤ V(b)[i]. Since at least one step strictly increments a component, V(a) < V(b).
  2. Conversely, suppose a occurs at house i and does not precede b (a ↛ b). Then no slip carrying information about a has reached b. By Rule 3, the value of row i at b reflects only events at i that causally precede b. Since a is not among them, V(b)[i] < V(a)[i]. Thus V(a) ≰ V(b).
  3. Therefore, a → b if and only if V(a) < V(b). Concurrency a ∥ b holds if and only if neither column dominates the other.∎
The goatherd again

Whose order do the houses keep?

The column is built from slips and nothing else, so the goatherd escapes it too. Catching the goatherd would take numbers that rise along every path in the world, slip or no slip, and only clocks that run with the world can promise that.

Such clocks can be described. Each house keeps a true clock, every slip carries the sender's reading, and a house that is behind sets itself forward. If the clocks never disagree by more than the goatherd's fastest crossing, the goatherd can no longer arrive before setting out.

Arche cannot keep them. They need a longest journey and messengers at regular hours, and the trading season gives neither. So the houses are left with the tally and the column, and it is worth saying plainly what each one sees.

The island of Arche from the air under cloud: a wooded mountain ringed by a coast road and small harbour towns
The tally

Respects every chain of slips

It gives every house the same sequence. It cannot say whether two entries were joined or unrelated.

The column

Sees every chain of slips

It tells joined from unrelated exactly, at the cost of one number for each house.

Neither

Sees what never went by slip

The sequence the houses keep is their own. A sequence judged by the sun would be a different promise, and a harder one.

Back to machines

The island was a network of machines

Read the island again with machines in the counting rooms. Every house is a process, every slip is a message, and the tally is a counter that each machine keeps. Hover over a row, or tap it, to see who is who.

On the island
In the machine room

Without a shared clock, machines can still agree on one order of events that never puts an effect before its cause.

One counter cannot tell related events from unrelated ones. One counter per machine can.

Lamport's logical clocks, and the vector clocks of Fidge and Mattern, are how distributed systems still put events in order.

The Ring Road, in detail All the papers

Setting The Ring Road

The papers behind this book

The papers behind this book. Leslie Lamport, “Time, Clocks, and the Ordering of Events in a Distributed System,” Communications of the ACM 21, 7 (July 1978), 558–565. Colin J. Fidge, “Timestamps in Message-Passing Systems That Preserve the Partial Ordering,” Proc. 11th Australian Computer Science Conference (1988), 56–66. Friedemann Mattern, “Virtual Time and Global States of Distributed Systems,” Proc. Workshop on Parallel and Distributed Algorithms, North-Holland (1988), 215–226.

Lamport, L. Time, clocks, and the ordering of events in a distributed system. Commun. ACM 21, 7 (1978), 558–565.

Fidge, C. J. Timestamps in message-passing systems that preserve the partial ordering. Aust. Comput. Sci. Commun. 10, 1 (1988), 56–66.

Mattern, F. Virtual time and global states of distributed systems. In Parallel and Distributed Algorithms, M. Cosnard et al., Eds. North-Holland, 1989, pp. 215–226.