I'm having trouble understanding lamport timestamps in practice and how they guarantee causal ordering.
Definitions
Lamport defines the "happens before" relationship in his paper. He states that an event a happens before an event b (denoted as a -> b) under the following conditions:
(1) If a and b are events in the same process, and a comes before b, then a -> b. (2) If a is the sending of a message by one process and b is the receipt of the same message by another process, then a -> b. (3) If a -> b and b -> c then a -> c.
He then describes the algorithm for each node to keep track of the event timestamps.
- Each process Pi increments (counter) Ci between any two successive events.
- (a) If event a is the sending of a message m by process Pi, then the message m contains a timestamp Tm= Ci(a). (b) Upon receiving a message m, process Pj sets Cj greater than or equal to its present value and greater than Tm.
This supposedly guarantees a causal ordering to events in the system
Question
In the following hypothetical sequence of events on 3 processes, isn't there a conflict in causal ordering? Event (2,1) happens before event (4,2), and (4,2) happens before (7,3), but then (7,3) happens before the receipt of (2,1). Since (4,2) had information from (2,1), applying the state from the broadcast of (2,1) after applying the state from the broadcast of (5,2) seems like it would result in an inconsistency? What am I missing?
- Note each event in the table is notated with the corresponding lamport timestamp (counter, nodeId)
- Events within a process occur in order from top to bottom
- "Broadcast(a,b)" is the event (a,b) that is the broadcast of state from node b to all other nodes
- "Receive(a,b) -> (x,y)" indicates the event (x,y) that is the receiving of some broadcast event (a,b).
P1 | P2 | P3 |
---|---|---|
(1,1) | (1,2) | (1,3) |
Broadcast(2,1) | (2,2) | |
Receive(2,1) -> (3,2) | ||
(4,2) | ||
Broadcast(5,2) | ||
Receive(5,2) -> (6,1) | Receive(5,2) -> (6,3) | |
(7,3) | ||
Receive(2,1) -> (8,3) |