This question appears in Mumbai University > Parallel And Distributed System subject

Marks: 10 M

Year: Dec 12

Distributed algorithms for clock synchronization

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 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.
• The global averaging algorithms differ mainly in the manner in which the fault-tolerant average of the estimated skews is calculated.

The commonly used algorithms are –

1.The simplest algorithm is to take the average of the estimated skews and use it as the correction for the local clock. To limit the impact of faulty clocks on the average value the estimated skew with respect to each node is compared against a threshold and skews greater than the threshold are set to zero before computing the average of the estimated skews.

2.In this algorithm each node limits the impact of faulty clocks by first discarding the m highest and m lowest estimated skews and then calculating the average of the remaining skews which is then used as the correction for the local clock. The value of m is usually decided based on the total number of clock nodes.

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.