Synchronization In Distributed System

Every standalone system running on uniprocessor needs a mechanism similar to that of timer, which keep track of time for process execution, it also checks the time spent by the process in utilizing the various resources – CPU, I/O, memory etc.

But what about the Distributed Environment?

Distributed system is much more complex than the stand alone system, the main question that arises is how to coordinate several processes running on different systems? Even if we apply some timer mechanism still it is so messy that we cannot coordinate our timer mechanism in the right way.

For that we need a timer mechanism with synchronization among the processes, and for that we need a Global Clock. But in real time, we cannot afford the global clock, which needs the system to display the same time among the processes, which is not possible, because each CPU has its own clock.


Let’s say above example is for an unsynchronized condition of the clock, where there are two process – editor and compiler, and the clock is shown in square boxes, where the program in the editor, will always be late, or more specifically it will not be re-compiled again, because of the slower clock in the machine.

Here we specifically understand the Logical Clock, as the clock is the most important aspect in DS system, These logical clock is been more understood and deeply analyzed by Lamport, he observed that it is not required to keep all the clocks synchronized, he is more concerned towards the event ordering.

Lamport’s Event Ordering

He made some of the  following ways to understand the event ordering, based on the event among different process. He defined “Happened- before Relation” used in logical clocks, and he denotes happened-before relation as “à“that satisfies the conditions,

1. Let’s say if we have a and b events in the same process and in the event, an event occurs before b, then happened before denotes as “aà b”.
   
   
   
2. Let’s say, if a will be your sending event of one process (P1) and the b will be your receiving event of another process (P2), then happened before denotes as “aàb”. This is simple to understand that the receiver cannot receive the message unless the sending event happened.
   
   
3. The last condition given by Lamport is the “Transitive Relation” that is if aàb, and bàc, then with transitivity aàc.

Also he has assumed some more conditions as, an event can never happen beforeitself, more specifically the condition “aàa” can never happen for any event a in the process.

Two events can be concurrent, concurrency here means in terms of relation, if the two events are not related to each other, then we say that these two events are concurrent. This also means that these two concurrent events are not happening before relation. Generally this happens when two events are not taking part in any eventing or not exchanging messages directly or indirectly with each other.

Moreover, In case of concurrent events, we cannot predict which event come first and which comes after, as they are not taking part in eventing. Such scenarios of happened before relation – are called – “Casual Ordering”.

The concept of logical clocks suggests that the clock synchronization is not very important, if two process are in eventing or they are exchanging messages, then it is not necessary that their clocks should be synchronized. It suggests that what really matters is not the synchronization of the clocks but it’s the order in which the process wants to perform.
More Simplified Version

In his final report Lamport suggested these keys points towards the logical clock in Distributed System,

• Those Process that don’t interact with each other don't matter.
• Event Ordering is the key in logical clocks, rather than to have a global clock or a true time.
• Absolute correctness is less important in logical clock than consistency.

I hope you liked it. Have a good day, and thank you for reading.