1.

Program for simulating Lamport Logical Clock

THEORY:

Inherent Limitations of a Distributed System

Absence of Global clock

•difficult to make temporal order of events
•difficult to collect up-to-date information on the state of the entire system absence of Shared
Memory
•no up-to-date state of the entire system to any individual process as there's no shared memory
•coherent view -- all observations of different processes ( computers ) are made at the same
physical time we can obtain a coherent but partial view of the system or incoherent view of the
system
• complete view ( global state ) -- local views ( local states ) + messages in transit difficult to
obtain a coherent global state

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.
e11 → e12 , e12 → e22e21 → e13 , e14 || e24

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

PROGRAM:

#include<stdio.h>
#include<conio.h>
#include<iostream.h>
#include<stdlib.h>
#include<graphics.h>
#include<string.h>
#include<dos.h>
void main(){
int s[4][9],n,m=0;
int i,j,next=0,step=0;
int msg[10][4]={0},totmsg;
char op;
int pi,pj,ei,ej;
clrscr();
cout<<"\nProgram for Lamport Logical Clock";
cout<<"\nEnter Number Of Process ";
cin>>n;
for(i=0;i<n;i++){
cout<<"\nEnter number of STATES of process P"<<i<<" ";
cin>>s[i][8];
for(j=1;j<=s[i][8];j++){
s[i][j]=j;
}
}
do{
cout<<"\nEnter message transit";
cout<<"\nFROM ->\nEnter Process Number P";
cin>>msg[m][0];
cout<<"\nEnter Event Number e";
cin>>msg[m][1];
cout<<"\nTO ->\nEnter Process Number P";
cin>>msg[m][2];
cout<<"\nEnter Event Number e";
cin>>msg[m][3];
cout<<"\n\nPress 'y' to continue";
op=getch();
cout<<op;
m++;
totmsg=m;
}while(op=='y');
m=0;
for (i=0;i<totmsg;i++)
{
pi=msg[i][0];
ei=msg[i][1];
pj=msg[i][2];
ej=msg[i][3];
if(s[pj][ej]< (s[pi][ei]+1)){
s[pj][ej]=s[pi][ei]+1;
for (j=ej+1;j<=s[pj][8];j++){
s[pj][j]=s[pj][j-1]+1;
}
}
}
int gd=DETECT,gm;
initgraph(&gd,&gm,"C:\\TC\\BGI");
outtextxy(200,15,"Program For Lamport Logical Clock");
//drawing process and events
for(i=0;i<n;i++){
char* p1;
itoa(i,p1,10);
outtextxy(5,100+next,"P");
outtextxy(13,100+next,p1);
line(100,100+next,600,100+next);
for(j=1;j<=s[i][8];j++){
char* p2;
itoa(j,p2,10);
outtextxy(100+step,90+next,"e");
outtextxy(110+step,90+next,p2);
//timestamp
char* p3;
itoa(s[i][j]-1,p3,10);
outtextxy(100+step,110+next,"t");
outtextxy(110+step,110+next,p3);
circle(105+step,100+next,5);
step+=50;
}
step=0;
next+=100;
}
delay(2000);
//drawing message transit
for(m=0;m<totmsg;m++){
setlinestyle(SOLID_LINE,1,3);
setcolor(m+4);
line(msg[m][1]*50+50,msg[m][0]*100+100,msg[m][3]*50+50,msg[m][2]*100+100);
if (msg[m][2]>msg[m][0]){
line(msg[m][3]*50+50,msg[m][2]*100+100,msg[m][3]*50+50,msg[m][2]*100+90);
line(msg[m][3]*50+50,msg[m][2]*100+100,msg[m][3]*50+40,msg[m][2]*100+90); }
else{
line(msg[m][3]*50+50,msg[m][2]*100+100,msg[m][3]*50+50,msg[m][2]*100+110);
line(msg[m][3]*50+50,msg[m][2]*100+100,msg[m][3]*50+40,msg[m][2]*100+110);
}
}
getch();
}
2. Program for implementing Vector Clock

THEORY:

Vector clock is an algorithm for generating a partial ordering of events in a distributed system
and detecting causality violations. Just as in Lamport timestamps, interprocess messages contain
the state of the sending process's logical clock. A vector clock of a system of N processes is an
array/vector of N logical clocks, one clock per process; a local "smallest possible values" copy of
the global clock-array is kept in each process, with the following rules for clock updates:

Initially all clocks are zero.

Each time a process experiences an internal event, it increments its own logical clock in the
vector by one.
Each time a process prepares to send a message, it increments its own logical clock in the vector
by one and then sends its entire vector along with the message being sent. Each time a process
receives a message, it increments its own logical clock in the vector by one and updates each
element in its vector by taking the maximum of the value in its own vector clock and the value in
the vector in the received message (for every element).
The vector clocks algorithm was independently developed by Colin Fidge and Friedemann
Mattern in 1988.

PROGRAM:

#include<stdio.h>
#include<conio.h>
#include<stdio.h>
#include<stdlib.h>
long *p1(int i,long *comp);
long *p2(int i,long *comp);
long *p3(int i,long *comp);
void main()
{
long start[]={0,0,0},*vector;
clrscr();
while(!kbhit())
{
p1(1,&start[0]);
}
printf("\n Process Vector\n");
vector=p1(0,&start[0]);
printf("p1[%ld%ld%ld]\n",*vector,*(vector+1),*(vector+2));
vector=p2(0,&start[0]);
printf("p2[%ld%ld%ld]\n",*vector,*(vector+1),*(vector+2));
vector=p3(0,&start[0]);
printf("p3[%ld%ld%ld]\n",*vector,*(vector+1),*(vector+2));
}
long *p1(int i,long *comp)
{
static long a[]={0,0,0};
int next;
if(i==1)
{
a[0]++;
if(*(comp+1)>a[1])
a[1]=*(comp+1);
if(*(comp+2)>a[2])
a[2]=*(comp+2);
next=random(2);
if(next==0)
p2(1,&a[0]);
else if(next==1)
p3(1,&a[0]);
return(&a[0]);
}
else
return(&a[0]);
}
long *p2(int i,long *comp)
{
static long b[]={0,0,0};
int next;
if(i==1)
{
b[i]++;
if(*comp>b[0])
b[0]=*(comp);
if(*(comp+2)>b[2])
b[2]=*(comp+2);
next=random(2);
if(next==0)
p1(1,&b[0]);
else if(next==1)
p3(1,&b[0]);
return &b[0];
}
else
return &b[0];
}
long *p3(int i,long *comp)
{
static long c[]={0,0,0};
int next;
if(i==1)
{
c[2]++;
if(*comp>c[0])
c[0]=*(comp);
if(*(comp+1)>c[1])
c[1]=*(comp+1);
next=random(2);
if(next==0)
p1(1,&c[0]);
return &c[0];
}
else
return &c[0];}
3. Program for simulating Distributed Mutual Exclusion

THEORY:

Distributed mutual exclusion (DME) coordinates software on different computers so that they
Agree upon assigning a resource or section of code to one particular task.

Requirement
• Mutual Exclusion
• Freedom from deadlock
• Eventual entry(freedom from starvation)
• All processes must participate equally.
• Only interested processes participate.

Assumptions
•N nodes randomly request access.
•Messages are not lost or corrupted.
•Message transmissions take a finite, variable, non-zero time.
•Messages arrive in order.
•Transmission time might not be transitive.
•Network is fully connected.

Mutual Exclusion Goals

• Minimize the number of messages sent.
• Grant permission in order of request
• Fault tolerant
• Fair to all systems
• Scalable

PROGRAM:

mutex1.c
#include <stdio.h>
#include <stdlib.h>
#include <pthread.h>
void *functionC();
pthread_mutex_t mutex1 = PTHREAD_MUTEX_INITIALIZER;
int counter = 0;
main()
{
int rc1, rc2;
pthread_t thread1, thread2;
/* Create independent threads each of which will execute functionC */
if( (rc1=pthread_create( &thread1, NULL, &functionC, NULL)) )
{
printf("Thread creation failed: %d\n", rc1);
}
if( (rc2=pthread_create( &thread2, NULL, &functionC, NULL)) )
{
printf("Thread creation failed: %d\n", rc2);
}
/* Wait till threads are complete before main continues. Unless we */
/* wait we run the risk of executing an exit which will terminate */
/* the process and all threads before the threads have completed. */
pthread_join( thread1, NULL);
pthread_join( thread2, NULL);
exit(0);
}
void *functionC()
{
pthread_mutex_lock( &mutex1 );
counter++;
printf("Counter value: %d\n",counter);
pthread_mutex_unlock( &mutex1 );
}
Compile: cc -lpthread mutex1.c
Run: ./[Link]
Results:
Counter value: 1 Counter value: 2

join1.c
#include <stdio.h>
#include <pthread.h>
#define NTHREADS 10
void *thread_function(void *);
pthread_mutex_t mutex1 = PTHREAD_MUTEX_INITIALIZER;
int counter = 0;
main()
{
pthread_t thread_id[NTHREADS];
int i, j;
for(i=0; i < NTHREADS; i++)
{
pthread_create( &thread_id[i], NULL, thread_function, NULL );
}
for(j=0; j < NTHREADS; j++)
{
pthread_join( thread_id[j], NULL);
}
/* Now that all threads are complete I can print the final result. */
/* Without the join I could be printing a value before all the threads */
/* have been completed.*/
printf("Final counter value: %d\n", counter);
}
void *thread_function(void *dummyPtr)
{
printf("Thread number %ld\n", pthread_self());
pthread_mutex_lock( &mutex1 );
counter++;
pthread_mutex_unlock( &mutex1 );
}
Compile:cc-lpthreadjoin1.c
Run:./[Link]
Results:
Thread number 1026
Thread number 2051
Thread number 3076
Thread number 4101
Thread number 5126
Thread number 6151
Thread number 7176
Thread number 8201
Thread number 9226
Thread number 10251
Final counter value: 10

cond1.c
#include <stdio.h>
#include <stdlib.h>
#include <pthread.h>
pthread_mutex_t count_mutex = PTHREAD_MUTEX_INITIALIZER;
pthread_cond_t condition_var = PTHREAD_COND_INITIALIZER;
void *functionCount1();
void *functionCount2();
int count = 0;
#define COUNT_DONE 10
#define COUNT_HALT1 3
#define COUNT_HALT2 6
main()
{
pthread_t thread1, thread2;
pthread_create( &thread1, NULL, &functionCount1, NULL);
pthread_create( &thread2, NULL, &functionCount2, NULL);
pthread_join( thread1, NULL);
pthread_join( thread2, NULL);
printf("Final count: %d\n",count);
exit(0);
}
// Write numbers 1-3 and 8-10 as permitted by functionCount2()
void *functionCount1()
{
for(;;)
{
// Lock mutex and then wait for signal to relase mutex
pthread_mutex_lock( &count_mutex );
// Wait while functionCount2() operates on count
// mutex unlocked if condition varialbe in functionCount2() signaled.
pthread_cond_wait( &condition_var, &count_mutex );
count++;
printf("Counter value functionCount1: %d\n",count);
pthread_mutex_unlock( &count_mutex );
if(count >= COUNT_DONE) return(NULL);
}
}
// Write numbers 4-7
void *functionCount2()
{
for(;;)
{
pthread_mutex_lock( &count_mutex );
if( count < COUNT_HALT1 || count > COUNT_HALT2 )
{
// Condition of if statement has been met.
// Signal to free waiting thread by freeing the mutex.
// Note: functionCount1() is now permitted to modify "count".
pthread_cond_signal( &condition_var );
}
else
{
count++;
printf("Counter value functionCount2: %d\n",count);
}
pthread_mutex_unlock( &count_mutex );
if(count >= COUNT_DONE) return(NULL);
}}
Compile: cc -lpthread cond1.c
Run: ./[Link]
Results:
Counter value functionCount1: 1
Counter value functionCount1: 2
Counter value functionCount1: 3
Counter value functionCount2: 4
Counter value functionCount2: 5
Counter value functionCount2: 6
Counter value functionCount2: 7
Counter value functionCount1: 8
Counter value functionCount1: 9
Counter value functionCount1: 10
Final count: 10
4. Program for implementing Distributed Chat Server using TCP
Sockets

THEORY:

A socket is the mechanism that most popular operating systems provide to give programs access
to the network. It allows messages to be sent and received between applications (unrelated
processes) on different networked machines.
The sockets mechanism has been created to be independent of any specific type of network. IP,
however, is by far the most dominant network and the most popular use of sockets. This tutorial
provides an introduction to using sockets over the IP network (IPv4).
This tutorial will not try to cover the entire topic of sockets. There are tutorials on the web that
delve into far greater detail. On-line manual pages will provide you with the latest information
on acceptable parameters and functions. The interface described here is the system call interface
provided by the OS X, Linux, and Solaris operating systems and is generally similar amongst all
Unix/POSIX systems (as well as many other operating systems).

PROGRAM:

#include <stdio.h>
#include <errno.h>
#include <stdlib.h>
#include <unistd.h>
#include <sys/types.h>
#include <sys/socket.h>
#include <netinet/in.h>
#include <netdb.h>
#define PORT 5555
#define MAXMSG 512
int
read_from_client (int filedes)
{
char buffer[MAXMSG];
int nbytes;
nbytes = read (filedes, buffer, MAXMSG);
if (nbytes < 0)
{
/* Read error. */
perror ("read");
exit (EXIT_FAILURE);
}
else if (nbytes == 0)
/* End-of-file. */
return -1;
else
{
/* Data read. */
fprintf (stderr, "Server: got message: `%s'\n", buffer);
return 0;
}
}
int
main (void)
{
extern int make_socket (uint16_t port);
int sock;
fd_set active_fd_set, read_fd_set;
int i;
struct sockaddr_in clientname;
size_t size;
/* Create the socket and set it up to accept connections. */
sock = make_socket (PORT);
if (listen (sock, 1) < 0)
{
perror ("listen");
exit (EXIT_FAILURE);
}
/* Initialize the set of active sockets. */
FD_ZERO (&active_fd_set);
FD_SET (sock, &active_fd_set);
while (1)
{
/* Block until input arrives on one or more active sockets. */
read_fd_set = active_fd_set;
if (select (FD_SETSIZE, &read_fd_set, NULL, NULL, NULL) < 0)
{
perror ("select");
exit (EXIT_FAILURE);
}
/* Service all the sockets with input pending. */
for (i = 0; i < FD_SETSIZE; ++i)
if (FD_ISSET (i, &read_fd_set))
{
if (i == sock)
{
/* Connection request on original socket. */
int new;
size = sizeof (clientname);
new = accept (sock,
(struct sockaddr *) &clientname,
&size);
if (new < 0)
{
perror ("accept");
exit (EXIT_FAILURE);
}
fprintf (stderr,
"Server: connect from host %s, port %hd.\n",
inet_ntoa (clientname.sin_addr),
ntohs (clientname.sin_port));
FD_SET (new, &active_fd_set);
}
else
{
/* Data arriving on an already-connected socket. */
if (read_from_client (i) < 0) {
close (i);
FD_CLR (i, &active_fd_set);
}}}}}
[Link] for implementing Java RMI Mechanism

THEORY:

The Java Remote Method Invocation (Java RMI) is a Java API that performs the object-oriented
equivalent of remote procedure calls (RPC), with support for direct transfer of serialized Java
objects and distributed garbage collection.
The original implementation depends on Java Virtual Machine (JVM) class representation
mechanisms and it thus only supports making calls from one JVM to another. The protocol
underlying this Java-only implementation is known as Java Remote Method Protocol (JRMP).
In order to support code running in a non-JVM context, a CORBA version was later developed.
Usage of the term RMI may denote solely the programming interface or may signify both the
API and JRMP, whereas the term RMI-IIOP (read: RMI over IIOP) denotes the RMI interface
delegating most of the functionality to the supporting CORBA implementation.

PROGRAM:

[Link]
import [Link].*;
import [Link].*;
public class Hello extends UnicastRemoteObject implements HelloInterface {
private String message;
public Hello (String msg) throws RemoteException {
message = msg;
}
public String say() throws RemoteException {
return message;
}
}

[Link]
import [Link];
public class HelloClient
{
public static void main (String[] argv) {
try {
HelloInterface hello =(HelloInterface) [Link] ("//[Link]/Hello");
[Link] ([Link]());
}
catch (Exception e){
[Link] ("HelloClient exception: " + e);}
}
}
[Link]
import [Link].*;
public interface HelloInterface extends Remote {
public String say() throws RemoteException;
}

[Link]
import [Link];
public class HelloServer
{
public static void main (String[] argv)
{
try {
[Link] ("Hello", new Hello ("Hello,From [Link] pvt ltd!"));
[Link] ("Server is connected and ready for operation.");
} catch (Exception e) {
[Link] ("Server not connected: " + e);
}
}}