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 Advanced Studies
Air Traffic Management and Airport Systems, SELEX-SI Rome, Italy
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 convergence and stability under different network settings.
1 Introduction
Clock synchronization is a fundamental building block for many distributed applications. 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 the 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 of clock synchronization is far from being solved. These applications are required to (1) operate without any assumption on deployed functionalities, preexisting 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 distribution service [1]
requires synchronized clocks, however in several relevant scenarios, 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 decentralized paradigm in which peers implement all the required functionalities, by running so calledgossip − based algorithms. In this approach, due to the large scale and geography 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 computes 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 solve the 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. Biological examples include network pacemaker cells in the hearth, congregations of synchronously flashing fireflies and crickets that chirp in unison. A description of the phenomenon was pioneered by Winfree [2]. He mathematically 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 oscillators has to interactions with others), a dramatic transition to a globally entrained state, in which oscillators freeze into synchrony, occurs. A valuable contribution has been subsequently done by Kuramoto [3] who
simplified the Winfree model by considering the coupling strength constant for all oscillators 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 others, which means assuming a fully connected oscillators network. However a considerable 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 oscillators 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 synchronize 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 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 for neighboring clock values in order to calculate their differ- ence in phase. Then, following our Kuramoto-like model, these differences in phase are combined and multiplied by a so-called coupling factor, expressessing the coupling strength, in order to adjust the clock. As the coupling factor has a key role in regulating the dynamics of coupling, we study throughoutly 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 (basi- cally deployed on a wired computer network): (1) errors on the phase difference estimates due to network delays and (2) neighborhoods possibly changing over the time. As a general result, low coupling factors lead to better synchro- nization 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 reducing 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 the values from other nodes, while an old node will have a small coupling to limit the sensitivity to system perturbations. The rationale behind this mechanism 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 partic- ularly useful in case of changing neighborhoods. 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 reduced when compared to a constant coupling factor. In other words, the adoption of adaptive coupling leads the system to keep its stability, a property hardly needed in face of network dynamism. The paper is organized as follows: Section 2 presents the clock coupling model along with the algorithm. The experimental evaluation is presented in Section 3, while Section 4 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 incre- mented at every tick of the oscillator. Depending on the quality of the oscillator, and the operating environment, its frequency will drift. Manufacturers typically provide a characterization forρ – the maximum absolute value for oscil- lator drift. Ignoring, for the time being, the resolution due to limited pulsing frequency of the oscillator, the hardware clock implemented by the oscillator can be described by the Equation 1:
C(t) = f t + C0; (1)
where:(1 − ρ) ≤ f ≤ (1 + ρ) This clock model is assumed by all clock synchronization 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 frequency fiǫ[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 the 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 to precise that Kuramoto modeled a non-linear oscillator coupling which is not directly applicable 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 stable point exists. This leads to consider a linear coupling equation of the form:
C˙i(t) = fi+φi
N XN i=1
(Cj(t) − Ci(t)), j = 1..N (2)
The intuition behind the 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φi provides a measure of how much the current clock rate should be influenced by the 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 communication graph.
Ci(n + 1) = Ci(n) + fi∆T +Ki
Ni Ni
X
i=1
[(Cj(n) − Ci(n)) ∗ edge(i, j)], j = 1..Ni (3)
WhereKi = φif ∆T , Niis the number of neighbors for clockCi, andedge(i, j) is 1 when the underlying communi- cation 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 2.2). Under this assumption, the real offset betweenCiandCjis 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 committed 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 afflicts the(Cj(n) − Ci(n)) estimate:
Ci(n+1) = Ci(n)+fi∆T +Ki
Ni Ni
X
i=1
[(Cj(n)−Ci(n))∗edge(i, j)]+Ki
Ni Ni
X
i=1
[(δi,j− δj,i
2 )∗edge(i, j)], j = 1..N (4) Equation 4 shows howKi < 1 helps reducing the sensitivity of the coupling model on the estimation error. On the
Fig. 1. NTP offset estimation
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 valueCiis 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 byKNi(n)
i .
3. Update the value ofCi, and the value ofKi, in the case in which it is time dependent.
In the following we provide the results of an extensive experimental study which highlights the behaviour, convergence time, synchronization error, and stability, of the proposed 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 Section we will first describe the details of the simulation settings used for our evaluation, and then the final performance results. Appendix A provides a numerical evaluation of Equation 2 along with some initial experimental results on a prototype of the algorithm.
3.1 Simulation settings
The proposed algorithm is evaluated against the metrics and the scenarios described below and summarized in Table 3.1.
Static Symmetric Scenario Static Asymmetric Scenario Dynamic Symmetric Scenario
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.
Evaluation Metrics The metrics used to evaluate the proposed algorithm are its convergence 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
Convergence Time. The convergence time metric is defined as the number of synchronization 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 standard 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 perturbations: 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 algorithm 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 network 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 of 30msec. When generating 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 asym- metry. 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 distribution 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 clocksN , 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 ofN 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 factorKibehaviour: initiallyKiassumes the1 value, then it undergoes an exponential decay up to the point it reaches the0.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. Finally, Equation’s 2 behaviour was analyzed using the Octave’s differential equation solverlsode.
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.
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 32K 8K16K 4K 2K 5121K 256 128 64 1632 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.
Convergence Time Figure 2(a), shows how the synchronization rounds SR depend on the size of the system N , and on the coupling factor K. As it can be seen from the plot, given a value of N , there is negative exponential dependenceK and SR. This dependence, can roughly be approximated an inverse dependence between K and SR, as (see Figure 2(a)) doublingK practically halves SR. On the other hand, if we fix the value of K we can see how SR grows slightly with N when K ≥ 0.5, while remains constant, or slightly diminishes with N when K > 0.5.
Figure 2(b) compares the effect ofK adaptive on the convergence time. To this end, it shows the dependence of SR 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 ofK = 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 happens 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 roundsSR 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 important 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 communication channels, we investigate how the asymmetry impacts on the synchronization error within which clocks synchronize. For this scenario we won’t show results for the convergence time as these are analogous to what described in the previous Section.
Synchronization Error Figure 3.2 reports results obtained using a fixed value of asymmetry 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 adaptive, are not shown as com- pletely overlap with those found forK = 0.1. This should come at no surprise as the K after a transitory assumes definitively the value0.1–the only relevant difference is that, as shown in Figure2(b), the use of K adaptive leads to shorter convergence times. The specific scenario used for the previous plot is far from being realistic, as it assumes a
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.
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.
fixed value for asymmetry. Thus, to better model realistic 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 vari- ance 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 “sym- metric”, i.e., the more the asymmetry variance is low, the lower is the synchronization error with a clear exponential 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 channels. 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 communication 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.
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 adaptiveK value. Curves reported in Figure 5(a) show that the core size has a relevant impact on
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 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 large K 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 of64K 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 ofK 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 [7,9,12,13,14,15,18,19,20,21] guarantee strict properties on the accuracy of the syn- chronization 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 al- gorithm 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 achieving 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 solution. 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 transmission 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 synchronized 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 provided 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 sim- ulations we showed that our solution is able 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 communi- cation (with respect to delay and symmetry). Our solution, thanks to the employment of an adaptable coupling 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, identify 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 possibly 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.
Appendix A
This Appendix provides some results showing (1) how Equation 2 performs ideally, and how its convergence time depends on the structure of the underlying random graph, and (2) how a prototype implementing of the proposed solution performs on a LAN.
5.1 Numerical Evaluation of the Coupling Model over Random Graphs.
In the following we will show the converge property of the Equation 2 over a random graph through a numerical simulation, i.e., by solving numerically the system of differential equations.
Convergence Time In this paragraph we will show how Equation 2 converges on a random graph, and relate this to the case in which the clock inteconnection is a clique. To start with, Figure 6 shows a trace of a simulation involving
C l
o c k T i
m e
( s e c )
0 10 20 30 40 50 60
0 10 20 30 40 50 60
Ti
me (
sec ) 00
.
20 .
40 .
60 .
8
1 00
.
20 .
40 .
60 .
8
1
C 1
C 2
C 3
C 4
C 5
C 6
C 7
C 8
C 9
C 10
C 11
C 12
C 1
3
C 14
C 15
C 1
6
C 17
C 18
C 1
9
C 20
Fig. 6. Convergence Time over a clique.
N = 20 nodes, with K = 20, connected by a clique. The resulting convergence time is Tc = 900msec. It turns out that this is a lower bound in terms of convergence time for any connected topology, meaning that if we start removing links to the clique the convergence time increases. Figure 7, fixedX0, shows how the convergence time is influenced by the underlying random graph. More specifically, Figure 7 was obtained by solving the Equation 2 on 300 different random graph withN = 20 nodes. It is worth noticing that while the convergence time is slightly higher than the clique case, the algorithm still converges practically at the same pace.
Figure 8(a), shows the dependence of the convergence timeTcon the coupling factorK. As it is easy to see from the plot, and from Table 2 there is a linear dependence betweenK and Tc, meaning that doublingK means halving Tc.
Synchronization Error As predicted by the dynamics implied by the Equation 2 the synchronization error tends to zero exponentially.
5.2 Coupled Clock Synchronization on a LAN
In order to validate our approach, we have implemented a C++ prototype of the coupled clock synchronization algo- rithm, which relies only on UDP messages in order to carry on the protocol. Initial experimentation performed on a LAN of interconnected Linux Workstations provided very promising results.
P r o b a b i
l i t
y
0 0
.
00 5 0.0
1 0
.
0 15 0
.
0 2
0 0
.
00 5 0.0
1 0
.
0 15 0
.
0 2
C onvergence
Ti
me (
sec ) 0
.
911
.
11
.
21
.
31
.
41
.
51
. 6 0
.
11
.
11
.
1
.
1
.
41
.
51
.
C onvergence
T i
me PDF
G auss
i
an F
i
t
(a) pdf
P r o b a b i
l i t y
0 0
. 1 0
. 2 0
. 3 0
. 4 0.
5 0
. 6 0
. 7
0 0
. 1 0
. 2 0
. 3 0
. 4 0.
5 0
. 6 0
. 7
T i
me (
sec ) 11
.
11
.
21
.
31
.
41
. 5 .....
C onvergence
Ti
me
C PF
(b) cdf
Fig. 7. Converge Time distribution for fixed initial condition and different random graphs.
C o n v e r g e n c e T i
m e
( s e c )
1 1
K 1 1
0
1 00 1 1
0
1 00
C onvergence
Ti
me
(a) Dependence on K
C o n v e r g e n c e T i
m e
1 .
8 2 2
.
2 2
. 4 2.
6 2
. 8 3
1 . 8 2 2
.
2 2
. 4 2.
6 2
. 8 3
N 020
4
0 6
0 8
0100 020
4
0 6
0 8
0100
C onvergence
Ti
me
(b) Dependence on N Fig. 8. Convergence Time Dependence from K and N.
Convergence Time. Figure 5.2 shows the results obtained by using a coupling factorK = 1, and a ∆T = 1sec, and N = 4. As shown in the Figure, where the X axis represents the real time since the clock was started, and the Y axis represents the time reading of the clock, clocks converge very quickly toward a common value, From the graph it is visible how the convergence time is on the order of 10 seconds., which translates to 10 synchronization cycles.
Comparing this result with Figure 8 we can see how the simulated result and the result measured experimentally are in complete accordance.
Synchronization Error For the case under exham the synchronization error was actually very small, as the network asymmetry was rather limited due to the deployment scenario, i.e., a LAN. More specifically, bu tuning our algorithm we were able to reach synchronization errrors in the order of few microseconds reasonably fast.
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.
K Convergence Time (sec)
1 27.93
2 13.52
4 6.68
8 3.33
16 1.66
32 0.83
64 0.41
128 0.21
Table 2. Convergence Time dependence on N
3e+10 3.5e+10 4e+10 4.5e+10 5e+10 5.5e+10 6e+10
0 2 4 6 8 10 12 14 16 18 20
Clock Time (nsec)
Real-Time (sec) Clock Synchronization
C0 C1 C2 C3
Fig. 9. Convergence Time in a LAN.
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 Synchronization, 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 Computing, 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 synchronization. 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 Parallel 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. Electrical 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 Sys- tems, 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: experimental 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 Conference, 2006.
28. R. Baldoni, A. Corsaro, L. Querzoni, S. Scipioni, S. Tucci-Piergiovanni, An Adaptive Coupling-Based Algorithm for In- ternal Clock Synchronization of Large Scale Dynamic Systems, MidLab Technical Report, 02/07, http://www.dis.
uniroma1.it/∼midlab.
