The Berkeley algorithm is a 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.[1] Like Cristian's algorithm, it is intended for use within intranets.

The algorithm

edit

Unlike Cristian's algorithm, the server process in the Berkeley algorithm, called the leader, periodically polls other follower processes. Generally speaking, the algorithm is:

  1. A leader is chosen via an election process such as Chang and Roberts algorithm.
  2. The leader polls the followers who reply with their time in a similar way to Cristian's algorithm.
  3. The leader observes the round-trip time (RTT) of the messages and estimates the time of each follower and its own.
  4. The leader 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 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. 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

edit
  1. ^ Gusella, R.; Zatti, S. (1989), "The accuracy of the clock synchronization achieved by TEMPO in Berkeley UNIX 4.3BSD", IEEE Transactions on Software Engineering, 15 (7), IEEE: 847–853, doi:10.1109/32.29484

📚 Artikel Terkait di Wikipedia

Clock synchronization

trivial; the server will dictate the system time. Cristian's algorithm and the Berkeley algorithm are potential solutions to the clock synchronization problem

Cristian's algorithm

synchronisation, which optimises the method by itself. Allan variance Berkeley algorithm Clock synchronization Daytime Protocol, older time synchronization

Algorithm

In mathematics and computer science, an algorithm (/ˈælɡərɪðəm/ ) is a finite sequence of mathematically rigorous instructions, typically used to solve

List of algorithms

An algorithm is a fundamental set of rules or defined procedures that are typically designed and used to be a simpler way to solve a specific problem

Ewin Tang

University of California, Berkeley. She was named as one of 2019 Science Forbes 30 Under 30 for her work developing classical algorithms which matched the performance

Richard M. Karp

theorist at the University of California, Berkeley. He is most notable for his research in the theory of algorithms, for which he received the 1985 ACM Turing

Shor's algorithm

Shor's algorithm is a quantum algorithm for finding the prime factors of an integer. It was developed in 1994 by the American mathematician Peter Shor

University of California, Berkeley

The University of California, Berkeley (UC Berkeley, Berkeley, Cal, or California) is a public land-grant research university in the Southside and Northside