Vector Clock
Machines on a network disagree about the time and always will, so asking which event came first cannot be settled by asking them. What can be settled is causation: if one event sent a message and another received it, the send came first, and everything the sender had already done came first too. That relation orders some pairs and leaves others genuinely unordered, because neither could have reached the other. A single counter per machine cannot express that. Eighteen of the thirty-six pairs here are unordered; the bare integer puts thirteen of them in an order and ties on the rest, and the tie-break Lamport also defines orders every one.
New to ordering events without a clock? Start here
Machines on a network disagree about the time and always will, so which event came first cannot be settled by asking them. What CAN be settled is causality: if one event sent a message and another received it, the send came first, and anything the sender had already done came first too.
That relation orders some pairs of events and leaves others genuinely unordered, because neither could have influenced the other. A single counter per machine cannot express the whole of it. Where two of its numbers differ it imposes an order whether or not one exists, and where they happen to be equal it says nothing at all. This page shows the pair where that matters.
A message that takes time and may not arrive
A message takes time to travel from one computer to another. Sending it does not establish that it arrived, and receiving one message does not establish that an earlier one arrived first.
Messages may be delayed, lost, duplicated or reordered. A protocol defines how the participants respond to those possibilities. Some machines here model only one of them; the page says which assumptions its result needs.
The machine for this idea on its own is Packet Switching, if you would rather press it than read about it.
Machines here that come first: Logical Clock.
Two events, and neither one came first
1 Events on three machines, each counting only its own
Three machines and a fixed script of events. Each machine counts only its own, so a vector is three numbers and every machine keeps its own copy.
| event | machine | what | vector | Lamport |
|---|
2 A message carrying the sender's whole vector, and the receiver taking the maximum
A message carries the sender's whole vector, and the receiver takes the larger of each pair before counting its own event. That is the entire algorithm, and it is why a receiver ends up knowing what the sender knew.
| from | to | carried | receiver had | receiver then had |
|---|
3 Two events compared: one before the other, or genuinely neither
Every pair of events, against the truth. The truth here is not either clock: it is happens-before, worked out by following messages and machine order and closing the result transitively.
| pair | the truth | vector says | Lamport integer | with a tie-break |
|---|
4 What it costs to get this right: one number per machine, not a single integer
And what it costs. A Lamport clock is one integer whatever the size of the system; a vector is one number per machine, on every message.
| claim | held | measured |
|---|---|---|
| the vector clock matches happens-before on all 51 pairs, in both scenarios | yes | happens-before is computed here by transitive closure over the event graph, without either clock |
| 18 of the 36 pairs are concurrent, and the bare Lamport integer orders 13 of them | yes | it TIES on the other 5 -- a1/b1, a1/c1, b1/c1, a2/c2, b2/a3 -- so a single counter does not always produce an order. An outside review caught this page claiming it did |
| Lamport's TOTAL order breaks those ties on process id and orders all 18 | yes | the 1978 paper defines both, and they are different claims. The total order really does put every pair in an order, including the 18 that have none |
| on a scenario where everything really is ordered, it gets every pair right | yes | causal precedence implies increasing Lamport timestamps. Different timestamps alone cannot distinguish causality from concurrency; equal timestamps on distinct events establish concurrency. This chained scenario has no concurrent pair |
| and where one event really did cause another, the scalar is never backwards | yes | happens-before implies a smaller Lamport number. The converse is what fails, and it is the whole reason vectors exist |
| the price is a number per machine on every message, here 3 | stated | a Lamport clock carries one integer whatever the size of the system. A vector carries one per participant, so the message grows with the cluster, which is why version vectors and their pruning exist at all |
| 1988 is when the theory was written down, not when the mechanism appeared | stated | Fidge in 1988 and Mattern in 1988-89, independently. At least six groups were already using it: Fischer and Michael 1982, Parker et al. 1983, Wuu and Bernstein 1984, Strom and Yemini 1985, Schmuck 1985, Liskov and Ladin 1986 |
What is real here, and what is not
A Lamport clock is not wrong, it is incomplete
It never claims a backwards order: if one event really did cause another, its number really is smaller, and this page checks that on every pair. What it cannot do is tell an order it has imposed from one that is real: where two of its numbers differ, that difference means nothing about causality. Where they are EQUAL it does establish that neither came first, because a cause always gets the smaller number, and five of the eighteen concurrent pairs here are equal. Calling it broken would be the easy version of this story and the wrong one.
A Lamport timestamp and a Lamport total order are two different things
Lamport's 1978 paper defines both, and this page conflated them until an outside review separated them. The bare integer often TIES: five of the eighteen concurrent pairs here have equal timestamps, so a single counter does not always produce an order. The total order breaks those ties on process identifier, and that one does order every pair -- including all eighteen that have no order at all. The first is incomplete; the second is arbitrary. The bare scalar declines on the five it ties and orders the rest regardless; only the vector gets all eighteen right.
The truth here is computed without either clock
Happens-before is built by following two rules -- earlier on the same machine, and a send before its receive -- and then closing the result transitively. Both clocks are then compared against that. If the closure were wrong everything would agree with it and this page would be confidently wrong, so the test asserts the relation's own properties: irreflexive, antisymmetric, transitively closed.
The script is fixed, and that is deliberate
Nine events in a set order, not generated. A page whose example changes on reload cannot be checked by anyone reading it, and the interesting pair has to be there every time rather than most times.
1988 is the theory, and the mechanism is older
Fidge in 1988 and Mattern in 1988 for the workshop and 1989 in print, independently, and Mattern cites Fidge in the later version. But at least six groups were already using time vectors: Fischer and Michael in 1982, Parker and colleagues in 1983 who named the version vector, Wuu and Bernstein in 1984, Strom and Yemini in 1985, Schmuck in 1985, Liskov and Ladin in 1986. Schwarz and Mattern put it plainly: several authors re-invented time vectors for their purposes, often without knowing of each other.
Three machines is small enough to be exhaustive and too small to show the cost
The page compares every pair of events, which is thirty-six comparisons here and would be unmanageable at any real size. The vector's real problem is the same scale: one number per participant on every message, which is why version vectors, dotted version vectors and their pruning schemes exist. None of that is on this page.
Sources
- Friedemann Mattern, Virtual Time and Global States of Distributed Systems, 1988 workshop, published 1989 — the paper, from the author's own institution. Colin Fidge's independent paper of 1988 is the other half of the attribution and is still not readable from here. An outside review of 2026-08-30 said copies were now available; the four routes it and a search turned up were checked on 2026-08-31 and none served the text: the author's old QUT host no longer resolves, two university course mirrors return 404, one returns 403, and Semantic Scholar serves a page about the paper rather than the paper. It is cited unread, and the vector-clock construction here is checked against Mattern, which is archived.
- Logical Clock, on this site — the scalar this one is measured against, and where the limitation is stated rather than fixed.
- Logical Art, the studio this belongs to.