written 8.6 years ago by | modified 2.7 years ago by |
This question appears in Mumbai University > Parallel And Distributed System subject
Marks: 10 M
Year: Dec 12
written 8.6 years ago by | modified 2.7 years ago by |
This question appears in Mumbai University > Parallel And Distributed System subject
Marks: 10 M
Year: Dec 12
written 8.6 years ago by |
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.
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