Berkeley algorithm

Berkeley algorithm

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 [Citation
authors=Gusella and Zatti
title= The accuracy of the clock synchronization achieved by TEMPO in Berkeley UNIX 4.3BSD
journal=Software Engineering, IEEE Transactions on
volume=15
issue=7
year=1989
pages=847-853
url=http://ieeexplore.ieee.org/xpl/freeabs_all.jsp?arnumber=29484
publisher=IEEE
] and like Cristian's algorithm is intended for use within intranets.

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:

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

Computer systems normally avoid rewinding their clock when they receive a negative clock alteration from the master. 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 master.

References


Wikimedia Foundation. 2010.

Игры ⚽ Нужна курсовая?

Look at other dictionaries:

  • Cristian's algorithm — (introduced by Flaviu Cristian in 1989)[1] is a method for clock synchronisation which can be used in many fields of distributive computer science but is primarily used in low latency intranets. Cristian observed that this simple algorithm is… …   Wikipedia

  • Auction algorithm — The term auction algorithm applies to several variations of a combinatorial optimization algorithm which solves assignment problems, including forward/reverse auction algorithms. An auction algorithm has been used in a business setting to… …   Wikipedia

  • Shor's algorithm — Shor s algorithm, first introduced by mathematician Peter Shor, is a quantum algorithm for integer factorization. On a quantum computer, to factor an integer N, Shor s algorithm takes polynomial time in log{N}, specifically O((log{N})^3),… …   Wikipedia

  • K-means algorithm — The k means algorithm is an algorithm to cluster n objects based on attributes into k partitions, k < n. It is similar to the expectation maximization algorithm for mixtures of Gaussians in that they both attempt to find the centers of natural… …   Wikipedia

  • Cannon's algorithm — In computer science, Cannon s algorithm is a distributed algorithm for matrix multiplication for two dimensional meshes first described in 1969 [http://dbpubs.stanford.edu:8090/pub/1994 25 Gupta, H.; Sadayappan, P.: Communication Efficient Matrix …   Wikipedia

  • Genetic algorithm — A genetic algorithm (GA) is a search heuristic that mimics the process of natural evolution. This heuristic is routinely used to generate useful solutions to optimization and search problems. Genetic algorithms belong to the larger class of… …   Wikipedia

  • Randomized algorithm — Part of a series on Probabilistic data structures Bloom filter · Skip list …   Wikipedia

  • Grover's algorithm — is a quantum algorithm for searching an unsorted database with N entries in O(N1/2) time and using O( log N) storage space (see big O notation). It was invented by Lov Grover in 1996.Classically, searching an unsorted database requires a linear… …   Wikipedia

  • Anytime algorithm — Introduction Most algorithms run to completion: they provide a single answer after performing some fixed amount of computation. In some cases, however, the user may wish to terminate the algorithm prior to completion. The amount of the… …   Wikipedia

  • Goertzel algorithm — The Goertzel algorithm is a digital signal processing (DSP) technique for identifying frequency components of a signal, published by Dr. Gerald Goertzel in 1958. While the general Fast Fourier transform (FFT) algorithm computes evenly across the… …   Wikipedia

Share the article and excerpts

Direct link
Do a right-click on the link above
and select “Copy Link”