Berkeley algorithm

The Berkeley Algorithm is an method of clock synchronisation in distributed computing which assumes no machine has an accurate time source. It was developed by Gusella and Zatti at the University of California, Berkeley in 1989

The algorithm

Unlike Cristian's algorithm the server process in Berkeley algorithm, called the master periodically polls other slave process. Generally speaking the algorithm is as follows:

1. A master is chosen via an election process such as Chang & Roberts.
2. The master polls the slaves who reply with their time in a similar way to Cristian's algorithm.
3. The master observes the Round Trip Time (RTT) of the messages and estimates the time of each slave and its own.
4. The master then averages the clock times, ignoring any values it receives far outside the values of the others.
5. Instead of sending the updated current time back to the other process. The master then sends out the amount (positive or negative) that each slave must adjust its clock. This avoids further uncertainty due to RTT at the slave processes.

With this method the average cancels out individual clock's tendencies to drift. Gusella and Zatti released results involving 15 computers whose clocks were synchronised to within about 20-25 milliseconds using their protocol.