A Probabilistic Approach to Distributed Clock Synchronization
Flaviu Christian

This paper presents a probabilistic approach to achieving clock
synchronization in systems with no assumed maximum message delay and with a
higher precision than deterministic approaches that assume a bounded message
delay or approaches that link clock synchronization to a partition detection
timeout.

By allowing for the possibility of not achieving rapport, the papers
algorithm is able to provide better precision for synchronized clocks with
only a small probability of failure.  The implied assumption is that at
least for some, if not many, systems that require higher precision, the
small probability of failure is acceptable.
Besides the idea of a probabilistic, rather than deterministic, approach to
clock synchronization, a major contribution is the allowance of multiple
synchronization attempts prior to failure which reduces the probability of
failure.

Although included as extension of the main algorithm, the discussion of
various master and slave failures, as well as adapting to changing system
load rounds out the paper well.

The paper's decisions not to deal with the problems caused by UTC time
discontinuities and the assumption that the external time source is reliable
and always available are two weaknesses.  An implementation would have to
deal with these issues, and a "leap second" would certain have some affect
on the synchronization unless the desired precision were significantly worse
than 1 second (which in modern systems is unlikely).  Although these may be
research topics in their right, as is mentioned for external time source
reliability and availability, some discussion of their effects on the
probabilistic algorithm would have been useful and insightful.

Another weakness was the lack of discussion on the assumed initial state of
the clocks and whether some form of initial rapport is needed for the
algorithm to function correctly.  And if the clocks can be widely
out-of-synch initially, the effects of possibly very slow or very fast clock
movement during amortization on the system would be interesting.

With the need for clock synchronization across vastly distributed systems,
this paper is relevant to modern systems.  Because with the internet
currently the communication medium of choice, a hard upper bound for message
delays is near impossible to establish and thus fully deterministic
approaches can not be used or, at least, would yield unacceptable precision.