Clock Synchronization Algorithm Assignment Help

• Multiple machines using physical clocks. How can we keep them more or even less synchronized.
• Internal versus External synchronization
• Perfect synchronization difficult due to communication delays
• Even synchronization inside a bound cannot be assured along with guarantee due to unpredictability associated with communication delays.

How clocks work

• Computer clocks tend to be crystals which oscillate in a particular rate of frequency
• Every H oscillations, the actual timer chip interrupts once. Number associated with interrupts per second is usually 18.2, 50, 60, 100; could be greater, settable in some instances
• The interrupt handler increments the counter which retains track associated with number of ticks from a reference previously
• Knowing number associated with ticks for each second, we areable to determine year, month, day, time of day and so on.

Clock Drift

• Unfortunately, period associated with crystal oscillation differs somewhat
• If this oscillates quicker, much more ticks per real second, therefore clock runs faster; comparable with regard to slower clocks
• For machine p, when correct reference time is t, let machine clock show time as C = Cp(t)
• Ideally, Cp(t) = t for all p, t
• In practice, 1 – ρ ≤ dC/dt ≤ 1 + ρ
• ρ = max. clock drift rate, usually around 10-5 for cheap oscillators
• Drift => Skew between clocks (difference in clock values of two machines)

Resynchronization

• Periodic resynchronization required to offset skew
• If two clocks tend to be drifting within reverse directions, maximum skew following period capital t is actually 2 ρ t
• If application requires which clock skew < δ, after that resynchronization period r < δ /(2 ρ)
• Usually ρ and δ are known.

Important topics in Clock Synchronization

• Berkeley algorithm
• Cristian's algorithm
• Marzullo's algorithm