interesting clock sync facts

seismo!nbires!vianet!devine seismo!nbires!vianet!devine
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
   dish antenna.

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
   very easy...

  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.]

Bob Devine

More information about the tz mailing list