Time and Global State

1. Clock Synchronization

1.1 Clocks

• hardware clock

• software clock = scaled factor * hardware clock + offset

• skew
• diff between the reading of any 2 clocks

• drift
• diff in the rate at which 2 clocks count time

• clock drift rate
• diff in rate between a perfect reference clock and a physical clock

• A synchronous distributed system is one in which the following bounds are defined:
• Time to execute step of a process has known lower and upper bounds
• Each message transmitted is received within a known bounded time
• Each process has a local clock whose drift rate has a known bound

1.2 Cristian's Method

• Cristian's algorithm works between a process P, and a time server S connected to a time reference source. Put simply:
• P requests the time from S
• After receiving the request from P, S prepares a response and appends the time T from its own clock.
• P then sets its time to be T + RTT/2

• This method assumes that the RTT is split equally between request and response, which may not always be the case but is a reasonable assumption on a LAN connection.

• Further accuracy can be gained by making multiple requests to S and using the response with the shortest RTT.

• We can estimate the accuracy of the system as follows. Let min be the minimum time to transmit a message one-way. The earliest point at which S could have placed the time T, was min after P sent its request. Therefore, the time at S, when the message by P is received, is in the range (T + min) to (T + RTT - min). The width of this range is (RTT - 2*min). This gives an accuracy of (RTT/2 - min).

1.3 Berkeley Algorithm

• Master + Slaves

• 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.

• 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.