Berkley’s Algorithm

Berkley’s Algorithm is mainly used in clock synchronization system. It is used in distributed systems. To implement this algorithm, we have to think that the network has no accurate time source and UTC server.

Algorithm

Step 1: First, it is necessary to choose one master node from the pool of nodes in the network. It will be chosen by leader election process algorithm. The elected node will be master and all other nodes will act as slave.

Step 2: The node which is considered as master node will send request for clock time to other nodes which are considered as slave nodes.

Step 3: The slave nodes will send the clock time to the master node.

Step 4: After fetching the clock time of all nodes, master node will calculate the average difference between the times received from slave nodes and its own time. After that, it will add this average to its current time and send over the network.

Note:

What is distributed system?

In a distributed system, we can’t find a physical connection between components but there is always a network to connect them. In this type of system, it is obvious that there will be individual local time for every nodes or components. But, we need a global time. So, we have to use clock synchronisation. This is the main concept behind the use of Berkley’s algorithm.

The following code is used to implement the approach to trigger master node:

Code:

# Python3 program to trigger master
from functools import reduce
from dateutil import parser
import threading
import datetime
import socket
import time
client_data = {}
def startReceivingClockTime(connector, address):


	while True:
		clock_time_string = connector.recv(1024).decode()
		clock_time = parser.parse(clock_time_string)
		clock_time_diff = datetime.datetime.now() - \
												clock_time


		client_data[address] = {
					"clock_time"	 : clock_time,
					"time_difference" : clock_time_diff,
					"connector"	 : connector
					}


		print("Client Data updated with: "+ str(address),
											end = "\n\n")
		time.sleep(5)


def startConnecting(master_server):
	
	while True:
		master_slave_connector, addr = master_server.accept()
		slave_address = str(addr[0]) + ":" + str(addr[1])


		print(slave_address + " got connected successfully")


		current_thread = threading.Thread(
						target = startReceivingClockTime,
						args = (master_slave_connector,
										slave_address, ))
		current_thread.start()


def getAverageClockDiff():


	current_client_data = client_data.copy()


	time_difference_list = list(client['time_difference']
								for client_addr, client
									in client_data.items())
									


	sum_of_clock_difference = sum(time_difference_list, \
								datetime.timedelta(0, 0))


	average_clock_difference = sum_of_clock_difference \
										/ len(client_data)


	return average_clock_difference


def synchronizeAllClocks():


	while True:


		print("New synchronization cycle started.")
		print("Number of clients to be synchronized: " + \
									str(len(client_data)))


		if len(client_data) > 0:


			average_clock_difference = getAverageClockDiff()


			for client_addr, client in client_data.items():
				try:
					synchronized_time = \
						datetime.datetime.now() + \
									average_clock_difference


					client['connector'].send(str(
							synchronized_time).encode())


				except Exception as e:
					print("Something went wrong while " + \
						"sending synchronized time " + \
						"through " + str(client_addr))


		else :
			print("No client data." + \
						" Synchronization not applicable.")


		print("\n\n")


		time.sleep(5)
def initiateClockServer(port = 8080):


	master_server = socket.socket()
	master_server.setsockopt(socket.SOL_SOCKET,
								socket.SO_REUSEADDR, 1)


	print("Socket at master node created successfully\n")
	
	master_server.bind(('', port))
	master_server.listen(10)
	print("Clock server started...\n")
	print("Starting to make connections...\n")
	master_thread = threading.Thread(
						target = startConnecting,
						args = (master_server, ))
	master_thread.start()
	print("Starting synchronization parallelly...\n")
	sync_thread = threading.Thread(
						target = synchronizeAllClocks,
						args = ())
	sync_thread.start()


if __name__ == '__main__':
	initiateClockServer(port = 8080)

Output:

New synchronization cycle started.
Number of clients to be synchronized: 3
Client Data updated with: 127.0.0.1:57284
Client Data updated with: 127.0.0.1:57274
Client Data updated with: 127.0.0.1:57272

The following code is used to trigger slave nodes:

# Python3 program to trigger slave
from timeit import default_timer as timer
from dateutil import parser
import threading
import datetime
import socket
import time
def startSendingTime(slave_client):


	while True:
		slave_client.send(str(
					datetime.datetime.now()).encode())


		print("Recent time sent successfully",
										end = "\n\n")
		time.sleep(5)
def startReceivingTime(slave_client):


	while True:
		Synchronized_time = parser.parse(
						slave_client.recv(1024).decode())


		print("Synchronized time at the client is: " + \
									str(Synchronized_time),
									end = "\n\n")
def initiateSlaveClient(port = 8080):


	slave_client = socket.socket()		
	
	slave_client.connect(('127.0.0.1', port))
	print("Starting to receive time from server\n")
	send_time_thread = threading.Thread(
					target = startSendingTime,
					args = (slave_client, ))
	send_time_thread.start()


	print("Starting to receiving " + \
						"synchronized time from server\n")
	receive_time_thread = threading.Thread(
					target = startReceivingTime,
					args = (slave_client, ))
	receive_time_thread.start()


if __name__ == '__main__':
	initiateSlaveClient(port = 8080)

Output:

Recent time sent successfully
Synchronized time at the client is: 2018-11-23 18:49:31.166449

Note:

This algorithm was invented by Gussela and Jatti at the University Of California Of Berkley so; it is named as Berkley’s algorithm. It is preferred to use this algorithm in intranet like Christian’s algorithm.