EXPERIMENT 2
Aim:
Implement Berkeley’s Clock Synchronization Algorithm.
Description:
In this internal synchronization algorithm, a coordinator computer is chosen to act as the
master. Unlike in Cristian’s protocol, this computer periodically polls the other computers
whose clocks are to be synchronized, called slaves. The slaves send back their clock values to
it. The master estimates their local clock times by observing the round-trip times (similarly
to Cristian’s technique), and it averages the values obtained (including its own clock’s
reading). The balance of probabilities is that this average cancel out the individual clocks’
tendencies to run fast or slow. The accuracy of the protocol depends upon a nominal
maximum round-trip time between the master and the slaves. The master eliminates any
occasional readings associated with larger times than this maximum.
Algorithm:
1) An individual node is chosen as the master node from a pool nodes in the network. This
node is the main node in the network which acts as a master and rest of the nodes act as
slaves. Master node is chosen using a election process/leader election algorithm.
2) Master node periodically pings slaves nodes and fetches clock time at them
using Cristian’s algorithm.
3) Master node calculates average time difference between all the clock times received and
the clock time given by master’s system clock itself. This average time difference is added to
the current time at master’s system clock and broadcasted over the network.
Code:
----Server-Side Code----
#include <unistd.h>
#include <stdio.h>
#include <sys/socket.h>
#include <stdlib.h>
#include <netinet/in.h>
#include <string.h>
#include <pthread.h>
#include <iostream>
using namespace std;
#define PORT 8080
int Flag_fin = 0;
int input[2];
int n = 0;
int sum = 0;
int local_time = rand()%24+1;
void * socketThread(void *arg)
{
int new_socket = *((int *)arg);
int berk;
char buffer[1024] = {0};
char hello[1024];
string s;
int valread = read( new_socket , buffer, 1024);
printf("%s\n",buffer);
//convert string sent from client into integer and store in an array
input[n] = stoi(buffer);
n++;
cout << "Time Sent by Client" << n << ": " << buffer << "\n";
//setting a limit of max of 2 clients can connect to the server therefore 2 clocks send time to
coordinator
if (n == 2)
{
for(int i = 0;i < n; i++)
{
int diff = input[i] - local_time;
sum = sum+diff;
}
cout << "Berkley Sum: " << sum << endl;
berk = sum/(n+1);
cout << "Average: " << berk << endl;
local_time = local_time+berk;
Flag_fin = 1;
}
while(Flag_fin != 1);
s = to_string(local_time);
strcpy(hello,s.c_str());
write(new_socket , hello , strlen(hello));
cout << "Updated Localtime Sent to Client!" << endl;
pthread_exit(NULL);
}
int main(int argc, char const *argv[])
{
int server_fd, new_socket, valread;
struct sockaddr_in address;
int opt = 1;
int addrlen = sizeof(address);
char buffer[1024] = {0};
char *hello = "Hello from Server";
pthread_t tid[100];
//generating random time for server
srand(time(0));
cout << local_time << " is the local time" << endl;
// Creating socket file descriptor
if ((server_fd = socket(AF_INET, SOCK_STREAM, 0)) == 0)
{
perror("socket failed");
exit(EXIT_FAILURE);
}
// Attaching socket to the port 8080
if (setsockopt(server_fd, SOL_SOCKET, SO_REUSEADDR | SO_REUSEPORT,
&opt, sizeof(opt)))
{
perror("setsockopt");
exit(EXIT_FAILURE);
}
address.sin_family = AF_INET;
address.sin_addr.s_addr = INADDR_ANY;
address.sin_port = htons( PORT );
// Binding the socket
if (bind(server_fd, (struct sockaddr *)&address,
sizeof(address))<0)
{
perror("Bind Failed");
exit(EXIT_FAILURE);
}
//Listen for connections
if (listen(server_fd, 3) < 0)
{
perror("Listen");
exit(EXIT_FAILURE);
}
int i = 0;
//Accepting multiple clients and creating threads for each one of them
while(1)
{
if ((new_socket = accept(server_fd, (struct sockaddr *)&address,
(socklen_t*)&addrlen))<0)
{
perror("Accept");
exit(EXIT_FAILURE);
}
if(pthread_create (&tid[i],NULL,socketThread,&new_socket) != 0)
{
cout << "New Thread Failed to Create!\n";
}
}
return 0;
}
----Client-Side Code----
#include <stdio.h>
#include <sys/socket.h>
#include <arpa/inet.h>
#include <unistd.h>
#include <string.h>
#include <iostream>
using namespace std;
#define PORT 8080
int main(int argc, char const *argv[])
{
int sock = 0, valread;
struct sockaddr_in serv_addr;
char hello[1024];
string s;
//Generating random local time
srand(time(0));
int time_sent = rand()%24+1;
cout << "Local Time: " << time_sent << endl;
s = to_string(time_sent);
strcpy(hello,s.c_str());
char buffer[1024] = {0};
//Creating a socket
if ((sock = socket(AF_INET, SOCK_STREAM, 0)) < 0)
{
printf("\n Socket Creation Error! \n");
return -1;
}
serv_addr.sin_family = AF_INET;
serv_addr.sin_port = htons(PORT);
// Convert IPv4 and IPv6 addresses from text to binary form
if(inet_pton(AF_INET, "127.0.0.1", &serv_addr.sin_addr)<=0)
{
printf("\nInvalid address / Address not supported \n");
return -1;
}
//Connecting to the server
if (connect(sock, (struct sockaddr *)&serv_addr, sizeof(serv_addr)) < 0)
{
printf("\nConnection Failed! \n");
return -1;
}
//Sending time to server
send(sock , hello , strlen(hello) , 0 );
printf("Time Sent\n");
//Saving the Berkley Time from server as new_time and telling the time difference between
new and old time
while(1)
{
while(valread = read( sock , buffer, 1024) > 0)
{
printf("%s\n",buffer );
int new_time = stoi(buffer);
cout << "Old Time: " << time_sent << endl;
cout << "New Time: " << new_time << endl;
cout << "Time Difference: " << new_time-time_sent << endl;
return 0;
}
}
return 0;
}
Result/Output:
----Server----
----Client1----
----Client2----
Discussion
Advantages
• The Berkeley algorithm eliminates readings from faulty clocks. Such clocks could
have a significant adverse effect if an ordinary average was taken so instead the
master takes a fault-tolerant average. That is, a subset is chosen of clocks that do not
differ from one another by more than a specified amount, and the average is taken
of readings from only these clocks.
• No separate time source needed, one of the nodes can be elected as leader and then
act as the time server
Disadvantages
• Berkeley’s Algorithm is highly centralized so it has problems like single point of
failure, congestion around the server.
Findings & Learnings
• In this experiment we learnt how to implement Berkeley clock synchronization
algorithm a distributed algorithm for timekeeping.
• Berkeley clock synchronization algorithm is only suitable in LANs with small number
of machines due to problems in case of large systems like load on central server and
variance in message delay in large networks.
