Logical Clocks: Lamport Timestamps

Question

I am currently trying to understand Lamport timestamps. Consider two processes P1 (producing events a1, a2,...) and P2 (producing events b1, b2,...). Let C(e) denote the Lamport timestamp associated with event an e. I created timestamps for each event as described in the Wikipedia article about Lamport timestamps:

According to Wikipedia, the following relation is true for all events e1, e2:

If e1 happened before e2, then C(e1) < C(e2).

Let's look at a1 and b2. Clearly a1 happened before b2, and since C(a1) = 1 and C(b2) = 3, the relation holds true: C(a1) < C(b2).

Problem: The relation doesn't hold true for b3 and a3. Obviously, b3 happened before a3. However, C(b3) = 4 and C(a3) = 3. So C(b3) < C(a3) does not apply.

What did I misunderstand? Help is much appreciated!

Answer 1

I spotted my error. I wrote:

If e1 happened before e2, then C(e1) < C(e2).

However, Lamport defined "happened before" as a partial ordering. This is what Wikipedia says about partially ordered sets:

Such a relation is called a partial order to reflect the fact that not every pair of elements need be related: for some pairs, it may be that neither element precedes the other in the poset.

According to Lamport's definition of "happened before", b3 and a3 aren't related, thus b3 didn't "happen before" a3, thus the equasion stated in the question doesn't have to hold true.

Answer 2

Yes, that definition might be slightly confusing. It’s correct what everyone else said so far, however maybe there is one word missing, to understand the system better. - concurrent

If your processes p1 and p2 are running on the same machine, there really isn't too much of a need to use lamport clocks (maybe some extremely specific case). Instead you can just use the clock provided by your OS. But what if p1 and p2 are on computers which are separated by a slow and unreliable network?

Lamport assumes, you can't trust your local clock and you don't have any global state of the distributed system, in which order events on 2 separate computers occurred. That's when you call those events occurring concurrently.

When you'd be debugging the execution of the distributed system and you'd see events a3 and b3 naturally you'd assume, a3 happened before b3. In your specific case you'd now claim, yeah, but that's wrong. However, because the events aren't related, as they didn't communicate with each other, the order is generally assumed to be concurrent and in such a case it doesn't matter which one happened first or second, for the whole execution of the system.

Since computers and networks are working so fast and still very precisely, it's sometimes difficult to comprehend, let's look at the same thing slightly differently:

p1 and p2 are two people living few 100 years ago in two different valleys. They communicate together using pidgins and never talk about when they did a certain task, just what they did. This way, nobody could know, if a3 happened before b3 or the other way around, hence they happened concurrently. Maybe not nobody, god watching from up on p1 and p2 could see it.

Unfortunately, when you have a distributed system, you can't be god and watching p1 and p2 at the same time, just out of the reason that messages from p1 might take longer than from p2. So even though your monitoring system (god) has received the information of b3 before it received the information about a4 it doesn't mean they happened in that order, maybe the packages containing information about a4 took just a longer or slower path.

In the end, there is another thing called vector clocks. Each process has a lamport clock for every process in the system. The key here is, event a would only happen before event b if all lamport clocks of a were smaller or equal those of b. If you'll try it out on your little example, you'll see that no event happened before the other => they are concurrent.

Answer 3

Lamport assumes that: we cannot in general use physical time to find out the order of any arbitrary pair of events occurring within it. In the proposed example, you ignore this assumption.

P1 and P2 increment their clocks independently. When an event occurs, the originating process sends its current value to the target process, which checks whether the value received is smaller than its current value. If it is, it changes its current value to received value + 1, else it discards the received value. In your case, P1 and P2 do not send their events a3 and b3.

Answer 4

Obviously, b3 happened before a3

Well, only assuming there’s a universal clock that both A and B agree on and can use for their timestamping. If such thing existed we wouldn’t need the Lamport clock at all!

When making the drawing you used a physical clock of your choice to place the events on the horizontal axis. The problem is that A and B are in general not able to agree on a physical clock readings. Their clocks may drift etc, there’s no way to perfectly align their clocks either (unless their both in the same place).

So, it comes down to the definition of happens before. How can we define it in a distributed system without resorting to the universal physical clock? It turns out that the best definition we can come up with isn’t as strong as that provided by the universal physical clock where two events are either happening on the same moment or one precedes another.

Our new definition only provides partial ordering. There will be events which can be compared and events which are incomparable (called concurrent). It doesn’t make any sense to ask the “happened before?” questions when two events are concurrent! This is somewhat similar to Special Relativity time cones but let me get back to the topic. What is the definition of happens before that Lamport clock readings promises to follow in the (one way) relationship you quoted? Think Leslie Lamport provided such definition in his original paper. Anyway. The definition goes like this:

An event a happened before event b if any of these is true:

1. a and b happened in the same process and a happened before b in the ordinary sense (we can easily compare two events in the same process by timestamping them with a monotonic clock)
2. a is the event of sending a message by one process and b is the event of receiving this message in another process.
3. There is an event e such that a happened before e and e happened before b (transitivity).

Such definition can be intuitively understood by saying that a happened before b if a could cause (affect) b. It’s the causality that we are interested in. If a could cause b then their Lamport inequality holds.