Two processes, P1 and P2, one message. Each event gets a Lamport counter L and a vector V.
Rules. Lamport: tick on every event; on receive, L = max(local, msg) + 1. Vector: each process owns one slot; tick your own slot on every event; on receive, take the element-wise max and then tick your own slot.
P1: e1(send) ----------- e2(local)
\
\ msg
v
P2: f1(local) ---- f2(receive e1)
e1: L=1 V=[1,0]
f1: L=1 V=[0,1]
f2: L=2 V=[1,2] (max(1,1)+1 = 2; max([1,0],[0,1]) then tick slot 2)
e2: L=2 V=[2,0]
Look at e2 and f2. Lamport gives both L=2. Tie-break on process id and you get a total order that says "e2 before f2", which looks meaningful and is not. With vectors, [2,0] and [1,2] are incomparable (neither is element-wise <= the other), so the events are concurrent. That is the whole point:
- Lamport: if
a -> bthenL(a) < L(b). The converse is false. - Vector:
a -> biffV(a) < V(b). You can detect concurrency, which is what you need to spot conflicting writes.
Cost: a vector is O(number of writers). Fine for 3 replicas, painful for a million clients, which is why real systems prune or use variants.