Skip to main content

Physical clock synchronization algorithm

Short answer

Physical clocks show real time and drift; logical clocks are counters for event ordering. The Berkeley algorithm synchronizes physical clocks: a master polls slaves for their times, averages them (discarding outliers), and sends each the adjustment amount. It avoids backward jumps but has a single point of failure; solution: elect a new master or use NTP with redundant servers.

Define logical and physical clocks. How can you synchronize the physical clock in a distributed network, explain with suitable algorithm. Also make a comment on the algorithm if any and suggest the solution.

Logical and physical clocks

  • Physical clock: a hardware clock showing real time. It drifts and must be synchronised to other clocks or to UTC.
  • Logical clock: a software counter that orders events by the happened-before relation (Lamport, vector clocks); has no relation to real time.

Synchronising physical clocks: Berkeley algorithm

Used within a network with no machine having a UTC source (internal synchronisation).

  1. A master (time daemon) is chosen.
  2. The master periodically polls all slaves for their current time.
  3. Each slave sends its time; the master corrects each value for the round-trip delay.
  4. The master averages all the times (including its own, ignoring values that are far off).
  5. It sends each machine the amount by which to adjust its clock (plus or minus), not the absolute time, so message delay does not matter. A clock that is ahead is slowed down, not set back.

Example: master 3:00, A 2:50, B 3:25; average = 3:05; adjustments: master +5 min, A +15, B −20.

(Another approach is Cristian's algorithm: ask a time server with a UTC receiver for the time and set T_new = T_S + RTT/2.)

Comment and solution

  • The master is a single point of failure, and its polling is a bottleneck in large systems; a faulty master can corrupt all clocks.
  • The result is the average of the nodes, not real UTC time, and accuracy is limited by variable delay.
  • Solution: elect a new master by an election algorithm when it fails (bully/ring); discard outliers; or use NTP, with a hierarchy of redundant time servers connected to UTC (strata), which scales and tolerates failures.

✓ Answer checked by Claude Opus 5.5 (high effort)

Related questions

All Distributed System chapter 5 questions →