interesting clock sync facts
Sun Mar 22 00:18:30 UTC 1987
To change the topic from the "time_t doesn't work for everything" series
of messages here is a note on about synchronizing clocks. And about the
limitations of time_t, it is something we can live with. Any extensions
should be extensions and not modification to time_t. Too breakable.
This has nothing at all to do with Posix, but, I thought that this
group might like to hear about it. Ignore if you want. If the wording
seems strange at times, bear with it. This was written in a stream of
consciousness mode. Note that there are many interesting algorithms
described in the OS literature about clock synchronization. Dave Mills
has been playing in the real world (TCP/IP connected machines) on how
to synchronize clocks. He found that human error accounts for a lot
of the problem (as is: "ahhh, was that supposed to be 'AM' or 'PM'?").
Suppose you have N clocks that you would like to synchronize. How
would you do it? The answer is "it depends". That is, it depends on
how much money you want to spend and how closely synchronized you want
the clocks to be. You can see that if you only want to spend one
postage stamp, the best you can achieve is +/- several days (the time
it takes the mailperson to deliver the letter containing a timestamp).
If you cough up some bucks for two modems, you can do better. Etc.
What do I mean by synchronization? The best explanation that I've
come up with is: consider how the Air Force's precision flying team
puts on a show. What matters to them is, first, how tight the formation
is, and second, where the planes are with respect to some ground-based
marker. Translating that example into clocks shows that clocks can
be very close to each other (== synchronized) but still give the incorrect
time (!= universal time). Sometimes synchronization is more important
than correctness (distributed databases that use timestamps are an example).
To get synchronization of clocks AND correctness calls for two things.
A mutually agreed upon reference time source supplies the correct time. A
convergence algorithm used between clocks supplies the synchronization.
Here's a list of time sources that I've heard of:
0. Set clocks at "factory"
I include this for completeness. Perhaps the atomic clocks are
set this way. I suspect some clocks in satellites are set this way.
1. The electrical "power grid"
This is the familiar 60 Hz (or 50 Hz) AC electric line. One could
devise a simple counter of the frequency so that all clocks would
always be in step with each other. Unfortunately there are several
problems. The first is how to initially synchronize the clocks.
Also, there are several (5?) different grids in the 48-state area of
the US that are not in sync with each other. Plus, each power-grid
master clock is only consistent when averaged over the entire day.
When peak demands occur, you aren't getting the full 60 Hz per second
that you would expect. I've heard that by about 6pm, the grid is
lagging by up to 10 seconds. However that lost time is made up while
(most) people sleep so that the alarm clock is correct at 8am.
[as an aside: leave work early tomorrow and if anyone asks, just give
them the above reason :-)]
2. Phone system
Each line used by for phone traffic has some timing-dependencies.
Major trunk lines have to synchronize. I don't know the details
of how the clocks are set. I vaguely remember something about a
master clock for AT'n'T located in Indiana (Illinois?) that serves as
the reference clock for the entire network. Anyone know more?
Problems with this is that the clock is not reachable by users not
in the phone company for free (maybe one could lease a T-1 channel and
count bits or watch for the 193'rd etc.).
3. Solar based
I've read where early clocks were synchronized to noon by someone
who watched an instrument's scale for the instant that the sun be
at the highest point in the sky. A tiny filament in the instrument
served as the focal point for a slit of sunlight, the instrument
could only be tilted north and south so that the seasonal tilt was
adjusted for. Problems are that it is tedious and labor-intensive.
How to set up the solar spotting tube sounds pretty tricky to me.
4. Universal time
This is the collection of atomic clocks (over 100 of 'em) around the
world that maintain the time. What's good is that is set up, working,
and is correct. Problem is dissemination. Unless you are close to
an actual clock, there is some delay. However, it is on the order of
milliseconds, not too bad. Expenses are getting a receiver for the
signal. In the US, there are several frequencies for WWV. Worldwide,
one can use a satellite's broadcast if you are lucky enough to be in
its "footprint". The GOES satellite serves North America and some of
Pan America. I don't know if there is an equivalent satellite for
Europe, Africa or Asia. Using a satellite means you have to pop for a
5. Neutron star
A spinning neutron star is very periodic. Some are more than others.
One neutron star has been watched for over a decade. During that
time, it has shown remarkable consistency -- on par with an atomic
clock. I'd have to rummage through my notes to get its designation.
Problems: besides buying and installing a radio telescope it is
OK, we got a source of time. Now how do we set the clocks?
A convergence algorithm can be structured one of two basic ways.
The simplest is in a master/multiple-slaves organization. The harder
to implement way is in a distributed fashion where each clock shares
its "time" with all other clocks. One has to worry about faults (and
Byzantine faults, ie, clocks that are "broken" and give different readings
depending on who asks it for the time), and compensating for delay in
messages between clocks. But the second way leads to some nice advantages
for a data network (deadlock detection is easier, can timestamp things
for local and remote use, ...)
Another problem is related to how clocks move -- forward. Suppose you
are going to reset your clock to a new value of time. What happens if
that new value is less than the current reading of a clock? Strange things
may happen if you set the clock back! Two ways around this are (1) to "stop"
the clock until the clock's reading equals the new time and (2) to run the
clock slower for a while. On my old pendulum clock at home, I can shorten
or lengthen the pendulum if the clock is running slow or fast, respectively.
One can't really change the rate of a digital clock. So, one uses the
first method. For an OS that updates its clock by seeing interrupts, if
the clock is too far ahead some of the updates can be skipped. If the clock
is behind, double up some of the clock updates. Careful consideration needs
to be done to see if anything (accounting for one!) breaks. Best to do it
when no one is using the machine (but then if updates are scheduled for at
night and the machine's clock is 12 hours off, strange things will happen).
Berkeley's TEMPO time synchronization protocol changed how the clock
is set to be better than one second resolution. [If I could find the
paper now, I could tell you more. It was in a Usenix proceedings of a
couple years ago.]
More information about the tz