Implementing a Probabilistic Clock Synchronization Algorithm.
In this paper we present a new probabilistic clock synchronization algorithm, its prototype implementation and experimental results. The algorithm follows the client-server programming paradigm and is designed to work in a departmental environment with few servers and a number of clients connected through an arbitrary network topology. At the core of the algorithm is a remote clock reading method that mitigates the negative effects of message delay uncertainty. The implementation proves the effectiveness of this approach and corroborates the theoretical speculations.
Introduction
In a distributed system there are strong reasons to keep the clocks of the units as synchronized as possible
since sharply synchronized clocks can ease the development of several distributed applications such as real
time control, performance evaluation tools, distributed simulations, transaction processing, data recovery,
atomic broadcast, group membership and many others [9].
However, the task of keeping the clocks synchronized is a hard one, since:
ffl variable clock drift
A hardware clock doesn't measure the time at the desired speed of 1sec=sec but, even if fault-free and
initially synchronized with a standard time reference, it tends to drift away from it. The drift rate
itself varies during the lifetime of the clock, and according with external conditions in an unpredictable
ffl message delay uncertainty
The messages that convey timing information are exposed to unforseeble delays. This delay uncertainty
is due to a number of different factors such as network load, queuing delays, I/O throughput, protocol
stack implementation and others.
Therefore even perfectly synchronized clocks tend to diverge and cannot be exactly resynchronized.
The primary goal of a distributed synchronization service is to keep all non-faulty clocks synchronized
within is called the synchronization precision, and is a key parameter to evaluate the performance
of a synchronization service [9].
In the literature, we can identify two different approaches to implement a distributed clock synchroniza-
tion. An internal clock synchronization algorithm keeps each node's clock synchronized within
while an external synchronization algorithm keeps each node's clock synchronized within time units from
an external time reference such as UTC (Universal Time Coordinates) or GPS (Global Positioning System).
A number of deterministic clock synchronization algorithms has been published [4, 8, 10, 14]. Most
of them are structured around periodic rounds of broadcast communication and address fault tolerance
aspects; for a survey see [13]. An important result [11] fixes the upper bound
Universit'e Catholique de Louvain
y Universit'a degli Studi di Pisa
the synchronization precision for deterministic algorithms executing in a distributed system with N nodes.
Here min and max are the minimum and maximum network delay and the quantity (max \Gamma min) gives an
indication of the network delay uncertainty.
According with these results, in networks with unbounded message delay, even if we assume that all system
nodes are fault-free, it is impossible to achieve clock synchronization through a deterministic algorithm.
In order to overcome this limitation, probabilistic clock synchronization algorithms have been proposed
[2, 5, 12]. These algorithms are probabilistic since there is a non null probability p fail that the precision of
the system clocks will exceed ffi time units. Furthermore p fail can be determined or at least bounded [2].
Relaxing the deterministic constraint, probabilistic algorithms are able to keep a given synchronization
precision even in systems where there is no upper bound on message delays, with a probability of failure
that is comparable with the reliability figures of the processing units [2, 5].
This work presents a probabilistic clock synchronization algorithm that adopts the remote clock reading
method of [1] and a client-server approach similar to the one in [5]. Unlike the one in [1] this algorithm
tolerates transient faults provided that they will not occur during synchronization periods. Transient faults
during the synchronization periods prevent the correct behavior of the algorithm only during that period;
therefore correct synchronization will be re-established during the first fault-free synchronization period.
The effectiveness of the algorithm is proved by some results obtained through a prototype implementation.
The rest of the paper is organized as follows. In Section 2 we introduce our model of the system. In
Section 3 we present and analyze the remote reading method adopted by our algorithm that is presented in
Section 4; Section 5 contains the description of the implementation and the results of the experiments and
Section 6 concludes the paper with some final consideration.
2 The Distributed Time Service
A distributed system consists of a set of nodes, interconnected by a communication network, exchanging
information only by means of messages. Each node N i is equipped with a hardware clock HC i of quartz
accuracy.
A hardware clock implements a monotonic increasing function of time HC(t) and is characterized by ae,
the maximum clock drift rate from real time. We define a predicate Correct that defines the requirements
a hardware clock must comply with over the time interval
Hardware clocks can only be read but not modified by software modules; we introduce logical clocks that
implement adjustable clocks. A logical clock LC(t) is a function of the underlying hardware clock HC(t)
(and hence of time t), and is implemented by a simple data structure. For example in [5] a logical clock LC
is a pair of real values (A; B) such that B: the rate of LC changes according
with the value of A while B is an offset value; the logical clock is equivalent to HC(t).
As already stated in the previous section, the goal of a distributed time service is to keep the values of
all logical clocks LC(t) synchronized within
With respect to the time service, we will partition the system nodes into two disjoint sets: Time Service
Servers and Time Service Clients. Every node i in Time Clients (Servers) runs a Client (Server) Synchronization
. The set of all the synchronization tasks cooperate to implement a distributed time service
by exchanging timing information over the network and acting on their logical clocks. Any other task may
access this service through a set of time service interface calls.
Thereafter, since clock drift ae is much smaller than one, we will neglect terms of the order of ae 2 or
higher in expressions whose value is comparable with the unit or larger. Such approximation in polynomial
expansions justifies (1
3 Reading a remote clock
In order to achieve clock synchronization we have to provide each node with the capability of remotely
reading the clock of another node of the system; the more precise this method is, the better the algorithm
will perform. In this section we briefly introduce the remote reading method of [1], and we analyze its
efficiency.
To read the remote clock of node S, the synchronization task PC running on client node C sends at real
time t 0 a message to the synchronization task PS on server node S. Let the message be delivered to PS
at real time t r ; the receiver immediately sends a reply message containing the value LCS (t r ). At real time
receives the server reply (see Figure 1 ).
min +a min +b
Client Node
Server Node
tr

Figure

1: Remote clock reading rule
min be the minimum point to point message
delay between PS and PC the following holds [1]:
and the hardware clocks of the nodes C and S are correct then the
value of the server's clock when the client receives the reply containing the clock value LCS (t r ) is
within the interval:
where
The proof follows directly from the one in [5] for a similar statement.
The following theorem is a direct consequence of the above lemma and indicates that, when the client
receives the reply, it can compute an approximation of the clock of the server and bound the precision of the
approximation.
Theorem 1 Under the hypotheses and the notation of Lemma 1, at time t 1 , when PC receives the reply
from PS , PC can compute an approximation LC C
of the clock of the server at that time, and bound the
difference between the approximation and the real value of the clock of the server with the upper bound /
computed as follows:
In order to evaluate the effectiveness of our method with respect to the one proposed in [5] we compare
Equations 6 and 7 to the corresponding ones derived according to the rules in [5]:
Thereafter, for the sake of clarity, we ignore also terms of the form D   ae: since the figures used in the
formulas have a magnitude comparable with that of D, a term D   ae can be neglected.
The following statement says that the clock precision obtained using our clock reading rule compares
favorably with that obtained using Cristian's rule:
Corollary 1 Using the notation introduced in Theorem 1, if
it holds that
and
ff MAX
The previous corollary identifies the cases when our reading rule performs better than that defined in [5],
and gives the corresponding error estimates. To complete the comparison we need a result stating that our
reading is not worse than the other in any other case:
Corollary 2 Using the notation introduced in Theorem 1, if
it holds that
The above Corollary states that, when the hypothesis is satisfied, the reading method either does not
improve the present knowledge of server's clock, in that case returns an approximation of that
value which is the same that would have been obtained with the application of Cristian's rule, and in that
case In either case, the reading accuracy is at least D \Gamma min.
From the above two corollaries we can derive an important conclusion stated by the following:
Corollary 3 If a client reads a server clock following the reading rule of Theorem 1 the error in approximating
the server clock at real time t 1 is not worse than the current approximation of the clock precision
The reader understands that the role played by the reading rule in a clock synchronizaton algorithm is
that of obtaining a new clock value whose distance from the current server's clock is smaller than that of
the current clock value; the result of a clock reading operation that does not satisfy this basic requirement,
expressed by the inequality completely useless. Therefore we say that when the clock
reading attempt has been successful. Otherwise, and from Corollary 3 we know that in that case
the clock reading attempt has been unsuccessful, and the result can be simply discarded.
The above discussion indicates the algorithm that should be followed in order to compute the value of /:
function read-rule(var t: time; var psi:time; lc:logical-clock);
begin
begin
else
else
else
In order to design a probabilistic clock synchronization algorithm we need to know the distribution of
the reading precision. To this purpose, we introduce the stochastic variable / and analyze the distribution
as a result of the distribution of other stochastic variables that may be reasonably assumed as known.
We introduce two auxiliary variables that have a relevant intuitive meaning and whose distribution can be
easely obtained by sampling or analitically. Let ffi real the real difference between the clock of the server and
that of the master
real the apparent delay of the request message; it is the time that the server could estimate if the
client's message were timestamped with client's clock value;
real the apparent delay of the reply message, as might be observed by the client;
Using these variables, the Corollary 1 can be rewritten as follows
Corollary 4 Let x
the reading operation is unsuccessful.
We recall that we are now evaluating an analytical expression for the probability of having a reading
precision better than a certain threshold: none of the variables mentioned in the previous expression is in
fact computed by the client or the server of the clock synchronization service.
The probability that the client reaches rapport with the server is given by the following compound
probability, that uses the stochastic valiables x 1 and x 2 associated with x 1 and x
Theorem 2 Using the notation introduced in Corollary 4 we have that, for any value /
distribution of the reading precision / is given by:
which depends on the distribution of the communication delays x 1 and x 2 , and on the precision of the
current clock, ffi 0 . In the sequel we will indicate the density and distribution functions of the reading precision
as
and
respectively, to show their dependency from the value of the current clock precision.
X: communication delay exceeding min (msecs)

Figure

2: Distribution of the offset of the communication delay from min
To show the impact of Corollary 1, we have simulated an environment similar to that illustrated in [5], and
compared the results of the two reading rules by plotting the distributions of the reading precisions obtained
using Cristian's reading rule, and the reading rule presented in this paper. Figure 2 shows the distribution
of the offset delays ff and fi, that have been generated using a W eibull(1:3; 0:2) distribution, that model
communication delays. In Figure 3 the reading precision distributions are plotted for
showing that our reading rule improves significantly the performance of Cristian's one.
4 The probabilistic algorithm
The basic idea of the probabilistic clock synchronization algorithm, as introduced in [5], is that each client
repeatedly reads the server's clock, trying to reach contact with it by reading its value with a precision better
than a predefined ffl; the protocol used to read the remote clock has been illustrated in the previous section.
The client is not allowed to fail undefinitely: after a certain timeout elapses from the last contact, the client's
clock is considered faulty and the client is considered unable to carry out time critical tasks. The timeout
depends on the minimal synchronization precision that allows an acceptable coordination of the time critical
system activities.
In order to succeed in reaching contact with the server with a given probability, usually higher than that
associated to the single attempt, the clock synchronization algorithm will start a series of at most K clock
reading attempts hopefully concluded by a contact before the timeout expires. The designer is in charge of
deciding how many attempts have to be available before that time, in order to guarantee that the client will
be able to synchronize with the server before the last attempt with a probability higher than that required
by the reliability associated with the time syncronization service.
Note that, since each attempt is considered as an independent experiment, two successive attempts should
be separated by a period of time W sufficient to ensure their statistic independence on the possible causes
preventing a rapport such as network load peaks, system performace degradations and many other transient
events: therefore, if we envision at most K attempts, the clock synchronization algorithm will start operating
K   W time units before the timeout expires. Preciser details on the timing of the algorithm can be found
in [5].
Let us analyze how the clock synchronization algorithm operates in our case. The clock synchronization
starts by creating a temporary logical clock TLCC identical to LCC ; then it sets 1. Until the next
rapport, all the time information needed to execute the protocol at the client side is measured according to
Alari and Ciuffoletti
Cristian

Figure

3: Comparison between success frequencies of the reading rules when (each point
10000 experiments)
TLCC . At each successful attempt of reading the server's clock (i.e., each time the reading error / is lower
than are updated by the following rules:
otherwise only ffi 0 will be updated by:
At rapport (i.e. whenever / - ffl), instead of updating TLCC , PC adjusts the value of LCC , discards
TLCC and computes the time when the next clock synchronization operation will be invoked as a function
of ae, K, W , / and of the overall synchronization precision ffi. On the other hand, if after K consecutive
reading attempts PC does not reach contact with the server, then it signals the exceptional event to upper
layer software levels.
The following program unfolds the previous description of client's activity:
forever
begin
delta0
count :=
while (count ! K) and (psi ? epsilon) do
begin
delta0
node-failure
else
clock-copy(TLC,LC)
As mentioned above, a key role is played by K: in order to evaluate its value as a function of the
communication delay distribution, of the required precision and reliability, we introduce a Markov process
that describes the precision of TLCC after the n-th clock reading attempt:
and, since at the first attempt we have no knowledge of the server's clock, that attempt is surely successful
and returns a :
that, in our example, corresponds to the Weibull density plotted in Figure 2. Then, using the Chapman-
Kolgomorov theorem:
p(/n j/
Since the value of / at the i-th attempt is used, incremented by 2   ae   W , as the value of ffi 0 in the next
attempt, we can compute the transition probability p(/n j/
p(/n j/
has been discussed in the previous section,
and its distribution has been plotted in Figure 3. Therefore we can write:
which can be computed numerically by recusion on n.
Once computed the Markov process, the value of K will be chosen so that (/ K indicates the stochastic
variable associated with /K
4.1 Comparison with other related algorithms
The main difference with respect to [5] is in the new clock reading rule: we have proved that the improvement
introduced by our rule may be significant and favorably reflects on the overhead introduced by the clock
synchronization algorithm.
On the other hand, the protocol presented in this paper shares several features with Cristian's one: it
does not require an upper bound for the communication delay, and tolerates transient faults occurring in
the lapse between two successive synchronizations.
This last feature is the most significant improvement with respect to our previous proposal, presented
in [1], and is obtained by assuming that the algorithm restarts each time with a "zero knowledge" hypothesis.
This option introduces a kind of self-stabilizing behavior [6]: the client gets finally synchronized regardless
of the initial value of the clock LCC . Therefore the client is able to resume a correct synchronization as soon
as its functionality is restored, without an explicit recovery activity. This characteristic greatly simplifies
the design of complex systems, improving their reliability.
Finally, another inprovement with respect to [1] is that now ffi 0 is not any more related to the overall
service precision ffi widening the applicability of the new algorithm to services where ffi is big comapred to
message delays.
5 Implementation
5.1 Software and Hardware environment
In this section we present the result of two experiments running on the network infrastructure consisting of
two 10Mb=s thin Ethernet segments interconnected by a routing host and depicted in Fig. 4; hosts are Sun
workstation whose clock resolution is of the order of microseconds. In the first experiment the time clients
and the time server were hosted on the same Ethernet segment while in the second one they run on hosts
located on two different segemnts.
Client and server software is written in the C programming language [7] and the communication protocol
used to send messages over the network is UDP, the connection-less service offered by the TCP/IP protocol
suite [3], [15]. We decided to implement the service over a connection-less protocol for two main reasons:
ffl connection-less protocols are lighter than connection oriented ones, so they introduce less overhead and
a small message latency
ffl loss of messages does not cause problems because it can be modelled as an extremely long network
this delay will be reflected in an unsuccessful remote clock reading attempt.
Time Client
Time Server
Time Client
ROUTER
10Mb/s
10Mb/s

Figure

4: Experiments setup
We programmed two time clients: one implementing Cristian's algorithm and the other the algorithm
described in Section 4. Time clients were run on the same host and started at the same time so that the
performace measurements of our time service and of Cristian's one were taken under approximately the same
network and host load; this implies that the differences in the obtained results are essentially due to the
algorithms implemented by the two time clients.
Experiments run during normal network activity and all refer to 1000 clock reading attempts. Once fixed
the value of ffi to two and three milliseconds for the single Ethernet segment and for the routed environment
respectively, we then sampled network delays and appropriately set the remaining algorithm parameters
to have an overall service failure probability p fail of the order of 10 \Gamma6 . The maximum reading error was
therefore set so that a single reading attempt with reading attempt such that
had probability of reaching contact p 0:35 and the maximum number of consecutive reading attempts
was 30. The time between two consecutive attempts was set to and the client drift rate with
respect to the server clock was found to be bounded by ae
With this setting, in the worst case assumption that we never improve with respect to the algoritm of [5],
we get p that respects the above probability reqirements. In reality, following
the arguments of Section 3 and Section 4, we proved that under realistic assumptions on message delays the
probability of service disruption of our algorithm is less then the one of Cristian's.
5.2 Results

Tables

show reading error figures with respect to message delays experienced during the experiments,
the number of rapports obtained, mean DNA (Delay to the Next Attempt timeout) and a measure of the
communication cost in terms of messages per second obtained using the formula NumOfMessages
Duration where
NumOfMessages is the total number of messages exchanged between the client and the server processes
and Duration is the duration in seconds of the experiment 1 .
Algorithm mean delay mean error rapports mean DNA cost
Cristian 1594.1 794.1 252 26.70 0.246
Alari Ciuffoletti 1481.6 526.7 403 31.71 0.143

Table

1: Delays and reading errors (in -sec), rapports, DNA (in sec) and communication cost (in msg/sec)
for the single subnet experiment;
Algorithm mean delay mean error rapports mean DNA cost
Cristian 1849.4 749.4 269 28.03 0.222
Alari Ciuffoletti 1940.9 643.2 361 29.79 0.166

Table

2: Delays and reading errors (in -sec), rapports, DNA (in sec) and communication cost (in msg/sec)
for the two subnet experiment;
The cost figure quantifies the benefits obtained by the application of the protocol presented in this paper:
due to the increased clock reading precision (see columns 1-2 in the tables), we obtatin more successful
attempts and a longer period between two successive synchronization periods (see columns 3-4 in the tables)
and consequently less message exchanges are performed during the same time period.
It is also important to analyze the different behavior of the two reading methods with respect to another
protocol parameter, min. In both the experimets the value assigned to min was about 100 -sec smaller
with respect to the real minimum delay experienced during the experiments. Again, our reading method
was able to overcome this fact because the discrepancy between the experienced minimum delay value and
min was absorbed by fi min and fi max approximations. On the contrary, with the clock reading method of [5],
the difference between min and the effective point to point client server minimum delay is directly reflected
in the reading error (see Equation 8).
The numerical results of our experiments presented in the above tables is visually rendered by the following
Figures plotting the frequencies of two relevant parameters common to both the probabilistic algorithms:
the DNA period and the number of attempts between two consecutive contacts.
In

Figure

5 the frequencies of DNA are plotted for the case of the single Ethernet and two Ethernet
segments: the improvement of our variant is significative since the values of the DNA period are higher in
our case reflecting the fact that the mean remote clock reading error is small.
In

Figure

6 the frequencies of the number of attempts before reaching contact are plotted for the case
of the single Ethernet and two Ethernet segments. Also for this significative parameter the new algorithm
presents advantages with respect to the algorithm of [5] since it reaches higher frequencies for small values
of the number of attempts with respect to the algorithm by Cristian. This indicates that, as studied in
Section 4, our time client has a higher probability to have contact with the time server hostcomaperd to the
one of the time client implementing the probabilistic algorithm described in [5]. So, our protocol permits a
time client to obtain more contacts with the time server process and to get a minimal remote clock reading
error, usually smaller than the reading error obtained with the probabilistic algoritm of Cristian.
NumOfAttempts (i.e. the number of messages per attempt times the total number of attempts
of the experiment) and Duration (i.e. the
time spent in unsuccessful attempts plus the number of successful attempts times the mean value of DNA experienced during
the experiment).
22 24 26 28
Comparison of frequeny of DNA (in sec.) at success, one Ethernet segment
Alari and Ciuffoletti Cristian0.050.150.250.350.4518 20 22 24 26 28
Comparison of frequeny of DNA (in sec.) at success, two Ethernet segments
Alari and Ciuffoletti Cristian

Figure

5: DNA (Delay to Next Attempt) frequencies0.10.30.50.70.9
Comparison of frequency of attempts before success, one Ethernet segment
Alari and Ciuffoletti
Comparison of frequeny of failures before success, two Ethernet segments
Alari and Ciuffoletti Cristian

Figure

Frequency of attempts to reach contact with the server
6

Summary

We designed and implemented a probabilistic clock synchronization algorithm. The strength of our implementation
resides in the remote reading method adopted; this method allows a sensible reduction of the
remote clock reading error by mitigating the negative effect of network delay uncertainty. Experimental
results confirm the effectiveness of the algorithm which improves the results in term of communication cost
with respect to other probabilistic time services.
A Proofs
A.1 Proof of Corollary 1
The corollary states that the value of LCS (t r ) must be outside an interval centered on the mid point of the
interval (as measured by the client) elapsing from the request of clock value and the receipt of the reply. We
can turn this requirement in the following inequalities:
If either inequality holds, then / ! D \Gamma min. From Inequality 13 we derive
ae
ae
We have therefore that
according with ff have that
ff MAX! fi MAX(15)
which concludes the first part of the proof.
From the Inequality 14 we derive
ae
ae
We have therefore that
according with fi
that concludes the proof of Corollary 1. 2
A.2 Proof of Corollary 2
We want to prove that
The inequality splits into two different cases that have to be considered separately. If
which is the case of a short roundtrip it follows that
ae
ae
We have therefore that
that concludes the first part of the proof.
On the other hand, if
which is the case of a long roundtrip it follows that
ae
ae
We have therefore that
and this concludes the second part of the proof. Summarizing, under the hypotheses of the corollary, we
have that
which is the same that
A.3 Proof of Corollary 3
We prove the corollary by dividing the domain of the possible reading scenarios into two subdomains; exactly
the ones corresponding to the Corollaries 1 and 2. For each of them we show that is impossible for / to
respect the error equation of the appropriated corollary and at the same time / ?
For the domain of Corollary 1 the error equation is
us first suppose
that following the proof of Corollary 1, LCS (t r
ff MAX
We now analyze both the cases of LCS (t r
This means that LCS (t r Equation 17 we have
is incompatible with the case at hand;
This means that LCS (t r it is in contrast with equation (17).
The same simple reasoning shows that
concluding the proof for the subdomain of Corollary 1.
Concerning the subdomain of Corollary 2 the error equation is that is manifestly
incompatible with / ? concludes the proof of Corollary 3. 2
A.4 Proof of Corollary 4
Note that the following inequalitites hold:
cUsing the above, the Inequality 13, that refers to the case where
In order to have a non empty interval, we also need fi c ? ff s . The Inequality 14, that refers to the case where
In order to have a non empty interval, we also need fi
Concerning the Corollary 2, the only case where the clock reading is significant is when
In terms of the new variables:
In that case we have that the reading precision is
(D
that can be rewritten as:
Which also implies the validity of Equation
rewrite the above assert as:
finally if )The proof that when x the reading attempt is unsuccessful is straightforward. 2
A.5 Proof of the theorems
The proof of Theorem 1 and Theorem 2 is immediate from Lemma 1 and Corollary 4 respectively. 2



--R

Improving the probabilistic clock synchronization algorithm.
Probabilistic clock synchronization in distributed systems.
Internetworking with TCP/IP: principles
Clock synchronization in the presence of omission and performance faults
Probabilistic clock synchronization.

The C programming language
Clock synchronization in distributed real-time systems
Using time instead of timeout for fault-tolerant distributed systems
Synchronizing clocks in the presence of faults.
An upper and lower bound for clock synchronization.
Probabilistic clock synchronization in large distributed systems.
A paradigm for reliable clock synchronization.
Optimal clock synchronization.
UNIX network programming.
--TR
Synchronizing clocks in the presence of faults
Using Time Instead of Timeout for Fault-Tolerant Distributed Systems.
Optimal clock synchronization
Clock synchronization in distributed real-time systems
Internetworking with TCP/IP: principles, protocols, and architecture
The C programming language
UNIX network programming
Optimal clock synchronization under different delay assumptions
A theory of clock synchronization (extended abstract)
Self-stabilizing systems in spite of distributed control
Probabilistic Clock Synchronization in Distributed Systems
A Paradigm for Reliable Clock Synchronization
TCP/IP;clock synchronization;distributed systems;distributed algorithms;probabilistic algorithms;local area networks