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 that -- it always produces an order, even where none exists. This page shows the pair where that matters.
A message that takes time and may not arrive
Two computers in one room are far apart by a processor's standards. A message crossing between them takes time you cannot argue with, and across a continent that floor is set by the speed of light in glass.
Worse, it may arrive after a message sent later, or arrive twice, or never arrive at all, and the sender is not told which. There is no moment at which both ends know the same thing. Every machine in this topic is a way of getting useful work done anyway, without that guarantee, and the ones that look overcomplicated are usually the ones that stopped pretending.
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 The same pair under a Lamport clock, which puts them in an order anyway
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 | a Lamport clock never claims a WRONG order: if it says a came first, nothing rules that out. What it cannot do is say that neither did |
| 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 | yes | 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 | yes | 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 say that neither came first, because a single number has no way to represent two things being unrelated. 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. Only the vector declines to answer.
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 not online in a form this site can archive.
- 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.