Lasitha Silva’s Web’log

Posts Tagged ‘Berkeley

For all @ FIT in aid of ASE subject tomorrow. Hope this helps..

Christian’s Algorithm

A clock synchronization algorithm used to synchronize the time on a machine with a remote time server. This is a very straightforward algorithm, and is quite easy to understand.

The procedure:

  1. A process p requests the time in a message mr and receives the time value t in a message mt.
  2. t is inserted in mt at the last possible point before transmission from the server S.
  3. Tround = Time(send mr) + Time ( receive mt) = (1-10)*10-3 seconds on a LAN.
  4. min = minimum queueing time for S.

The earliest point at which S could have placed the time mt was min after p dispatched mr. The time by S’s clock when the message is received by P is in the range t + min < p < t + Tround - min. The total width of this range is Tround - 2*min. This gives an accuracy of (Tround / 2 – min). If all of that made absolutely no sense to you, here’s a much simpler (but far less rigorous) explanation. Basically, the client sends a request for the current time to the time server. When it receives the response, it finds the transmission delay (time between the request being sent and the response being received), divides that in half, and adds that to the time received back from the server. The idea is to eliminate the inaccuracy caused by network delays. This assumes that the link is equally fast both ways, which may not always be the case. But as with any algorithm, you have to make tradeoffs.

Berkeley Algorithm

A distributed clock synchronization algorithm, developed by Drs. Gusella and Zatti at the University of California, Berkeley in 1989.

Here’s what you do:
Choose a coordinator computer to act as the master. The master periodically polls the slaves whose clocks are to be synchronized to the master. The slaves send their clock values to the master.

The master observes the transmission delays and estimates their local clock times. Once this is done, it takes a fault-tolerant average of all the times including its own, and ignores those that are far outside of the range of the rest.

The master then sends each slave the amount (positive or negative) that it should adjust its clock. This is very ingenious, because it means that it doesn’t have to send absolute times (which will be messed up by network delays

Source: http://everything2.com/