Perhaps the seminal work in computer clock synchronization is
Lamport's work that elucidates the importance of virtual clocks
in systems where causality is more important than absolute time
[Lam78]. In his system, computer has a local
clock which is incremented monotonically after each event that it
observes. Each message sent to another node also carries the
timestamp of the sender with it. When a node receives a message, it
advances its local clock its current value is less than the value in
the received message. This simple scheme is enough to guarantee that
timestamps can reconstruct the total ordering of any sequence of
events that were causal. That is, if event 
causes event 
, the
timestamp of is less than the timestamp of .
Over the years, many protocols have been designed for maintaining synchronization of physical clocks over computer networks [GZ89,ST87,Cri89,Mil94]. These protocols all have basic features in common: a simple connectionless messaging protocol; exchange of clock information between clients and one (or a few) servers; methods for mitigating the effects of nondeterminism in message delivery and processing; and an algorithm on the client for updating local clocks based on information received from a server. They do differ in certain details: whether the network is kept internally consistent or synchronized to an external standard; whether the server is considered to be the canonical clock, or merely an arbiter of client clocks, and so on.
Mills' NTP [Mil94] stands out by virtue of its scalability, robustness to various types of failures, self-configuration, security in the face of deliberate sabotage, and widespread deployment. NTP allows construction of a hierarchy of time servers, multiply rooted at sources of canonical, external time (see Section 4.2). Levels closer to the root have better accuracy and precision to the external standard, but lower levels can be more populous due to the high degree of fan-out possible from each server. Clients are typically children of multiple higher-layer nodes, using statistical methods to determine the best estimate of the current time.
As we will see in Section 6, an important feature of NTP is that it keeps a running estimate of a client clock's frequency relative to an external standard. This facilitates reasonably accurate timekeeping during long periods of disconnected operation.
Some methods of physical clock synchronization strive only to maintain internal consistency. However, others distribute time from an external standard--an ``out of band'' source of time. Frequently, these external sources are the time provided by government agencies tasked with maintaining and disseminating a country's official time. For example, the U.S. Naval Observatory's Time Service Department maintains the official time of the United States. USNO's ``Master Clock #2'' is steered by an ensemble of advanced hydrogen maser and cesium frequency standards [MMK99]. UTC, the most commonly used international standard timescale, is based on a weighted average of over 200 atomic clocks at over 50 such national laboratories [Tho97]. It is calculated at BIPM (Bureau International des Poids et Mesures) in Paris, France.
Many of these laboratories are involved in active research in the area of time transfer--that is, synchronization of geographically distant clocks. This ability is a fundamental requirement for any national laboratory whose mission is to transmit time to its users (citizens, the military, and so forth). It is also the technology that enables computation of aggregate time standards such as UTC. Many modern time transfer schemes have been developed.
Historically speaking, they all harken back to much older methods. An unprecedented surge of interest in timekeeping was seen in the 14th century as mechanical clocks swept Europe, often found in the belfries and towers of city halls and churches [Lan83]. Clocks in other forms had been known for at least a thousand years beforehand, such as the sundial or water-driven clepsydra. But these newer mechanical clocks were the first to be accompanied by automatically ringing bells--a simple form of time transfer. In 1845, the U.S. Naval Observatory began to disseminate time by dropping a ``time ball'' from atop a flagpole every day precisely at noon [BD82]. The ball was often used by ships anchored in the Potomac river that needed a calibrated chronometer for navigation before setting out to sea [SA98].
In modern times, the state of the art is in radio time transfer
methods. The first of these, seen originally in the 1920's, was the a
voice announcer on radio station WWV operated by the National
Institute of Standards and Technology. WWV is still in operation
today, along with its more recent cousin, WWVB, which provides
computer-readable signals in stead of voice announcements. The
modern-day service provides references to U.S. time and frequency
standards within one part in 
.
The most active subject of modern-day research is in two-way satellite time transfer [SPK00]. TWSTT allows two clocks connected by a satellite relay to both compute their offset from their peer. It is superior to methods such as WWV's radio broadcasts because it transfer is two-way, instead of solely from sender to receiver. Use of satellites also allows intercontinental time transfer. TWSTT methods are used to connect the time and frequency standards of national laboratories to BIPM in France for computation of international timescales.
Satellite navigation systems--most notably, GPS [Kap96]--have an important relationship to time. GPS provides localization service by allowing users to measure time of flight of radio signals from satellites (at known locations) to a receiver. The system needs synchronized time for the scheme to work; it also provides one-way time transfer to the user as a ``side effect'' of localization. (Recent work has focused on using GPS for two-way time transfer as well [LL99].) Although a complete discussion of the technical details is beyond the scope of this document, it is important to note that GPS is both a user and disseminator of USNO's timescale. Consumer GPS receivers can synchronize nodes to UTC(USNO) within 200ns [MKMT99].
In some cases, the time synchronization problem can be solved by not solving it--designing the system to avoid the need for the problem to be solved. A number of systems exemplify this design principle. Specifically, it is instructive to reconsider several localization and ranging systems. (The relationship between time and space is closely intertwined; time synchronization often goes hand in hand with localization.)
Many localization systems estimate the distance between two points by
measuring the time-of-flight of some phenomenon from one point to the
other. Generally speaking, a system emits a recognizable signal at a
sender 
, then times the interval required for the signal to arrive
at a receiver 
. If the propagation speed of the phenomenon is
known, the time measurement can be converted to distance. The
fundamental problem that must be solved is synchronizing and
in time so that the propagation delay can be properly measured. We
will briefly examine three systems that solve this problem in three
different ways.
Pinpoint, Inc.'s RF-ID system [] avoids the
synchronization problem by setting 
; that is, making and
the same node. The RF-ID system emits an RF pulse which is modulated
by the target and reflected back to the sender. The sender and
receiver are implicitly synchronized by virtue of being the same
device. This allows a measurement of the signal's round-trip time,
and therefore the range from the sender/receiver to the target.
The GPS satellite system, mentioned earlier, also localizes by
measuring the time-of-flight of RF signals. GPS also avoids
synchronizing (the satellites) with (the user's receiver) by
treating the clock bias between and as an unknown. Because
there are many redundant sending satellites, the receiver can lock
onto one additional satellite, solving for its
instead
of only 
. As we discussed earlier in
Section 3.1, this only works by virtue of the senders
being synchronized with each other.
Finally, ORL's Active Bat system [WJH97] synchronizes
with by using a synchronization modality different from the
measurement modality. In their system, modulo certain details,
simultaneously emits a (fast) RF pulse and a (slow) ultrasound pulse.
The time of flight of the RF pulse is negligible compared to that of
the ultrasound. The RF pulse can be considered an instantaneous
phenomenon that establishes synchronization between and with
respect to the ultrasound pulse.
Of course, the localization application (and these implementations in particular) are only representative. Many other systems use similar designs to avoid the need for synchronized clocks. For example, in the LOCUS distributed operating system [PWB$^+$87], consistency of distributed filesystem operations is ensured by dynamically selecting a single node as a synchronization point for a particular file-descriptor. By forcing all file operations to go through the synchronization point, no clock sync is needed to achieve maintain a consistent view of the total ordering of file events.