The Berkeley algorithm is a method of

clock synchronisation Clock synchronization is a topic in computer science and engineering that aims to coordinate otherwise independent clocks. Even when initially set accurately, real clocks will differ after some amount of time due to clock drift, caused by clocks ...

distributed computing A distributed system is a system whose components are located on different computer network, networked computers, which communicate and coordinate their actions by message passing, passing messages to one another from any system. Distributed com ...

which assumes no machine has an accurate time source. It was developed by Gusella and Zatti at the University of California, Berkeley in 1989. Like

Cristian's algorithm Cristian's algorithm (introduced by Flaviu Cristian in 1989) is a method for clock synchronization which can be used in many fields of distributive computer science but is primarily used in low-latency intranets. Cristian observed that this simple ...

, it is intended for use within

intranets An intranet is a computer network for sharing information, easier communication, collaboration tools, operational systems, and other computing services within an organization, usually to the exclusion of access by outsiders. The term is used in c ...

The algorithm

Unlike

, the server process in the Berkeley algorithm, called the ''leader'', periodically polls other ''follower'' processes. Generally speaking, the algorithm is: # A ''leader'' is chosen via an election process such as

Chang and Roberts algorithm The Chang and Roberts algorithm is a ring-based coordinator election algorithm, employed in distributed computing. The algorithm The algorithm assumes that each process has a Unique Identification (UID) and that the processes can arrange the ...

. # The ''leader'' polls the ''followers'' who reply with their time in a similar way to

. # The ''leader'' observes the

round-trip time In telecommunications, round-trip delay (RTD) or round-trip time (RTT) is the amount of time it takes for a signal to be sent ''plus'' the amount of time it takes for acknowledgement of that signal having been received. This time delay includes p ...

(RTT) of the messages and estimates the time of each ''follower'' and its own. # The ''leader'' then averages the clock times, ignoring any values it receives far outside the values of the others. # Instead of sending the updated current time back to the other process, the ''leader'' then sends out the amount (positive or negative) that each ''follower'' must adjust its clock. This avoids further uncertainty due to RTT at the ''follower'' 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. Computer systems normally avoid rewinding their clock when they receive a negative clock alteration from the leader. Doing so would break the property of monotonic time, which is a fundamental assumption in certain algorithms in the system itself or in programs such as

make Make or MAKE may refer to: *Make (magazine), a tech DIY periodical *Make (software), a software build tool *Make, Botswana, in the Kalahari Desert *Make Architects Make Architects is an international architecture practice headquartered in London ...

. A simple solution to this problem is to halt the clock for the duration specified by the leader, but this simplistic solution can also cause problems, although they are less severe. For minor corrections, most systems slow the clock, applying the correction over a longer period of time. Often, any client whose clock differs by a value outside of a given tolerance is disregarded when averaging the results. This prevents the overall system time from being drastically skewed due to one erroneous clock.

References

{{reflist Distributed algorithms