Berkeley algorithm: Difference between revisions

Content deleted Content added

Inline

Revision as of 21:34, 27 January 2020

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

Unlike Cristian's algorithm, 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 leader polls the followers who reply with their time in a similar way to Cristian's algorithm.
The leader observes the round-trip time (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. 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 (known as "clock slew"), 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

^ 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

[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

[1]

@@ Line 11: / Line 11: @@
 == The algorithm ==
-Unlike [[Cristian's algorithm]], the server process in the Berkeley algorithm, called the ''master'', periodically polls other ''slave'' processes. Generally speaking, the algorithm is:
+Unlike [[Cristian's algorithm]], the server process in the Berkeley algorithm, called the ''leader'', periodically polls other ''follower'' processes. Generally speaking, the algorithm is:
-# A ''master'' is chosen via an [[leader election|election process]] such as [[Chang and Roberts algorithm]].
+# A ''leader'' is chosen via an [[leader election|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 ''leader'' polls the ''followers'' 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 ''leader'' observes the [[round-trip time]] (RTT) of the messages and estimates the time of each ''follower'' and its own.
-# The ''master'' then averages the clock times, ignoring any values it receives far outside the values of the others.
+# 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 ''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.
+# 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 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 (software)|make]]. A simple solution to this problem is to halt the clock for the duration specified by the master, but this simplistic solution can also cause problems, although they are less severe.  For minor corrections, most systems slow the clock (known as "clock slew"), applying the correction over a longer period of time.
+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 (software)|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 (known as "clock slew"), 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.