A vector clock carries one counter per process, merged by elementwise maximum, and it makes happens-before decidable in both directions: e → f exactly when V(e) ≤ V(f) componentwise and the vectors differ. When neither vector dominates the other the events are concurrent — unordered by any chain of messages. On the same eleven-event diagram, 23 of the 55 pairs are concurrent, and those are precisely the pairs a merge will have to decide.
Core ideas
One counter per process, a comparison that can fail in both directions, and a word that does not mean what it sounds like.
Process i keeps a vector V and increments V[i] at each of its own events. A message carries the sender's whole vector; on receipt the receiver takes the elementwise maximum with its own and then increments its own component. The vector is therefore a record of how much of each process's history this event knows about.
V(e) ≤ V(f) means every component of V(e) is at most the matching component of V(f). If that holds and the vectors differ, e → f. If neither V(e) ≤ V(f) nor V(f) ≤ V(e), there is no chain either way and the events are concurrent. Unlike a single integer, a vector can simply refuse to compare, and that refusal is the answer.
A3 and C3 on this diagram are concurrent, and they may have occurred a minute apart on any wall clock. What makes them concurrent is that neither process had heard anything of the other's event when its own occurred. Concurrency here means “unordered by any chain of messages”, and it is exactly the condition under which two updates conflict.
The material
How the vectors propagate, what the componentwise comparison decides, and why the count of concurrent pairs is the useful output.
A vector clock on n processes assigns each event a vector V of n counters. Process i increments V[i] at each of its events; a receive first takes the elementwise maximum with the vector carried by the message. Then e → f if and only if V(e) ≤ V(f) componentwise with V(e) ≠ V(f), and e and f are concurrent if neither comparison holds.
The “if and only if” is what a Lamport stamp could not offer. A single integer can be compared with any other integer, so it always produces an answer even when there is no answer to produce; a vector produces three possible outcomes — before, after, or neither — and the third is as informative as the others.
Read C3 = (2,3,3) as a sentence: this event knows about the first two events of A, the first three of B, and is C's own third. That is the whole content of a vector clock, and every ordering question is answered by comparing two such sentences.
Twenty-three of fifty-five is not an anomaly of this diagram, it is what a system with few messages looks like. Concurrency is the default and ordering is what communication buys, so a system that gossips rarely has a great many concurrent pairs and a system that synchronises constantly has few — and pays for the difference in messages.
A3 = (3,0,0) and C3 = (2,3,3). Compare: 3 ≤ 2 fails, so A3 does not precede C3; and 3 ≤ 0 fails in the middle component, so C3 does not precede A3. They are concurrent — and C3 is the last event on its process while A3 is in the middle of another, so on a wall clock they could be seconds or minutes apart. The vectors are not claiming they happened at the same moment. They are claiming that neither process could possibly have known about the other's event, which is the condition under which two updates to the same key are a conflict rather than an overwrite.
That is what the count is for. Every concurrent pair touching the same data is a decision somebody has to make — keep one, keep both, merge them — and “Conflict Resolution, Counted” is where those decisions get priced. The vector clock's job ends at identifying them, and it does that exactly, which is more than any single number can do.
Interactive
Happens-before as a partial order, with every incomparable pair listed
Method
The propagation is mechanical. The part worth slowing down for is the comparison, which has three outcomes and not two.
Decide once that the vector is (A, B, C) and write every vector that way. Most arithmetic errors here are a component written in the wrong slot, and they are invisible until a comparison comes out strangely.
A send is an event on the sender and a receive is an event on the receiver, so both increment. Forgetting the increment on a send makes the send and the message's previous event compare as equal.
Maximum with the message's vector, then +1 in your own slot. The order matters: incrementing first and then taking the maximum can lose your own increment if the message was ahead in your component, which it should never be but will be if an earlier step was wrong.
Ask whether V(e) ≤ V(f), then whether V(f) ≤ V(e). Two failures mean concurrent; one success means ordered; two successes mean the vectors are equal and you have compared an event with itself.
The same three processes and three messages as before. The stamps this time are vectors, and the output is not an order but a census: how many of the fifty-five pairs are ordered and how many are conflicts waiting to happen.
The second and third comparisons are the ones to sit with. A1 and A3 are two events on the same process, one before the other, and the vectors say that the earlier one precedes C3 while the later one does not. That is not a contradiction: A1's information reached C through the chain of messages and A3's did not, because A3 happened after A had already sent everything it was going to send.
Twenty-three concurrent pairs on eleven events is the real output. If those events were updates to one key, twenty-three of the pairs would need a merge rule and thirty-two would not — and no amount of clock accuracy changes that split, because it is a fact about which messages were sent.
For a faded rehearsal, delete the message C1 → A4 from the diagram. The supplied first move is that A4 becomes a local event, so its vector is (4,0,0) rather than (4,0,1). Restamp what changes, predict whether the concurrent count rises or falls, then compute it and check against the lab.
You should be able to propagate vectors along a diagram including sends and receives, compare two vectors in both directions and report one of three outcomes, count the concurrent pairs, and say what a concurrent pair implies about two updates to one key.
Something to change about this lesson? Write it down, tick it off when it is handled, and export the list when you want to act on it. Kept in this browser only: nothing is sent anywhere, and nobody is notified.
No recommendations yet for this lesson.