An Adaptive Coupling-Based Algorithm for Internal
Clock Synchronization of Large Scale Dynamic
Systems
⋆Roberto Baldoni1, Angelo Corsaro2, Leonardo Querzoni1, Sirio Scipioni1, Sara Tucci-Piergiovanni1
1 Dipartimento di Informatica e Sistemistica “A. Ruberti”
Sapienza - Universit`a di Roma Rome, Italy
{baldoni|querzoni|scipioni|tucci}@dis.uniroma1.it
2 PrismTech 4, Rue Angiboust, 91460
Marcoussis, France
angelo.corsaro@prismtech.com
Abstract. This paper proposes an internal clock synchronization algorithm which combines the gossip-based paradigm with a nature-inspired approach coming from the coupled oscillators phenomenon. The proposed solution allows a very large number of clocks to self-synchronize without any central control, despite node departure and arrival. This addresses the needs of an emergent class of large- scale peer-to-peer applications that have to operate without any assumptions on the underlying infrastructure. Empirical evaluation shows extremely good con- vergence and stability under different network settings.
1 Introduction
Clock synchronization is a fundamental building block for many distributed applica- tions. As such, the topic has been widely studied for many years, and several algorithms exist which address different scales, ranging from local area networks (LAN), to wide area networks (WAN). For instance, the Network Time Protocol (NTP) [23,24], has emerged as a standard de facto for external clock synchronization in both LAN and WAN settings. The work presented in this paper is motivated by an emergent class of applications and services, operating in very challenging settings, for which the problem synchronizing clocks is far from being solved. These applications are required to (1) op- erate without any assumption on deployed functionalities, pre-existing infrastructure, or centralized control, while (2) being able to tolerate network dynamism, due to crashes or to node joining or leaving the system, and (3) scaling from few hundred to tens of thousands of nodes. For instance, publish/subscribe middleware, such as the data distri- bution service [1] requires synchronized clocks, however in several relevant scenarios,
⋆The work described in this paper was partially supported by CINI-Finmeccanica and the EU Project Resist.
due to security issues, or limited assumptions on the infrastructure, it cannot assume that members of the system, either have access to an NTP server, or are equipped with an NTP daemon.
A promising approach to tackle this kind of problems is to embrace a fully decen- tralized paradigm in which peers implement all the required functionalities, by running so calledgossip − based algorithms. In this approach, due to the large scale and ge- ography of the system, each peer is provided with a neighborhood representing the part of the system it can directly interact with. The algorithm running at each peer com- putes local results by collecting information from this neighborhood. These results are computed periodically leading the system to gradually compute the expected global result. In this paper, in order to obtain clock synchronization, we combine this gossip- based paradigm with a nature-inspired approach coming from the coupled oscillators phenomenon. This phenomenon shows enormous systems of oscillators spontaneously locking to a common phase, despite the inevitable differences in the natural frequencies of the individual oscillators. Examples from biology include network pacemaker cells in the heart, congregations of synchronously flashing fireflies and crickets that chirp in unison. A description of the phenomenon was pioneered by Winfree [2]. He mathe- matically modeled a population of interacting oscillators and discovered that assuming nearly identical individual frequencies and a certain strength of the coupling (which is a measure of the sensitivity each oscillator has to interactions with others), a dramatic transition to a globally entrained state, in which oscillators freeze into synchrony, oc- curs. A valuable contribution has been subsequently introduced by Kuramoto [3] who simplified the Winfree model by considering the coupling strength constant for all os- cillators and depending only on their phase difference. Both Winfree’s and Kuramoto’s work was done assuming that each oscillator is coupled directly and equally to all oth- ers, which means assuming a fully connected oscillators network. However a consider- able amount of work has been done also on so called “non-standard topologies”. Satoh in [5] performed numerical experiments comparing the capabilities of networks of os- cillators arranged in two-dimensional lattices and random graphs. Results showed that the system becomes globally synchronous much more effectively in the random case.
In fact, Matthews et al. in [6] note that the coupling strength required to globally syn- chronize oscillators in a random network is the same as the one required in the fully interconnected case.
In this paper we adapt the Kuramoto model to let a very large number of computer clocks synchronize over a random graph. The first issue we tackle is how to artificially reproduce the physical phenomenon in a network of computer clocks in which every clock can be influenced by other clocks only by exchanging messages reporting local values. In our approach, each clock (process) explicitly asks clock values from neigh- boring processes in order to calculate their difference in phase. Then, following our Kuramoto-like model, these differences in phase are combined and multiplied by a so- called coupling factor, expressing the coupling strength, in order to adjust the local clock.
As the coupling factor has a key role in regulating the dynamics of coupling, we study thoroughly its impact on the performance of the proposed solution. First, we consider a time-invariant coupling factor identical for all oscillators. Different constant
coupling factors are then evaluated to investigate their effect on system perturbations specific to target settings (basically deployed on a wired computer network): (1) er- rors on the phase difference estimates due to network delays and (2) neighborhoods possibly changing over time. As a general result, low coupling factors lead to better synchronization regardless of system perturbations–all clocks lock to a value such that their differences are negligible. On the other hand, higher coupling factors lead to a faster locking at the cost of more dispersed values. This phenomenon depends on the fact that a higher coupling factor augments the sensitivity a clock has with respect to other clocks but it also increases the influence of system perturbations.
Another fundamental aspect this approach revealed is its unprecedented scalability:
the time to converge to a common value remains the same considering both a few dozen nodes and thousands nodes, with even a small reduction in the latter case.
Even though these observations are really encouraging per se, we further improve the system behaviour by using an adaptive coupling factor, with the objective of reduc- ing the impact of system perturbations while still keeping the time to converge small.
This new approach has been revealed really successful, both in the case of errors phase estimates due to network delays and in the case of changing neighbors. The idea is simple: the local coupling factor reflects the age of a node (expressed by the number of adjustments already performed); a young node will have a high coupling factor to absorb soon values from other nodes, while an old node will have a small coupling factor to limit its sensitivity to system perturbations. The rationale behind this mecha- nism comes from the observation that an old node is more aligned to the values of other clocks than a new one. With this adaptive coupling factor, a young node, supposed to have a value generally far from other clock values, will rapidly align its value to others since the system perturbations have a small impact when the relative clock differences are still huge. Then, when nodes reach good values, i.e. their relative differences are small, a lower coupling factor lets to maintain these differences small despite system perturbations. This strategy reveals to be particularly useful in case of a dynamic sys- tem. Considering a network which starts and locks to some clock value, the perturbation caused by a massive entrance of new nodes (generally not synchronized with the ones which already reached a synchronization inside the network) could be dramatically re- duced when compared to a constant coupling factor. In other words, the adoption of adaptive coupling leads the system to maintain its stability, a property strongly needed in face of network dynamism. The rest of the paper is organized as follows: Section 2 presents the clock coupling model along with the algorithm. The experimental eval- uation is presented in Section 3. Section 4 discusses related works, while Section 5 concludes the paper.
2 Clock Coupling Model
Every computer is equipped with a hardware clock consisting of an oscillator and a counting register that is incremented at every tick of the oscillator. Depending on the quality of the oscillator, and the operating environment, its frequency may drift. Man- ufacturers typically provide a characterization forρ – the maximum absolute value for oscillator drift. Ignoring, for the time being, the resolution due to limited pulsing fre-
quency of the oscillator, the hardware clock implemented by the oscillator can be de- scribed by Equation 1:
C(t) = f t + C0; (1)
where:(1 − ρ) ≤ f ≤ (1 + ρ) This clock model is assumed by all clock synchroniza- tion algorithms described in literature, thus we will also adopt it, and we won’t go in further details in characterizing its properties. In the remainder of this Section we will describe mathematical principles governing the coupling of different clocks in order to synchronize them.
2.1 Time Continuous Clock Coupling
Let us consider a system composed by N distinct clocks, with each clock Ci being characterized by a frequencyfi ∈ [1 − ρ, 1 + ρ], and characterized by equation (1).
Clocks are initially non synchronized, meaning that they might show different time readings at the same real-time.
Thanks to a continuous coupling of these clocks over time, they will lock to a so- called stable point: each clock will show the same value, without changing the value once reached.
Even though our coupling resembles the model proposed by [3,4], it is worth noting that Kuramoto modeled a non-linear oscillator coupling which is not directly applica- ble to our problem. In fact, the non-linear oscillator used by Kuramoto to model the emergence of fireflies flashing synchrony, models intentionally a phenomenon which is characterized by several stable points (which arise due to the sinusoidal coupling), i.e., the system does not converge to a unique point, but it can partition in subsystems each with a different stable point. On the other hand, for synchronizing clocks in a distributed system it is highly desirable that a single point of synchronization exists. This leads to consider a linear coupling equation of the form:
C˙i(t) = fi+φi
N XN j=1
(Cj(t) − Ci(t)), i = 1..N (2)
The intuition behind Equation 2 is that a clock has to speed up if its neighboring clocks are going faster, while it has to slowdown when they are going slower. The coupling constantφiprovides a measure of how much the current clock rate should be influenced by others. It can be shown analytically that Equation 2 has a single stable fixed point, and thus converges, in the case in which all the clocks are connected to each other. An empirical evaluation of the convergence of Equation 2, under different topologies, can be found in [28].
2.2 Time Discrete Coupling with Imperfect Estimates
The coupling model described in Equation 2 is not directly applicable to distributed systems as (1) it is based on differential equations, and thus continuous time, and (2) it assumes that the underlying topology is a fully connected graph. As shown below,
Equation 2 can be made applicable to distributed systems by (1) considering its discrete counterpart, and (2) explicitly introducing a dependency on the underlying communi- cation graph.
Ci(n + 1) = Ci(n) + fi∆T + +Ki
Ni Ni
X
j=1
[(Cj(n) − Ci(n)) ∗ edge(i, j)], i = 1..N
(3)
WhereKi = φif ∆T , Ni is the number of neighbors for clockCi, andedge(i, j) is 1 when the underlying communication graph has an edge (i, j), 0 otherwise. When applying Equation 3 in real distributed systems, the clock difference(Cj(n) − Ci(n)) will be estimated with an errorǫ which depends on the mechanism used to perform the estimation. In this paper we assume that the difference between neighboring clocks are estimated as NTP does [23,24] (see Figure 1). Under this assumption, the real offset
Fig. 1. NTP offset estimation
betweenCi andCj is such that the error is(δ1− δ2)/2. Note that, if the two delays are equal (channel symmetry) the error is zero. Moreover, it has been shown that the maximum error is bounded by±(δ1+ δ2)/2 ≈ ±RT T /2, where RTT is the round trip time. Thus, we can now rewrite Equation 3 by considering the error which affects the (Cj(n) − Ci(n)) estimation:
Ci(n + 1) = Ci(n) + fi∆T + +Ki
Ni Ni
X
j=1
[(Cj(n) − Ci(n)) ∗ edge(i, j)]+
+Ki
Ni Ni
X
j=1
[(δi,j− δj,i
2 ) ∗ edge(i, j)], i = 1..N
(4)
Equation 4 shows howKi < 1 helps reducing the sensitivity of the coupling model on the estimation error. On the other hand,Kiclose to 1 provides faster convergence time,
as we will see later in the paper, while values greater than 1 make the system diverge.
As a final remark, it is worth pointing out thatKicould be made time dependent, and as we will see in the reminder of the paper, this could be very useful for making the solution more robust and performant.
Finally, if we consider the worst case bound on estimate error, it is worth pointing out that slow channels (high RTT) may introduce more noise than fast channels (low RTT), however, it is important to keep in mind that the source of error is not the RTT per se, but the asymmetry, i.e., the difference betweenδ1andδ2.
2.3 The Clock Coupling Algorithm
In order to translate Equation 4 into an algorithm, we should note that the valueCi is computed periodically, every∆T . As a result, the coupling-based clock synchronization algorithm proceeds in synchronization rounds, performing at each round the following steps:
1. Evaluate the difference with every neighboring clock, using a request-reply pattern of messages.
2. Sum the differences and multiply by KNi(n)
i .
3. Update the value ofCi, and the value ofKi, in the case in which it is time depen- dent.
In the following we provide the results of an extensive experimental study which high- lights the behaviour, convergence time, synchronization error, and stability, of the pro- posed algorithm.
3 Empirical Evaluation
The aim of this section is to show the behaviour of the proposed coupling algorithm when the different clocks are connected by a communication graph obtained through a peer-sampling service [26]. The mechanism evaluation is performed defining a set of metrics and then studying, through simulations3, their evolution in a set of scenarios each defined with the aim of isolating some specific aspects. In the reminder of this Sec- tion we will first describe the details of the simulation settings used for our evaluation, and then the final performance results.
3.1 Simulation settings
The proposed algorithm is evaluated against the metrics and the scenarios described below and summarized in Table 3.1.
Evaluation Metrics The metrics used to evaluate the proposed algorithm are its con- vergence time, synchronization error, and stability. A precise definition, for each metric, is provided below.
3Tests were run on Peersim, a simulation software specifically designed to reproduce large- scale scenarios. The simulator code for the coupling mechanism is available for download at the following address:http://www.dis.uniroma1.it/˜midlab/clocksync_
sim.zip
Static Symmetric Static Asymmetric Dynamic Symmetric
Convergence Time K, N – –
Synchronization Error – K, Asymmetry K, Stable Core%
Stability - – K, Injected nodes%
Table 1. Summary of evaluated scenarios, with metrics measured against which parameters.
Convergence Time. The convergence time metric is defined as the number of synchro- nization rounds (SR) taken to converge to a desired standard deviation of clocks. More specifically, in our tests we will measure the number of synchronization rounds taken to reach a standard deviation equal to10µsec. It should be noticed that we consider SR as the only convergence time metrics as, once the duration∆T of a synchronization round has been fixed, the time to reach a predefined clock dispersion only depends on the number of synchronizations.
Synchronization Error. The synchronization error (SE) is defined as the minimum stan- dard deviation the algorithm can achieve. This metric will not be considered in the static scenario with symmetric channels, as for symmetric channels the estimation error on clock differences is zero, and thus the synchronization error (see Equation 4). On the other hand this metric will be evaluated in both scenarios which include system pertur- bations: static with asymmetric channels and the dynamic scenario.
Stability. Once all clocks converge to some value, the stability metric measures how much these clocks are sensitive to the injection of new nodes. A perfectly stable al- gorithm should not allow these clocks to significantly change the convergency value already reached.
Simulation Scenarios Below are described the scenarios in which the metrics, defined above, will be evaluated. These scenarios were defined so to isolate aspects relevant to the metrics under exam.
Static with Symmetric Channels This scenario corresponds to a system in which the net- work is static (no nodes are added/removed during the simulation) and (1) the network delay is bounded but unknown, (2) communication channels are symmetricδ1= δ2and thus no estimation error occurs, (3) processes execute the algorithm periodically every
∆T time units, but not in a lock step mode. The round-trip time (RTT) is modeled by means of a Gaussian distribution whose mean and standard deviation have been derived, as described in [27] by fitting several round-trip data set measured over the Internet. To be more precise, in this scenario we consider two different kind of channels, slow and fast. Slow channels are characterized by an average round trip delay of180msec, while fast channels are characterized by an average round trip delay of30msec. When gen- erating a communication graph links between nodes are randomly chosen to be of one kind or another.∆T is the third quartile of the slow channels RTT Gaussian distribution.
This model is worth considering as it closely matches the model underlying Equation 3.
Static with Asymmetric Channels. This simulation scenario adds to the previous one communication channel asymmetry. Channel asymmetry defines how the round-trip time is distributed between the two ways of a channel (i.e. given a channel connecting A to B, which is the ratio between the transfer delay of a message from A to B and the delay back from B to A). The asymmetry is modeled by means of a Gaussian distri- bution with mean0.5 (i.e., symmetric channel). The parameters of this distribution are used in order to explore the sensitivity of the algorithm to channel asymmetry, and thus to estimate clock difference errors.
Dynamic with Symmetric Channels. The last scenario considered in our tests takes into account network dynamics, and thus considers the evolution of a network under the continual addition/removal of nodes. In order to characterize only the dependency of the proposed algorithm under dynamics, we ignore the estimation errors on clock differences, thus assuming symmetric channels.
Simulation Parameters Tests have been conducted varying both the number of clocks N , and the coupling factor K. In order to test our approach under different system scales, ranging from very small to very large, we will be considering values of N in the set of {8, 16, . . . , 64K}. To show the dependency with respect to a constant coupling factorK we will consider values in the set {0.1, 0.2, . . . , 1}. Tests aimed at evaluating the adaptive coupling factor will consider the following local coupling fac- torKi behaviour: initiallyKi assumes the1 value, then it undergoes an exponential decay up to the point it reaches the 0.1 value. Specific tests aimed at evaluating the dependency of the synchronization error on channel asymmetry have been conducted varying the amount of asymmetry, either using a fixed value in the set{0.1, . . . , 0.5}, or varying the variance of the Gaussian distribution used to model it within the set {10−3, . . . , 10−11, 0}. Tests for the dynamic symmetric scenario have been conducted varying either the size of the stable core, i.e. the amount of nodes that remain in the system from the beginning to the end of the test, or the amount of replaced nodes for a single time unit. In all our tests we assume that the initial value assumed by a clock, referred asX0, is a uniform random number in the interval[0, 60] sec.
3.2 Static Scenario with Symmetric Channels Results
Assuming as a deployment scenario a static network with symmetric communication channels, we show how the convergence time, of the proposed algorithm, depends on the scaleN , and on the coupling factor K–the case of K adaptive is also considered.
Convergence Time Figure 2(a), shows how the synchronization roundsSR depend on the size of the systemN , and on the coupling factor K. As it can be seen from the plot, given a value ofN , there is negative exponential dependence K and SR. This dependence, can roughly be approximated an inverse dependence betweenK and SR, as (see Figure 2(a)) doublingK almost halves SR. On the other hand, if we fix the value ofK we can see how SR grows slightly with N when K ≥ 0.5, while it remains constant, or slightly diminishes with N whenK > 0.5.
0 20 40 60 80 100 120 140
0.9 1 0.7 0.8 0,5 0.6 0.3 0.4 0.1 0.2
64K 16K32K 8K 4K 1K2K 512 256 64128 32 16 8 0
20 40 60 80 100 120 140
SR
Synchronization Round
K
N SR
(a) Static K
0 20 40 60 80 100 120 140
64K 32K 16K 8K 4K 2K 1K 512 256 128 64 32 16 8
SR
N
Synchronization Rounds, K=0.1 Synchronization Rounds, K=1 Synchronization Rounds, K adaptive
(b) Adaptive K
Fig. 2. Convergence dependency on N and K.
Figure 2(b) compares the effect ofK adaptive on the convergence time. To this end, it shows the dependence ofSR on the network size for K = 1, K = 0.1 and K adaptive. From this plot it is easy to see how K adaptive provides a performance improvement with respect to the convergence time that is close to that of K = 1, while, as shown later in the paper, retaining error mitigation properties similar to that ofK = 0.1 (see Equation 4).
Synchronization Error As the communication channels are symmetric, and thus the neighboring clock estimate is perfect, the synchronization error will tend to zero as a negative exponential (this comes from Equation 2).
Scalability Most distributed algorithms tend to degrade their performance as the scale of the systems grows, when this happens, the scale of a system can practically exclude certain algorithmic solutions. Thus, it is extremely important to characterize what hap-
pens to a distributed algorithm as the number of nodes involved in the computation grows. To this end Figure 2(a) and Figure 2(b) show how the synchronization rounds SR change over a very wide set of network sizes. Contrarily to many existing clock synchronization solutions, the proposed algorithm scales extremely well, and in some cases, namely forK > 0.5, its performance slightly improve with N . This is a very im- portant property which makes this solution appealing for applications that need to scale to a very large number of nodes. While the behaviour might seem counter-intuitive at first, it has a simple explanation. As the scale of the system grows, so does the average rank of a node, i.e., number of links, with the result that its random sample of neighbors has an increasingly higher probability of being closer to the system clock average, thus reducing the number of rounds taken to converge.
3.3 Static Scenario with Asymmetric Channels Results
Assuming as a deployment scenario a static network with asymmetric communica- tion channels, we investigate how the asymmetry impacts on the synchronization er- ror within which clocks synchronize. For this scenario we won’t show results for the convergence time as these are analogous to what is described in the previous Section.
0 0.05 0.1 0.15 0.2 0.25 0.3 0.35 0.4
0.1 0.15 0.2 0.25 0.3 0.35 0.4 0.45 0.5
SE (sec)
Asymmetry
Synch. std, K=0.1 Synch std, K=1
Fig. 3. Synchronization error varying channel asymmetry.
Synchronization Error Figure 3 reports results obtained using a fixed value of asymme- try for all communication channels. The system sizeN is fixed to 64K for this plot. As the plot shows there is (1) a linear dependency between the channel asymmetry and the synchronization error, and (2) the value ofK, as predicted by the Equation 4 behaves as scaling factor on the synchronization error. The results obtained with the use ofK adap- tive, are not shown as completely overlap with those found forK = 0.1. This should come at no surprise as theK after a transitory assumes definitively the value 0.1–the only relevant difference is that, as shown in Figure2(b), the use ofK adaptive leads to
0 1 2 3 4 5 6
32K 64K 8K 16K 2K 4K 512 1K 128 256 32 64 0 10E-11 10E-10 10E-9 10E-8 10E-7 10E-6 10E-5 10E-4 10E-3
0 1 2 3 4 5 6
SE (sec) Slow Channel Synch. Error
N Variance
SE (sec)
(a) Slow Channels
0 1 2 3 4 5 6
32K 64K 8K 16K 2K 4K 512 1K 128 256 32 64 0 10E-11 10E-10 10E-9 10E-8 10E-7 10E-6 10E-5 10E-4 10E-3
0 1 2 3 4 5 6
SE (sec) Fast Channel Synch. Error
N Variance
SE (sec)
(b) Fast Channels
Fig. 4. Synchronization error for slow and fast Channels with a Gaussian asymmetry distribution.
shorter convergence times. The specific scenario used for the previous plot is far from being realistic, as it assumes a fixed value for asymmetry. Thus, to better model realis- tic channel asymmetry, we used a Gaussian distribution with mean0.5 and studied how systems with variable sizes behave with respect to synchronization error, varying the variance of the distribution. Results for slow and fast channels are reported respectively in Figures 4(a) and 4(b), where the clock standard deviation (expressed in seconds) is reported. As the graphs show, the more channels are “symmetric”, i.e., the more the asymmetry variance is low, the lower is the synchronization error with a clear exponen- tial dependency. It is interesting to point out that the error difference between slow and fast channels quickly becomes negligible as soon as we consider fairly symmetric chan- nels. These plots therefore confirm that the impact of RTT on synchronization error is not straight, but it strongly depends on channel asymmetry.
3.4 Dynamic Scenario with Symmetric Channels Results
Assuming as a deployment scenario a dynamic network with symmetric communica- tion channels, we investigate how the dynamicity impacts on the synchronization error within which clocks synchronize, as well as on the stability of the clock value.
0 0.05 0.1 0.15 0.2 0.25 0.3 0.35 0.4
75 50
25 10
5 1
SE (sec)
Stable Core %
Synch. Error under churn with K=1.0 Synch. Error under churn with K=0.1 Synch. Error under churn with K adaptive
(a) Synchronization error dependency on core network size and K value.
0 5 10 15 20 25 30
50 25
10 5
Clock Avg. Variation (sec)
New Nodes %
Clock variation under churn with K=1.0 Clock variation under churn with K adaptive
(b) Stability versus the number of new injected nodes and K value.
Fig. 5. System behavior under dynamics.
Synchronization Error First we evaluated the resilience of our solution with respect to a continuous addition/removal of nodes. In this test we built a system with64K nodes and considered a fixed core made up of nodes that remain in the system for the whole simulation. Dynamics is modeled substituting 1% of the system at each time unit. Then we evaluated how standard deviation of clocks residing in these nodes varies when the
remaining part of the system keeps changing. The evaluation was done for two extreme values of the coupling factorK (i.e. K = 0.1 and K = 1), and also using an adaptive K value. Curves reported in Figure 5(a) show that the core size has a relevant impact on synchronization error as long as we consider a fixedK value. Intuitively, the larger is the core, the less nodes pertaining to it are prone to change their clock due to reads done on newly joined nodes. In this case, by adopting a small value for the coupling factor, nodes belonging to the fixed core are more resilient to node dynamics. More interesting is the behavior of the system when we adopt the adaptiveK strategy. In this case, new nodes enter the system using a largeK value and therefore rapidly absorb timing information from nodes in the core, while these are slightly perturbed.
Stability Figure 5(b) shows the stability of the system to a perturbation caused by the injection of a huge number of new nodes. In order to better show this behavior we introduced during the simulation in a network made up of 64K nodes, all with clocks synchronized on a specific value, a set of new nodes (expressed in the graph as a percentage of the original network size). Newly injected nodes start with a clock value that is distant 60 seconds from the synchronization value of nodes in the original system. The plot shows how the synchronization value varies from the original one (the distance between the synchronization values is reported in seconds on they axis) when the new network converges again. If we assumeK = 1 the system is prone to huge synchronization value variation, that, intuitively, is larger if a larger number of nodes is injected. However, the introduction of K adaptive mechanism drastically reduces this undesired behavior, limiting the variation of synchronization value, even when the amount of nodes injected is close to 50% of the original system.
These results justify the introduction of an age-based adaptive mechanism for the coupling factor value tuning as an effective solution to improve the stability of systems in face of dynamism.
4 Related Work
We can divide clock synchronization algorithms in two main classes: deterministic and probabilistic. Deterministic clock synchronization algorithms [9,12,13,14,15,18,19,20]
guarantee strict properties on the accuracy of the synchronization but assumes that a known bound on message transfer delays exists. Lamport in [12] defines a distributed algorithm for synchronizing a system of logical clocks which can be used to totally order events, specializes this algorithm to synchronize physical clocks, and derives a bound on how far out of synchrony the clocks can become. Following works of Lamport and Melliar-Smith analyze the problem of clock synchronization in presence of faults, defining Byzantine clock synchronization [13,14]. Some deterministic solutions, such as those proposed in [7,8,14,17], prove that, when up to F reference time servers can suffer arbitrary failures, at least 2F+1 reference time servers are necessary for achiev- ing clock synchronization. In this case, these solutions can be fault-tolerant also for Byzantine faults. Currently, we do not analyze byzantine-tolerant behavior of our solu- tion. The deterministic approach, normally tuned to cope with the worst case scenario, assures a bounded accuracy in LAN environments but loses its significance in WAN
environments where messages can suffer high and unpredictable variations in trans- mission delays. Several works of Dolev et al. [7,8,9,10] propose and analyze several decentralized synchronization protocols applicable for WAN but that require a clique- based interconnecting topology, which is hardly scalable with a large number of nodes.
Clock synchronization algorithms based on a probabilistic approach were proposed in [11,22]. The basic idea is to follow a master-slave pattern and synchronize clocks in the presence of unbounded communication delays by using a probabilistic remote clock reading procedure. Each node makes several attempts to read a remote clock and, after each attempt, calculates the maximum error. By retrying often enough, a node can read the other clock to any required precision with a probability as close to 1 as desired. This implies that the overhead imposed by the synchronization algorithm and the probability of loss of synchronization increases when the synchronization error is reduced. The master-slave approach and the execution of several attempts are basic building blocks of the most popular clock synchronization protocol for WAN settings: NTP [23,24].
NTP works in a static and manually-configured hierarchical topology. In this hierarchy, the primary time servers are directly connected to an external reference time source (GPS, atomic clock, etc.) and are the roots of the spanning tree used to diffuse clock values. Secondary time servers are represented by inner nodes in the hierarchy, and they synchronize their clock communicating with one or more primary time servers.
Clients of the system resides in the hierarchy leaves. NTP requires complex analysis on samples, support from kernel and a controlled network between primary and secondary servers. A work proposing solutions close to NTP is CesiumSpray [25] that is based on a hierarchy composed by a WAN of LANs where in each LAN at least a node has a GPS receiver. This node acts as leader and “sprays” inside the local network its clock. These solutions require static configuration and the presence of some nodes directly connected with a external time reference in order to obtain external time synchronization.
A probabilistic solution based on a gossip-based protocol to achieve external clock synchronization is proposed in [16]. The presence of a source node perfectly synchro- nized with real-time clock is assumed. Each node uses a peer sampling service to select another node in the network and to exchange timing information with. If the time read from the contacted node is of higher quality than its own time (e.g. the contacted node is the source), then the reading node will adopt the clock setting of the other one. The quality of timing information is evaluated using a dispersion metric like the one pro- vided by NTP.
5 Concluding Remarks
Clock synchronization for distributed systems is a fundamental problem that has been widely treated in the literature. Today’s large scale distributed applications, deployed on WANs like Internet, pose new issues that are hardly addressed by existing solutions.
These systems thus require the development of new approaches able to reach satisfying level of synchronization while providing the desired level of scalability.
In this paper we proposed a novel algorithm for clock synchronization in large scale dynamic systems in absence of external clock sources. Our algorithm stems from the work on coupled oscillators developed by Kuramoto [3], adequately adapted to our
purposes. Through theoretical analysis backed up by an experimental study based on simulations we showed that our solution is able to converge and synchronize clocks in systems ranging from very small to very large sizes, achieving small synchronization errors that strictly depend on the quality of links used for communication (with respect to delay and symmetry). Our solution, thanks to the employment of an adaptable cou- pling factor, is also shown to be resilient to network dynamics, i.e. to the continuous arrival and departure of nodes in the system.
The approach to clock synchronization presented in this paper showed interesting properties, but is nevertheless susceptible to further improvements. There are mainly four points we plan to address in the next future. The K adaptive strategy employed in the current proposal (based on an exponentially decaying value) is only one of various possible solutions; we therefore plan to further investigate this aspect to, possibly, iden- tify the best strategy to adaptK at run-time. Moreover, the adaptive mechanism could also be applied to ∆T : the basic idea is that stable nodes, whose clocks have possi- bly converged to a stable value, should “delay” further synchronization adopting larger values for∆T . System adaptiveness can be also pushed one more step ahead, trying to rearrange node links in the interconnecting application-level network to favor neighbors connected to links that are more symmetric and that will therefore induce lower errors in clock readings. Finally, we plan to quickly implement a prototypical version of our algorithm to move our tests to the realistic testbed offered by PlanetLab. To this end, initial empirical evaluations [28] performed in our labs on a mid sized LAN confirm what predicted by the simulation presented in this paper.
References
1. Object Management Group. Data distribution service for real-time systems specication v1.2, ptc/2006-04-09.
2. A.T. Winfree. J. Theoret. Biol. 16 (1967) 15.
3. Y. Kuramoto. Chemical oscillations, waves and turbulence. Chap. 5. Springer-Verlag, Berlin, 1984.
4. S.H. Strogatz and R.E. Mirollo. Phase-locking and critical phenomena in lattices of coupled nonlinear oscillators with random intrinsic frequencies, Physica D, vol. 31, pp. 143-168, 1988.
5. K. Satoh. Computer Experiment on the Cooperative Behavior of a Network of Interacting Nonlinear Oscillators, J. Phys. Soc. Jpn. 58, 2010 (1989).
6. P.C. Matthews, R. E. Mirollo and S. H. Strogatz. Dynamics of a large system of coupled nonlinear oscillators. Physica D 52. p. 293. 1991.
7. A. Daliot, D. Dolev and H. Parnas. Linear Time Byzantine Self-Stabilizing Clock Synchro- nization, Technical Report TR2003-89, Schools of Engineering and Computer Science, The Hebrew University of Jerusalem, Dec. 2003
8. A. Daliot, D. Dolev, H. Parnas. Self-Stabilizing Pulse Synchronization Inspired by Biological Pacemaker Networks, Proc. Of the Sixth Symposium on Self-Stabilizing Systems, pp. 32-48, 2003
9. S. Dolev. Possible and Impossible Self-Stabilizing Digital Clock Synchronization in General Graph, Journal of Real-Time Systems, no. 12(1), pp. 95-107, 1997
10. T. Herman and S. Ghosh. Stabilizing Phase-Clock. Information Processing Letters, 5(6):585- 598, 1994
11. F. Cristian. A probabilistic approach to distributed clock synchronization. Distributed Com- puting, 3:146158, 1989.
12. L. Lamport. Time, clocks and ordering of events in a distributed system. Commun ACM, vol 21, no. 7, pp. 558-565, 1978
13. L. Lamport and P. M. Melliar-Smith. Byzantine clock synchronization. Proc. 3rd Ann. ACM Symp. Principles of Distributed Computing, 1984, pp. 68-74
14. L. Lamport and P. M. Melliar-Smith. Synchronizing clocks in the presence of faults. Journal of the ACM, 32(1):525278, Jan 1985.
15. J. Lundelius-Welch and N. Lynch. A new fault-tolerant algorithm for clock synchronization.
Proc. 3rd Ann. ACM Symp. Principles of Distrib. Computing, 1984, pp. 75-88
16. K. Iwanicki, M. van Steen and S. Voulgaris. Gossip-based Synchronization for Large Scale Decentralized Systems. 2006
17. F. Cristian and C. Fetzer. Integrating Internal and External Clock Synchronization, Journal of Real Time Systems, Vol. 12, No. 2, March, 1997
18. F. Cristian and C. Fetzer. Lower bounds for convergence function based clock synchroniza- tion. Proceedings of the fourteenth annual ACM symposium on Principles of distributed computing, p.137-143, August 20-23, 1995
19. F. Cristian, H. Aghili and R. Strong. Clock synchronization in the presence of omission and performance faults, and processor joins, Proc. Int. Conf. Fault-Tolerant Computing, pp. 218- 223,1986
20. J. Halpern, B. Simons and R. Strong. Fault-tolerant clock synchronization, Proc. 3rd Ann.
ACM Symp. Principles of Distrib. Computing, pp. 89-102, 1984
21. H. Kopetz and W. Ochsenreiter. Clock synchronization in distributed real-time systems, IEE Trans. Comput., vol. 36, no. 8, pp. 933-940, Aug. 1987
22. K. Arvind. Probabilistic Clock Synchronization in Distributed Systems, IEEE Trans. on Par- allel and Distrib. Systems, vol. 5, no. 5, May 1994
23. D. L. Mills. Network Time Protocol (Version 1) specification and implementation. Network Working Group Report RFC-1059. University of Delaware, July 1988
24. D. L. Mills. Network Time Protocol Version 4 Reference and Implementation Guide. Elec- trical and Computer Engineering Technical Report 06-06-1, University of Delaware, June 2006, 83 pp
25. P. Verissimo, L. Rodrigues and A. Casimiro. CesiumSpray: a Precise and Accurate Global Time Service for Large-scale Systems, Journal of Real-Time Systems, Vol. 12, No. 3, pp.
243-294, May 1997
26. M. Jelasity, R. Guerraoui, A.-M. Kermarrec, M. van Steen. The peer sampling service: ex- perimental evaluation of unstructured gossip-based implementations, Proceedings of the 5th ACM/IFIP/USENIX international conference on Middleware, 2004.
27. R. Baldoni, C. Marchetti, A. Virgillito. Impact of WAN Channel Behavior on End-to-end Latency of Replication Protocols, In Proceedings of European Dependable Computing Con- ference, 2006.
28. R. Baldoni, A. Corsaro, L. Querzoni, S. Scipioni, S. Tucci-Piergiovanni, An Adaptive Coupling-Based Algorithm for Internal Clock Synchronization of Large Scale Dynamic Sys- tems, MidLab Technical Report, 02/07,http://www.dis.uniroma1.it/˜midlab.
