Name
Title | ||
|---|---|---|
Coupling-Based Internal Clock Synchronization for Large-Scale Dynamic Distributed Systems |
Abstract | ||
|---|---|---|
This paper studies the problem of realizing a common software clock among a large set of nodes without an external time reference (i.e., internal clock synchronization), any centralized control, and where nodes can join and leave the distributed system at their will. The paper proposes an internal clock synchronization algorithm which combines the gossip-based paradigm with a nature-inspired approach, coming from the coupled oscillators phenomenon, to cope with scale and churn. The algorithm works on the top of an overlay network and uses a uniform peer sampling service to fulfill each node's local view. Therefore, differently from clock synchronization protocols for small scale and static distributed systems, here, each node synchronizes regularly with only the neighbors in its local view and not with the whole system. An evaluation of the convergence speed and the synchronization error of the coupled-based internal clock synchronization algorithm has been carried out, showing how convergence time and the synchronization error depends on the coupling factor and the local view size. Moreover, the variation of the synchronization error with respect to churn and the impact of a sudden variation of the number of nodes have been analyzed to show the stability of the algorithm. In all these contexts, the algorithm shows nice performance and very good self-organizing properties. Finally, we showed how the assumption on the existence of a uniform peer-sampling service is instrumental for the good behavior of the algorithm and how, in system models where network delays are unbounded, a mean-based convergence function reaches a lower synchronization error than median-based convergence functions exploiting the number of averaged clock values. |
Year | DOI | Venue |
|---|---|---|
2010 | 10.1109/TPDS.2009.111 | IEEE Trans. Parallel Distrib. Syst. |
Keywords | Field | DocType |
common software clock,overlay networks.,coupled-based internal clock synchronization,internal clock synchronization,peer sampling,clock synchronization protocol,index terms peer-to-peer,local view,internal clock synchronization algorithm,coupling-based internal clock synchronization,large-scale dynamic,synchronization error,algorithm work,lower synchronization error,clock value,self organization,convergence,indexing terms,couplings,overlay networks,clock synchronization,protocols,algorithm design and analysis,distributed system,overlay network,distributed processing,synchronisation,sampling methods,oscillators,synchronization | Vector clock,Synchronization,Algorithm design,Computer science,Data synchronization,Real-time computing,Clock synchronization,Synchronization (computer science),Overlay network,Distributed computing,Self-clocking signal | Journal |
Volume | Issue | ISSN |
21 | 5 | 1045-9219 |
Citations | PageRank | References |
12 | 0.58 | 34 |
Authors | ||
5 | ||
Name | Order | Citations | PageRank |
|---|---|---|---|
| Roberto Baldoni | 1 | 1606 | 132.37 |
| Angelo Corsaro | 2 | 26 | 1.65 |
| Leonardo Querzoni | 3 | 433 | 33.18 |
| Sirio Scipioni | 4 | 29 | 3.41 |
| Sara Tucci Piergiovanni | 5 | 286 | 22.22 |