How to use the Lamport and Vector Clock Calculator
- 1. List the eventsOne line per process, events in order. Use a name for internal events, send(m1) and recv(m1) for messages.
- 2. Name eventsWrite b=send(m1) to give a send or receive a name you can refer to.
- 3. Compare eventsType two event names to see if one happened before the other or they are concurrent.
The rules
Lamport clock: each process keeps a counter C. Before each event, C = C + 1. A message carries the sender's C. On receive, C = max(C, message time) + 1.
Vector clock: process i keeps a vector V. Before each event, V[i] = V[i] + 1. A message carries V. On receive, take the element-wise max with the message's vector, then add 1 to V[i].
If a → b (a happened before b), then C(a) < C(b). The reverse is not true for Lamport clocks. Vector clocks fix this: a → b exactly when V(a) ≤ V(b) in every position and they differ. If neither is ≤ the other, the events are concurrent.
Worked example (Coulouris)
P1: a, then b sends m1. P2: c receives m1, then d sends m2. P3: e, then f receives m2.
- Lamport: a = 1, b = 2, c = max(0, 2) + 1 = 3, d = 4, e = 1, f = max(1, 4) + 1 = 5.
- Vector: a = (1,0,0), b = (2,0,0), c = (2,1,0), d = (2,2,0), e = (0,0,1), f = (2,2,2).
Compare e and c: Lamport gives 1 < 3, but (0,0,1) and (2,1,0) are not ordered, so e ∥ c. That is the case Lamport clocks cannot detect.
Where these clocks are used
Lamport timestamps with process-number tie-breaks give the total order used in Lamport's distributed mutual exclusion algorithm and in totally ordered multicast. Vector clocks, and the closely related version vectors, let replicated stores tell a newer update from a conflicting concurrent one. The cost is one counter per process in every message.
Frequently asked questions
Why break ties by process number?
Lamport times can be equal for concurrent events. Adding the process number gives a total order that every process agrees on, used in mutual exclusion algorithms.
Do I increment before or after the max on a receive?
Both orders give the same values here: take the max with the message timestamp and add 1 for the receive event.
Can one message be received by several processes?
Yes. Use recv(m1) on each receiving process for a multicast.