In this tutorial you are going to learn about Lamport's Logical Clock in Distributed System.
Lamport’s Logical Clocks
In practice many people use portable watches to order the occurrence of the events. For instance, we say that an event that took place in 2:00 AM in the morning occurred before 2:00 PM in the afternoon. In distributed systems, we cannot depend on portable watches as they are not always accurate, so we use real time to order the occurrence of the events. In this case, we can use sensible clocks to create partial or complete order of events. It provides the basis for a highly advanced Vector Clock algorithm. As there is an absence of global clock in the distributed system, Lamport’s Logical Clock is very much required. This tutorial explores the concept and use of sensational clocks invented by Leslie Lamport in his first paper “Time, Clocks, and Event Arrangements in Distributed System”.
Mathematical Skills Used
Sets are represented as a set of well-defined objects or elements and do not change from one person to another. The set is capitalized. The number of elements in a limited set is known as the cardinal number of the set. As a set is usually represented by a capital letter. Thus, A is a set and 1, 2, 3, 4, 5 are elements of a set or members of a set. The elements listed in the set can be in any way but cannot be repeated. All the fixed elements are represented by a lower case in case they are alphabetical.
Sub-sets are part of one of the mathematical concepts called Sets. Set a set of objects or elements, collected in italicized brackets, such as {a, b, c, d}. If set A is a set of equal numbers and set B contains {2,4,6}, then B is a subset of A, defined by B⊆A and A is a superset B. Learn Sets Subset And Superset understanding the difference.
The word ‘product’ mathematically indicates the result obtained when two or more values are multiplied together. For example, 45 is a product of 9 and 5. One has to become accustomed to basic operations in sets such as Union and Intersection, which are made up of 2 or more sets. Cartesian Product is also one such function performed in two sets, which returns a set of ordered pears.
Mathematical relationships describe the relationships between two different groups of information. Considering the two sets, a relationship between them will be established if there is a connection between the elements of two or more empty sets.
At a school meeting in the morning, students should stand in a line that rises to the level of all the students. This defines the structured relationship between students and their length. Therefore, we can say , ‘A group of ordered pears is defined as a relationship.’
Algorithm
- Occurred before the relationship (->): a -> b, meaning ‘a’ occurred before ‘b’.
- Reasonable Clock: The conditions for smart watches are:
- [C1]: Ci (a) <Ci (b), [Ci -> Logical Clock, If 'a' happened before 'b', then 'time' would be less than'b' in a certain process.]
- [C2]: Ci (a) <Cj (b), [The clock value of Ci (a) is less than Cj (b)]
Partial and Total Ordering
Partial Ordering - An irreflexive partial ordering on a set AA is a relation on AA that satisfies three properties.
- irreflexivity: a≮aa≮a
- antisymmetry: if a<ba<b then b≮ab≮a
- transitivity: if a<ba<b and b<cb<c then a<ca<c
Physical timing creates a natural “pre-existing” timeline(Irreflexive partial ordering of events). If we look at two incidents A and B, we can use physical time to know that A has happened before B ,B has happened before A, or the two are unrelated (i.e. occur simultaneously). Since virtual clocks are inaccurate, we cannot spend real time on distributed systems, but we would still like a consistent component of events.
Total Ordering - An irreflexive total ordering is a irreflexive partial ordering that satisfices another condition.
- totality: if a≠ba≠b then a<ba<b or b<ab<a.
For example, the "less-than" relation on natural numbers is an irreflexive total ordering. For all naturals ii and jj where i≠ji≠j, i<ji<j or j<ij<i.
Implementation
The implementation provides a lamport wind function that takes a list of each task representing the process. Tasks take the example of Clock_i which supports three modes: send (n), recv (n), and local (). the wind returns the task you would like to set up the space graphs we used to visualize sensible clocks. Here is an example in python programming.
EXAMPLE:
Import lamport
def f(clock):
clock.recive(1)
clock.send(1)
def g(clock):
clock.send(0)
clock.recive(0)
Lamport.wind([f,g])()
This article on Lamport's Logical Clock in Distributed System is contributed by Harnoor Kaur. If you like TheCode11 and would like to contribute, you can also write your article and mail to thecode11info@gmail.com
