Similar questions

What is physical clock synchronization? Explain any one algorithm in detail.

Marks: 10 M

Year: May 12, Dec 13

Physical clock synchronization algorithm

Every computer contains a clock which is an electronic device that counts the oscillations in a crystal at a particular frequency. Synchronization of these physical clocks to some known high degree of accuracy is needed. This helps to measure the time relative to each local clock to determine order between events.

Physical clock synchronization algorithms can be classified as centralized and distributed.

1.Centralized clock synchronization algorithms

These have one node with a real-time receiver and are called time server node. The clock time of this node is regarded as correct and used as reference time.

The goal of this algorithm is to keep the clocks of all other nodes synchronized with time server node.

i. Cristian’s Algorithm

• In this method each node periodically sends a message to the server. When the time server receives the message it responds with a message T, where T is the current time of server node.
• Assume the clock time of client be To when it sends the message and T1 when it receives the message from server. To and T1 are measured using same clock so best estimate of time for propagation is (T1-To)/2.
• When the reply is received at clients node, its clock is readjusted to T+(T1-T0)/2. There can be unpredictable variation in the message propagation time between the nodes hence (T1-T0)/2 is not good to be added to T for calculating current time.
• For this several measurements of T1-To are made and if these measurements exceed some threshold value then they are unreliable and discarded. The average of the remaining measurements is calculated and the minimum value is considered accurate and half of the calculated value is added to T.
• Advantage-It assumes that no additional information is available.
• Disadvantage- It restricts the number of measurements for estimating the value.

ii.The Berkley Algorithm

• This is an active time server approach where the time server periodically broadcasts its clock time and the other nodes receive the message to correct their own clocks.
• In this algorithm the time server periodically sends a message to all the computers in the group of computers. When this message is received each computer sends back its own clock value to the time server. The time server has a prior knowledge of the approximate time required for propagation of a message which is used to readjust the clock values. It then takes a fault tolerant average of clock values of all the computers. The calculated average is the current time to which all clocks should be readjusted.
• The time server readjusts its own clock to this value and instead of sending the current time to other computers it sends the amount of time each computer needs for readjustment. This can be positive or negative value and is calculated based on the knowledge the time server has about the propagation of message.

2.Distributed algorithms

Distributed algorithms overcome the problems of centralized by internally synchronizing for better accuracy. One of the two approaches can be used:

i.Global Averaging Distributed Algorithms

• In this approach the clock process at each node broadcasts its local clock time in the form of a “resync” message at the beginning of every fixed-length resynchronization interval. This is done when its local time equals To+iR for some integer i, where To is a fixed time agreed by all nodes and R is a system parameter that depends on total nodes in a system.
• After broadcasting the clock value, the clock process of a node waits for time T which is determined by the algorithm.
• During this waiting the clock process collects the resync messages and the clock process records the time when the message is received which estimates the skew after the waiting is done. It then computes a fault-tolerant average of the estimated skew and uses it to correct the clocks.

ii.Localized Averaging Distributes Algorithms

• The global averaging algorithms do not scale as they need a network to support broadcast facility and a lot of message traffic is generated.
• Localized averaging algorithms overcome these drawbacks as the nodes in distributed systems are logically arranged in a pattern or ring.
• Each node exchanges its clock time with its neighbors and then sets its clock time to the average of its own clock time and of its neighbors.