Time and Global States in Distributed Systems

Simple Synchronization in Synchronous Systems

  • A process sends its internal clock to a UTC Server
  • t + Ttrans not valid because of network variations
  • instead uses t + (max +min) / 2, being transmission max/min bounds

Cristian’s Algorithm

  • Method achieves synchronization if round-trip is sufficiently short compared with the accuracy
  • P1 ask for time to P2
  • P1 receives t from P2
  • P1 sets t + RTT/2

Berkley Algorithm

  • Internal Synchronization for collection of computers
  • Server polls a subset of computers which clocks difference is not larger than a given threshold.
  • Average the result and send the difference to each one, to correct drift tendencies

The Network Time Protocol

  • Accurately Synchronization to UTC: NTP employs statistical techniques for filtering timing data and discriminates the quality of timing data
  • Reliable service: Redundant servers and redundant paths between servers.
  • Frequent synchronization to offset rates of drift: the system is designed to scale
  • Protection against interferences: Authentication techniques
  • Primary Servers connected to a time source
  • Secondary Servers synchronized with primary servers
  • Servers connected in a “synchronization subnets” organized in stratums. Primary = stratum 1, and so on till leafs which are servers in users’ workstations.
  • Error are introduces at each level so the ones with higher numbers are less accurate
  • Servers synchronize: Multicast mode (high-speed LAN), Procedure-call mode (Similar to Cristian’s Algorithm) and Symmetric mode (between higher stratums, exchange message bearing time)
  • UDP is used as message delivery mechanism
  • NTP employs a  phase lock loop model, modifying the clock’s frequency in accordance with its drift rate.

Logical Time and Logical Clocks