Clocks and Time

In Distributed Systems, time is important for purposes including time stamping in transactions and synchronization in algorithms.

Clock Skew and Drift Rate

Each process has an internal clock. Clocks between processes on different computers differ.

• Skew: relative difference between two clock values
• Drift Rate: change in skew from a perfect reference clock per unit time (measured by the reference clock)
  • System Model#Synchronous System have bound on maximum drift rate

Synchronization

External Synchronization: Synchronize time with an authoritative clock, when accurate timestamps are required

• For a synchronization/accuracy bound $D>0$, and for a source $S$ of UTC time, $|S(t)-A(t)|<D$ for all real times $t$ in time interval $I$
• All clocks $C_i$ are accurate to within the bound $D$

Internal Synchronization: Synchronize time internally between all processes in a distributed system, when internally comparable timestamps are required

• For a synchronization/accuracy bound $D>0$, $|A(t)-B(t)|<D$ for all real times $t$ in time interval $I$
• $\text{skew}(A,B)<D$ during the time interval $I$
• All clocks agree within the bound D

If all clocks in a system are externally synchronized, they are also internally synchronized.
Clocks that are internally synchronized are not necessarily externally synchronized (since they may drift collectively from an external source of time).

If all clocks in a system are externally synchronized within a bound of $D$, the bound on their skew relative to one another is $2D$.

Synchronization in Synchronous Systems

What time $T_c$ should client adjust its local clock to after receiving $m_s$ ?

Let $\text{max}$ and $\text{min}$ be maximum and minimum network delay.

• If $T_c=T_s$: $\text{skew(client, server)}\le$ $\text{max}$
• If $T_c=(T_s+\text{max})$: $\text{skew(client, server)}\le (\text{max}-\text{min})$
• If $T_c=(T_s+\text{min})$: $\text{skew(client, server)}\le (\text{max}-\text{min})$
• If $T_c=(T_s+(\text{min + max})/2)$: $\text{skew(client, server)}\le (\text{max}-\text{min})/2$

Synchronization in Asynchronous Systems

What time $T_c$ should client adjust its local clock to after receiving $m_s$ ?

Cristian Algorithm

The use of a time server, connected to a device that receives signals from a source of UTC, to synchronize computers externally. Upon request, the server process $S$ supplies the time according to its clock.

• Client measures the round trip time $T_{\text{round}}$
• $T_c=T_s+(T_{\text{round}}/2)$
  • This is the client assuming its one-way delay from server is $\mathrm{\Delta }=T_{\text{round}}/2$
• $\text{skew}\le (T_{\text{round}}/2)-\text{min}\le (T_{\text{round}}/2)$
• 

Improve accuracy by sending multiple spaced requests and using response with smallest $T_{\text{round}}$.

Handling Failure:

• Use multiple synchronized time servers in case of failure.

Handling Faulty Processes:

• Cannot handle faulty time servers.

Berkeley Algorithm

Only supports Internal #Synchronization. An coordinator computer is chosen as leader

1. Server periodically polls clients "what time do you think it is?"
2. Each client responds with its local time
3. Server uses #Cristian Algorithm to estimate local time at each client
4. Average all local times (including its own) -- use as updated time
5. Send the offset (amount by which each clock needs adjustment)

$\to$

Handling Faulty Processes:

• Only uses timestamps within some thresholds of each other

Handling Server Failure:

• Detect the failure and elect a new leader

Network Time Protocol

NTP defines an architecture for time service over the Internet for synchronizing to UTC, it has:

• Hierarchical structure for scalability
• Multiple lower strata servers for robustness
• Authentication mechanisms for security
• Statistical techniques for better accuracy

The structure:

1. Primary servers are connected directly to a time source such as a radio clock receiving UTC
2. Secondary servers are synchronized with primary servers, third with second, etc.
3. Each level is a strata
4. The leaf servers execute in users' workstations

Ways that NTP servers synchronize with one another:

1. Servers multicast timestamps within a LAN, clients adjust time assuming a small delay
   (Low accuracy)
2. Procedure Call (#Cristian Algorithm)
   (Higher accuracy)
3. Symmetric Mode used to synchronize lower strata servers
   (Highest accuracy)

Symmetric Mode

Takes into consideration of non-consecutive messages.

Suppose:

• $t$ and $t^{\prime }$ are actual transmission times for $m$ and $m^{\prime }$ (unknown)
• $o$ is the true offset of clock B relative to clock A (unknown)

We want to estimate:

• $o_i$ the offset between the two clocks
• $d_i$ the accuracy of $o_i$

We have:

• $T_{Br}=T_{As}+t+o$
• $T_{Ar}=T_{Bs}+t^{\prime }-o$
• $o=((T_{Br}-T_{As})-(T_{Ar}-T_{Bs})+(t^{\prime }-t))/2$

Assuming symmetric $t$ and $t^{\prime }$:

• $o_i=((T_{Br}-T_{As})-(T_{Ar}-T_{Bs}))/2$
• $o=o_i+(t^{\prime }-t)/2$
• $d_i=t+t^{\prime }=(T_{Br}-T_{As})+(T_{Ar}-T_{Bs})$
• $o_i-d_i/2\le o\le o_i+d_i/2$