Measuring Time, Clocks, and Clock Synchronization

1. Time Measurement Fundamentals

Basic Time Measurement

$$T_x=\frac{N}{f_0}$$

Explanation:

• Measures time by counting oscillations
• $T_x$ is measured time interval
• $N$ counts oscillations
• $f_0$ is reference clock frequency

  Example: With 1MHz clock, counting 1000 ticks gives 1ms

Measurement Error

$$\frac{\Delta T_x}{T_x}\approx \frac{1}{N}+\frac{\Delta f_0}{f_0}$$

Sources:

1. Quantization error ($\frac{1}{N}$)
2. Frequency instability ($\frac{\Delta f_0}{f_0}$)

2. Clock Synchronization

Clock Drift

$${\text{Drift}}_k(t_i,t_{i+1})=\frac{C_k(t_{i+1})-C_k(t_i)}{C(t_{i+1})-C(t_i)}$$

Key Points:

• Measures clock speed vs reference
• $C_k(t)$ is local clock time
• $C(t)$ is reference time

  Example: Drift=1.001 means 0.1% fast

Drift Rate

$${\delta }_k={\text{Drift}}_k-1$$

Usage:

• Measures deviation from perfect timing
• Positive: running fast
• Negative: running slow

Clock Offset

$${\text{Offset}}_{j,k}(t)=C_j(t)-C_k(t)$$

Purpose:

• Measures time difference between clocks
• Used for synchronization algorithms

Precision

$$\Pi (t)=\max \left\{{\text{Offset}}_{j,k}(t)|1\le j,k\le n\right\}$$

Application:

• Maximum offset between any two clocks
• Key metric for system synchronization

3. Synchronization Algorithms

Cristian’s Algorithm

$$\text{Correction}=\frac{T_1-T_0-I}{2}$$

Process:

1. Client requests time ($T_0$)
2. Server responds ($T_1$)
3. $I$ is processing delay
4. Correction adjusts local time

Master-Slave

$${\Delta }_j=\frac{d_1-d_2}{2}$$

Implementation:

• $d_1$: forward delay
• $d_2$: return delay
• Assumes symmetric delays

4. Error Handling

Interval Consistency

$$\alpha =\max (L_j(t)),\beta =\min (R_j(t))$$ $$\alpha <\beta$$

Purpose:

• Ensures time intervals overlap
• $L_j(t)$: lower bounds
• $R_j(t)$: upper bounds

Byzantine Fault Tolerance

$$\text{Average}=\frac{{\sum }_{i=1}^{N-2k}\text{Remaining Differences}}{N-2k}$$

Process:

1. Remove k highest/lowest values
2. Average remaining values
3. Tolerates k faulty clocks

5. Physical Limitations

Clock Granularity

$$g=\frac{1}{f}$$

Impact:

• Minimum time measurement unit
• Affects synchronization accuracy

Synchronization Error Bounds

$$d_{\text{observed}}-2g<d_{\text{true}}<d_{\text{observed}}+2g$$

Application:

• Bounds actual delay
• Accounts for granularity

Jitter Analysis

$$e=d_{\max }-d_{\min }$$ $$\Pi =e\left(1-\frac{1}{N}\right)$$

Significance:

• Measures timing variation
• Affects system precision
• $N$ is number of nodes