Program No: 1
1.1 Objective 1.2 Theory 1.3 Algorithm 1.4 Questions
1.1 OBJECTIVE: Simulate the functioning of Lamport’s Logical Clock in ‘C’.
1.2 THEORY:
Leslie Lamport proposed this scheme to provide ordering of events in a distributed environment
using logical clocks. Because it is impossible to have perfectly synchronized clocks and global
time in a distributed system, it is often necessary to use logical clocks instead.
Definitions:
Happened Before Relation (->). This relation captures causal dependencies between events, that
is, whether or not events have a cause and effect relation. This relation (->) is defined as follows:
● a -> b, if a and b are in the same process and a occurred before b.
● a -> b, if a is the event of sending a message and b is the receipt of that message by
another process.
● If a -> b and b -> c, then a -> c - that is, the relation has the property of transitivity.
Causally Related Events: If event a -> event b, then a causally affects b.
Concurrent Events: Two distinct events a and b are concurrent (a || b) if (not) a -> b and (not) b
-> a. That is, the events have no causal relationship. This is equivalent to b || a.
For any two events a and b in a system, only one of the following is true: a -> b, b -> a, or a || b.
Lamport introduced a system of logical clocks in order to make the -> relation possible. It works
like this: Each process Pi in the system has its own clock Ci. Ci can be looked at as a function that
assigns a number, Ci(a) to an event a. This is the timestamp of the event a in process Pi. These
numbers are not in any way related to physical time -- that is why they are called logical clocks.
These are generally implemented using counters, which increase each time an event occurs.
Generally, an event's timestamp is the value of the clock at that time it occurs.
Conditions Satisfied by the Logical Clock system:
For any events a and b, if a -> b, then C(a) < C(b). This is true if two conditions are met:
● If a occurs before b, then Ci(a) < Ci(b).
● If a is a message sent from Pi and b is the recept of that same message in Pj, then Ci(a) <
Cj(b).
Implementation Rules Required
● Clock Ci is incremented for each event: Ci := Ci + d (d > 0)
if a is the event of sending a message from one process to another, then the receiver sets its clock
to the max of its current clock and the sender's clock - that is, Cj := max(Cj, tm + d) (d > 0) .
1.3 ALGORITHM :
// declaration and initial values of global variables
0 Enter, Number: array [1..N] of integer = {0};
// logic used by each thread...
// where "(a, b) < (c, d)" means "(a < c) or ((a == c)
and (b < d))"
1 Thread(i) {
2 while (true) {
3 Enter[i] = 1;
4 Number[i] = 1 + max(Number[1], ..., Number[N]);
5 Enter[i] = 0;
6 for (j = 1; j <= N; j++) {
7 while (Enter[j] != 0) {
8 // wait until thread j receives its number
9 }
10 while ((Number[j] != 0) && ((Number[j], j)
< (Number[i], i))) {
11 // wait until threads with smaller numbers or with the same
12 // number, but with higher priority, finish their work
13 }
14 }
15 Number[i] = 0;
16 }}
1.4 Questions:
a) Why the Lamport’s clock is used? Why Global clock can’t be used in
distributed systems?
Ans. To synchronize the events in a distributed system Lamport’s clock is used.
Due to clock drifting global clock can’t be used in distributed systems.
b) How is the logical clock is different from physical clock?
Ans. Logical clock is incremented according to the events occurred in processes.
So between these two events logical clock is not functional but in physical clock
is functional always.
Program:
#include<stdio.h>
#include<conio.h>
int max(int a,int b);
int main()
{
int i,j,k,p1[20],p2[20],e1,e2,dep[20][20];
printf("*** Lamport's Logical Clock ***\n");
printf("Enter the events : ");
scanf("%d %d",&e1,&e2);
for(i=0;i<e1;i++)
p1[i]=i+1;
for(i=0;i<e2;i++)
p2[i]=i+1;
printf("Enter the Dependency matrix:\n");
printf("\nEnter 1 if E1->E2 \nEnter -1, if E2->E1 \nElse Enter 0 \n\n");
printf(" ");
for(i=0;i<e2;i++)
printf(" e2%d",i+1);
for(i=0;i<e1;i++){
printf("\ne1%d ",i+1);
for(j=0;j<e2;j++){
scanf("%d",&dep[i][j]);
}
}
for(i=0;i<e1;i++){
for(j=0;j<e2;j++){
//change the Time stamp if dependency exist
if(dep[i][j]==1){
p2[j]=max(p2[j],p1[i]+1);
for(k=j;k<e2;k++)
p2[k+1]=p2[k]+1;
}
//change the Time stamp if dependency exist
if(dep[i][j]==-1){
p1[i]=max(p1[i],p2[j]+1);
for(k=i;k<e1;k++)
p2[k+1]=p1[k]+1;
}
}
}
//to print the outcome of Lamport Logical Clock
printf("\nP1 : ");
for(i=0;i<e1;i++){
printf("%d",p1[i]);
}
printf("\nP2 : ");
for(j=0;j<e2;j++)
printf("%d",p2[j]);
getch();
return 0 ;
}
//to find the maximum timestamp between two events
int max(int a, int b)
{
if (a>b)
return a;
else
return b;
The Output Of this Program :
