Berkeley algorithm

The Berkeley algorithm is a method of clock synchronisation for distributed computing that assumes no machine on the network has an accurate time source. It was developed by Gusella and Zatti at the University of California, Berkeley in 1989 and, like Cristian's algorithm, is meant for use inside an intranet. A leader is chosen by an election process, then polls the follower processes for their clock readings. The leader measures the round trip time of each exchange, estimates every follower's time and its own, and averages the readings while ignoring values far outside those of the others. Rather than sending back a new time, the leader sends each follower the positive or negative amount by which to adjust its clock, which avoids adding the follower's own message delay to the error. The averaging cancels individual clock drift, and the authors reported fifteen computers synchronised to within roughly 20 to 25 milliseconds. Systems usually avoid rewinding a clock, so a negative correction is applied by slowing the clock over a longer period.