Lamport Timestamps and Causality

Question

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.

1. Each process Pi increments (counter) Ci between any two successive events.
2. (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)

Answer 1

No, there is no inherent logical/temporal inconsistency in the events described in the question, although it can be considered "unfair" that process P2 can receive and broadcast messages faster than other process. Well, this kind of "unfairness" occurs naturally and commonly. It is not the responsibility of Lamport timestamps to remove or hide this "unfairness".

Note that the events in the question can happen in the same temporal order, without any reference to Lamport timestamps. That is, a message sent by P1 was received by P3 only long after the message was received by P2. We can imagine, for example, both the messaging link between P1 and P2 and the messaging link between P2 and P3 are fast channels while the messaging link between P1 and P3 are sluggish. It takes a second for a message to go between P2 and another process while it takes a day for a message to go between P1 and p3. So, these events cannot involve any impossible "causal ordering".

In fact, we could say that Lamport timestamps makes it easier to identify this kind of "unfairness" or "difference of communication speeds", such as when an event like "Receive(5,*)" happens before an event like "Receive(2,*)".