3
$\begingroup$

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)
$\endgroup$

1 Answer 1

3
$\begingroup$

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,*)".

$\endgroup$
4
  • $\begingroup$ Not sure I follow how it's not an inconsistency. Say that (1,1) and (4,2) are writes to the same key in a datastore. Then P3 is applying these writes backwards and replaying the logs from P3 would result in a different result than what is in (4,2). $\endgroup$
    – RSHAP
    May 24, 2022 at 15:00
  • $\begingroup$ Yes, there is an inconsistency, but in a different sense. There are many kinds of inconsistencies. For example, one child loves math and the other hates it even though both have been brought up in the same environment. Is there an inconsistency here? Certainly. Does that inconsistency indicate a violation of "causal ordering" or "happens before" chain? No. $\endgroup$
    – John L.
    May 24, 2022 at 20:58
  • $\begingroup$ Please come to chat with me. $\endgroup$
    – John L.
    May 24, 2022 at 21:02
  • $\begingroup$ I think the answer is that the implementation and results from the question are correct but my understanding of what "causal" means (and how it's used) is incomplete. But that is a different question. $\endgroup$
    – RSHAP
    May 25, 2022 at 1:47

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.