Search code examples
messagingdistributedclocktimingdistributed-system

Logical Clocks: Lamport Timestamps

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:

enter image description here

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!

Solution

  • 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.