Distributed System
A Distributed System is a collection of independent but interconnected computers that appear to the users of the system as a single coherent system. These computers are connected by a computer network and are equipped with distributed system software.
Distributed system software enables these independent computers to coordinate their activities and share computing resources to perform operations seamlessly. This software ensures that the distributed system functions as a unified entity, providing services and resources efficiently and reliably.
What is Clock synchronization?
Clock synchronization is the process of aligning the clocks of all participating nodes in a distributed system. Using clock synchronization techniques, the time across all nodes in a distributed system is made to show the same, or nearly the same, time.
What is the importance of Clock Synchronization?
Let me explain with an example. Suppose you build a course enrollment system with servers located in different locations. Here's an example to illustrate the importance of clock synchronization.
1. Person P1 submits an enrolment request at 9:10, which goes to Server A.
2. Person P2 submits an enrolment request at 9:11, which goes to Server B.
3. Person P3 submits an enrolment request at 9:09, which goes to Server C.
Ideally, Person P3 should get enrolled first, followed by P1, and then P2. However, due to network delays, the requests are received by the Master Server in the order P2, P1, and P3. The Master Server processes the requests in the order they are received, allocating seats to P2, P1, and then P3, which is incorrect.
This problem can be resolved by synchronizing the clocks of all servers. By attaching the synchronized timestamps to each request when sending them to the Master Server, the server can correctly order the requests based on their timestamps, ensuring that P3 is enrolled first, followed by P1, and then P2.
How to synchronize clocks using Berkeley’s Algorithm?
Let me explain Berkeley’s algorithm with 5 nodes that are part of a distributed computing network and each with its own clock time:
· A: 10:10
· B: 10:30
· C: 9:45
· D: 9:30
· E: 10:25
1. Choose the master server or time synchronizer
One of the nodes in the distributed system are chosen as Master server or time synchronizer, and it is responsible for the coordination process.
2. Master server (A) Collects the time stamps of all the other participating servers B, C, D and E.
3. After receiving the clock times, the Master server computes the difference between its time and those of the other nodes:
· The time difference with B is calculated as 10:30 - 10:10, resulting in a positive 20 minutes.
· The time difference with C is determined as 9:45 - 10:10, resulting in a negative 25 minutes.
· The time difference with D is calculated as 9:30 - 10:10, resulting in a negative 40 minutes.
· The time difference with E is determined as 10:25 - 10:10, resulting in a positive 15 minutes.
4. Calculate the average difference between the node clocks to master server clock
Average Offset = (20 - 25 - 40 + 15 + 0) / 5 = -30 / 5 = -6 minutes
So, we need to adjust 6 minutes.
5. This adjustment of -6 minutes is added to the master server time. And the master time become 10:10 = 0:6 = 10:04 minutes.
Not the master server broad cast it’s time to all the slave nodes in the distributed system.
Upon receiving the time adjustment message from Master server, all the salve nodes adjust their times to same 10:04 (10 hours 4 minutes)
Now all the servers in the distributed systems point to the same time. This is continuous process, master process periodically checks the timestamps and update accordingly.
Find the below working application for the same.
Time.java
package com.sample.app.model;
public class Time {
private final int hours;
private final int minutes;
private final int seconds;
public Time(int totalSeconds) {
this.hours = totalSeconds / 3600; // 3600 seconds in an hour
int remainingSeconds = totalSeconds % 3600;
this.minutes = remainingSeconds / 60; // 60 seconds in a minute
this.seconds = remainingSeconds % 60;
}
public Time(int hours, int minutes, int seconds) {
this.hours = hours;
this.minutes = minutes;
this.seconds = seconds;
}
public int getHours() {
return hours;
}
public int getMinutes() {
return minutes;
}
public int getSeconds() {
return seconds;
}
public int inSeconds() {
return hours * 3600 + minutes * 60 + seconds;
}
@Override
public String toString() {
return "Time [hours=" + hours + ", minutes=" + minutes + ", seconds=" + seconds + "]";
}
}
Node.java
package com.sample.app.model;
public class Node {
private final String name;
private final Time clock;
public Node(String name, Time clock) {
this.name = name;
this.clock = clock;
}
public String getName() {
return name;
}
public Time getClock() {
return clock;
}
}
DistributedSystem.java
package com.sample.app.model;
import java.util.List;
public class DistributedSystem {
private final Node masterNode;
private final List<Node> slaveNodes;
public DistributedSystem(Node masterNode, List<Node> slaveNodes) {
this.masterNode = masterNode;
this.slaveNodes = slaveNodes;
}
public Node getMasterNode() {
return masterNode;
}
public List<Node> getSlaveNodes() {
return slaveNodes;
}
public Time berkleysAdjustedTime() {
int masterNodeTimeInSeconds = masterNode.getClock().inSeconds();
int timeDiff = 0;
for (Node slaveNode : slaveNodes) {
timeDiff = timeDiff + (slaveNode.getClock().inSeconds() - masterNodeTimeInSeconds);
}
int avgTime = timeDiff / (slaveNodes.size() + 1);
//System.out.println("avgTime : " + avgTime);
int finalTimeInSeconds = masterNodeTimeInSeconds + avgTime;
return new Time(finalTimeInSeconds);
}
}
BerkeleyAlgorithmDemo.java
package com.sample.app;
import java.util.Arrays;
import com.sample.app.model.DistributedSystem;
import com.sample.app.model.Node;
import com.sample.app.model.Time;
public class BerkeleyAlgorithmDemo {
public static void main(String args[]) {
Node masterNode = new Node("A", new Time(10, 10, 0));
Node slaveNode1 = new Node("B", new Time(10, 30, 0));
Node slaveNode2 = new Node("C", new Time(9, 45, 0));
Node slaveNode3 = new Node("D", new Time(9, 30, 0));
Node slaveNode4 = new Node("E", new Time(10, 25, 0));
DistributedSystem ds = new DistributedSystem(masterNode,
Arrays.asList(slaveNode1, slaveNode2, slaveNode3, slaveNode4));
Time adjustedTime = ds.berkleysAdjustedTime();
System.out.println("adjustedTime : " + adjustedTime);
}
}
Output
adjustedTime : Time [hours=10, minutes=4, seconds=0]
Limitations of Berkeley’s Algorithm
1. Relying on One Leader: Berkeley's method needs one main node to organize syncing. If this main node stops working or can't be reached, syncing might not work.
2. Risk of Malicious Nodes: The method doesn't check if nodes are trustworthy or if they report the right time. Malicious nodes could lie about the time, making syncing wrong.
3. Trouble with Congested Networks: Berkeley's way depends on nodes talking to each other to set their clocks. If the network is busy or unreliable, messages might be late or lost, making syncing wrong.
4. Can’t handle Many Nodes: As more nodes join, syncing gets harder because there's more work to do. This can make it tough for the method to work well, especially in really big systems.
5. Can't Adapt to Dynamically: Berkeley's method works best when the network stays the same. If nodes join or leave a lot, or if connections change, syncing might not be accurate.
System Design Questions
No comments:
Post a Comment