Logic Clock: Lamport Timestamps

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

enter image description here

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

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

Look at a1 and b2 . It is clear that a1 happened before b2 , and since C (a1) = 1 and C (b2) = 3, the relation is true: C (a1) < C (b2 ) .

Problem : The relation does not hold for b3 and a3 . Obviously, b3 happened before a3 . However, C (b3) = 4 and C (a3) ​​= 3 . Thus, C (b3) C (a3) does not apply.

What did I misunderstand? Help is much appreciated!

+6
source share
3 answers

I noticed my mistake. I wrote:

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

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

This relationship is called partial order to reflect the fact that not every pair of elements needs to be connected: for some pairs it may be that none of the elements precedes the other in poset.

According to Lamport’s definition, “happened earlier” b3 and a3 are not connected, so b3 did not happen “ a3 , so the evasion mentioned in the question does not have to be performed.

+1
source

Yes, this definition can be a bit confusing. It is true that everyone else said, however, perhaps there is one word to better understand the system. - parallel

If you are running p1 and p2 processes on the same computer, in fact you don't need to use lamport clocks too much (maybe some extremely specific case). Instead, you can simply use the clock provided by your OS. But what if p1 and p2 are on computers that are separated by a slow and unreliable network?

Lamport assumes that you cannot trust your local clock, and you do not have the global state of the distributed system in which order events occurred on two separate computers. This is when you trigger those events that happen simultaneously.

When you debug the execution of a distributed system, and you naturally count events a3 and b3 , a3 happened before b3 . In your particular case, you are now declaring yes, but that is wrong. However, since the events are not related to each other, since they do not interact with each other, the order is usually considered parallel, and in this case it does not matter which one happened first or second for the entire system execution.

Since computers and networks are so fast and still very accurate, they are sometimes difficult to understand, let's look at the same thing a little differently:

p1 and p2 are two people living several years ago in two different valleys. They communicate together using pidgins and never talk about when they performed a specific task, only what they did. Thus, no one could know who, if a3 happened before b3 or vice versa, so they happened at the same time. Maybe not someone, the god who looked at p1 , and p2 could see it.

Unfortunately, when you have a distributed system, you cannot be a god and watch p1 and p2 at the same time, simply because messages from p1 may take longer than from p2 . Therefore, despite the fact that your monitoring system (god) received information b3 before it received information about a4 , this does not mean that they occurred in this order, it is possible that packets containing information about a4 took only longer or slower way.

After all, there is one more thing called a vector clock . Each process has clock pulses for each process in the system. The key point here is event a , which will occur only before event b , if all the hours of lamport a were less than or equal to b . If you try this with your small example, you will see that nothing happened before the others => they are parallel .

+3
source

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

P1 and P2 increase their hours independently. When an event occurs, the initiating process sends its current value to the target process, which checks whether the received value is less than its current value. If so, it changes its current value to the accepted value + 1, otherwise it discards the received value. In your case, P1 and P2 do not send their events a3 and b3 .

+1
source

Source: https://habr.com/ru/post/989449/


All Articles