Distributed Systems
Clock Synchronization:
Physical Clocks
Prepared By: Kassahun T.
What’s it for?
Temporal ordering of events produced
by concurrent processes
Synchronization between senders
and receivers of messages
Coordination of joint activity
Serialization of concurrent access for
shared objects
Physical
clocks
Logical vs. physical clocks
Logical clock keeps track of event ordering
– among related (causal) events
Physical clocks keep time of day
– Consistent across systems
Physical clocks in computers
Real-time Clock: CMOS clock (counter) circuit
driven by a quartz oscillator
– battery backup to continue measuring time when
power is off
OS generally programs a timer circuit to
generate an interrupt periodically
– e.g., 60, 100, 250, 1000 interrupts per second
(Linux 2.6+ adjustable up to 1000 Hz)
– Programmable Interval Timer (PIT) – Intel 8253, 8254
– Interrupt service procedure adds 1 to a counter in memory
Problem
Getting two systems to agree on time
– Two clocks hardly ever agree
– Quartz oscillators oscillate at slightly different
frequencies
Clocks tick at different rates
– Create ever-widening gap in perceived time
– Clock Drift
Difference between two clocks at one point in time
– Clock Skew
8:00:00 8:00:00
Sept 18, 2024
8:00:00
8:01:24 8:01:48
Skew = +84 seconds Skew = +108 seconds
Oct 23, 2024
+84 seconds/35 days +108 seconds/35 days
Drift = +2.4 sec/day 8:00:00 Drift = +3.1 sec/day
Perfect clock
Computer’s time,
C
UTC time, t
Drift with slow clock
skew
Computer’s time,
C
UTC time, t
Drift with fast clock
skew
Computer’s time,
C
UTC time, t
Dealing with drift
Assume we set computer to true time
Not good idea to set clock back
– Illusion of time moving backwards can
confuse message ordering and software
development environments
Dealing with drift
Go for gradual clock correction
If fast:
Make clock run slower until it synchronizes
If slow:
Make clock run faster until it synchronizes
Dealing with drift
OS can do this:
Change rate at which it requests interrupts
e.g.:
if system requests interrupts every
17 msec but clock is too slow:
request interrupts at (e.g.) 15 msec
Or software correction: redefine the interval
Adjustment changes slope of system time:
Linear compensating function
Compensating for a fast clock
Computer’s time,
Clock synchronized
skew
Linear compensating
function applied
C
UTC time, t
Compensating for a fast clock
Computer’s time, C
UTC time, t
Resynchronizing
After synchronization period is reached
– Resynchronize periodically
– Successive application of a second linear
compensating function can bring us closer to true
slope
Keep track of adjustments and apply
continuously
– e.g., UNIX adjtime system call
Getting accurate time
• Attach GPS receiver to each computer
± 1 msec of UTC
• Attach WWV radio receiver
Obtain time broadcasts from Boulder or DC
± 3 msec of UTC (depending on distance)
• Attach GOES receiver
± 0.1 msec of UTC
Not practical solution for every machine
– Cost, size, convenience, environment
Getting accurate time
Synchronize from another machine
– One with a more accurate clock
Machine/service that provides time information:
Time server
RPC
Simplest synchronization technique
– Issue RPC to obtain time
– Set time
client what’s the time? server
3:42:19
Does not account for network or
processing latency
Cristian’s algorithm
Compensate for delays
– Note times:
• request sent: T0
• reply received: T1
– Assume network delays are symmetric
Tserver
server
request reply
client
T0 T1 time
Cristian’s algorithm
Client sets time to:
Tserver
server
request reply
client
T0 T1 time
= estimated overhead
in each direction
Error bounds
If minimum message transit time (Tmin) is known:
Place bounds on accuracy of result
Error bounds
Tserver
server
request reply
client
T0 T1 time
Tmin Tmin
Earliest time Latest time
message arrives message leaves
range = T1-T0-2Tmin
accuracy of result =
Cristian’s algorithm: example
• Send request at 5:08:15.100 (T0)
• Receive response at 5:08:15.900 (T1)
– Response contains 5:09:25.300 (Tserver)
• Elapsed time is T1 -T0
5:08:15.900 - 5:08:15.100 = 800 msec
• Best guess: timestamp was generated
400 msec ago
• Set time to Tserver+ elapsed time
5:09:25.300 + 400 = 5:09.25.700
Cristian’s algorithm: example
If best-case message time=200 msec T0 = 5:08:15.100
T1 = 5:08:15.900
Ts = 5:09:25:300
Tserver Tmin = 200msec
server
request reply
client
T0 T1 time
200 200
800
Error =
Berkeley Algorithm
• Gusella & Zatti, 1989
• Assumes no machine has an accurate time
source
• Obtains average from participating computers
• Synchronizes all clocks to average
Berkeley Algorithm
• Machines run time dæmon
– Process that implements protocol
• One machine is elected (or designated) as the
server (master)
– Others are slaves
Berkeley Algorithm
• Master polls each machine periodically
– Ask each machine for time
• Can use Cristian’s algorithm to compensate for network
latency
• When results are in, compute average
– Including master’s time
• Hope: average cancels out individual clock’s
tendencies to run fast or slow
• Send offset by which each clock needs
adjustment to each slave
– Avoids problems with network delays if we send a
time stamp
Berkeley Algorithm
Algorithm has provisions for ignoring readings
from clocks whose skew is too great
– Compute a fault-tolerant average
If master fails
– Any slave can take over
Berkeley Algorithm: example
3:00
2:50
3:25 2:50 9:10
1. Request timestamps from all slaves
Berkeley Algorithm: example
3:00
2:50
3:25 2:50 9:10
2. Compute fault-tolerant average:
Berkeley Algorithm: example
+0.15
3:00
+0:15
3:25 2:50 9:10
3. Send offset to each client
SNTP
Simple Network Time Protocol
– Based on Unicast mode of NTP
– Subset of NTP, not new protocol
– Operates in multicast or procedure call mode
– Recommended for environments where server is root
node and client is leaf of synchronization subnet
– Root delay, root dispersion, reference timestamp
ignored
SNTP
T2 T3
server
request reply
client
T1 T4 time
Roundtrip delay: Time offset:
d = (T4-T1) - (T2-T3)
SNTP example
T2=800 T3=850
server
request reply
time
client
T1=1100 T4=1200
Offset =
((800 - 1100) + (850 - 1200))/2
=((-300) + (-350))/2
= -650/2 = -325 Time offset:
Set time to T4 + t
= 1200 - 325 = 875
Cristian’s algorithm
T2=800 T3=850
server
request reply
Ts=825 time
client
T1=1100 T4=1200
Offset = (1200 - 1100)/2 = 50
Set time to Ts + offset
= 825 + 50 = 875
Key Points: Physical Clocks
• Cristian’s algorithm & SNTP
– Set clock from server
– But account for network delays
– Error: uncertainty due to network/processor
latency: errors are additive
±10 msec and ±20 msec = ±30 msec.
• Adjust for local clock skew
– Linear compensating function
The end.
