Take a look at the new version of this page: [ beta version ]. Tell us what you think.

ABSTRACT

Synchronized clocks are usually considered as a prerequisite for many distributed applications. Existing solutions mainly deal with this problem in static environments with well defined characteristics and limits. The needs of an emergent class of large-scale peer-to-peer applications that have to operate without any assumptions on the surrounding environment have recently revitalized this research area with the proposals of new solutions characterized by self-organization capabilities and strong adaptability to dynamic settings.

This paper reports about the properties of a clock synchronization algorithm for large scale applications. The algorithm implements an internal clock synchronization mechanism which combines the gossip-based paradigm with a nature-inspired approach coming from the coupled oscillators phenomenon. Using a theoretical approach, the paper focuses on the convergence properties of the algorithm, characterizing its synchronization speed (decay factor) the final synchronization point and error.

REFERENCES

• 1: K. Arvind, Probabilistic Clock Synchronization in Distributed Systems, IEEE Transactions on Parallel and Distributed Systems, v.5 n.5, p.474-487, May 1994 [doi>10.1109/71.282558]
• 2: R. Baldoni, A. Corsaro, L. Querzoni, S. Scipioni, and S. Tucci-Piergiovanni. An adaptive coupling-based algorithm for internal clock synchronization of large scale dynamic systems. In OTM Conferences, pages 701--716, 2007.
• 3: Roberto Baldoni , Carlo Marchetti , Antonino Virgillito, Impact ofWAN Channel Behavior on End-to-end Latency of Replication Protocols, Proceedings of the Sixth European Dependable Computing Conference, p.109-118, October 18-20, 2006 [doi>10.1109/EDCC.2006.13]
• 4: F. Cristian. A probabilistic approach to distributed clock synchronization, chapter 3, pages 146--158. Distributed Computing. 1989.
• 5: F. Cristian, H. Aghili, and R. Strong. Clock synchronization in the presence of omission and performance faults, and processor joins. In Proceedings of the Int. Conf. Fault-Tolerant Computing, pages 218--223, 1986.
• 6: Christof Fetzer , Flaviu Cristian, 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, Ottowa, Ontario, Canada [doi>10.1145/224964.224980]
• 7: A. Daliot, D. Dolev, and H. Parnas. Linear time byzantine self-stabilizing clock synchronization. Technical Report TR2003-89, The Hebrew University of Jerusalem, 2003.
• 8: A. Daliot, D. Dolev, and H. Parnas. Self-stabilizing pulse synchronization inspired by biological pacemaker networks. In Proceedings of the Sixth Symposium on Self-Stabilizing Systems, pages 32--48, 2003.
• 9: Shlomi Dolev, Possible and Impossible Self-Stabilizing Digital ClockSynchronization in General Graphs, Real-Time Systems, v.12 n.1, p.95-107, Jan. 1997 [doi>10.1023/A:1007914216733]
• 10: Joseph Y. Halpern , Barbara Simons , Ray Strong , Danny Dolev, Fault-tolerant clock synchronization, Proceedings of the third annual ACM symposium on Principles of distributed computing, p.89-102, August 27-29, 1984, Vancouver, British Columbia, Canada [doi>10.1145/800222.806739]
• 11: Ted Herman , Sukumar Ghosh, Stabilizing phase-clocks, Information Processing Letters, v.54 n.5, p.259-265, June 9, 1995 [doi>10.1016/0020-0190(95)00050-M]
• 12: K. Iwanicki, M. van Steen, and S. Voulgaris. Gossip-based synchronization for large scale decentralized systems. In Proceedings of the Second IEEE International Workshop on Self-Managed Networks, Systems and Services, 2006.
• 13: Márk Jelasity , Rachid Guerraoui , Anne-Marie Kermarrec , Maarten van Steen, The peer sampling service: experimental evaluation of unstructured gossip-based implementations, Proceedings of the 5th ACM/IFIP/USENIX international conference on Middleware, October 18-22, 2004, Toronto, Canada
• 14: Leslie Lamport, Time, clocks, and the ordering of events in a distributed system, Communications of the ACM, v.21 n.7, p.558-565, July 1978 [doi>10.1145/359545.359563]
• 15: Leslie Lamport , P. M. Melliar-Smith, Byzantine clock synchronization, Proceedings of the third annual ACM symposium on Principles of distributed computing, p.68-74, August 27-29, 1984, Vancouver, British Columbia, Canada [doi>10.1145/800222.806737]
• 16: Leslie Lamport , P. M. Melliar-Smith, Synchronizing clocks in the presence of faults, Journal of the ACM (JACM), v.32 n.1, p.52-78, Jan. 1985 [doi>10.1145/2455.2457]
• 17: Jennifer Lundelius , Nancy Lynch, A new fault-tolerant algorithm for clock synchronization, Proceedings of the third annual ACM symposium on Principles of distributed computing, p.75-88, August 27-29, 1984, Vancouver, British Columbia, Canada [doi>10.1145/800222.806738]
• 18: Hicham Marouani , Michel R. Dagenais, Internal clock drift estimation in computer clusters, Journal of Computer Systems, Networks, and Communications, v.2008 n.2, p.1-7, February 2008 [doi>10.1155/2008/583162]
• 19: D. L. Mills, Network Time Protocol (version 1) specification and implementation, RFC Editor, 1988
• 20: D. Mills. Network time protocol version 4 reference and implementation guide. Electrical and Computer Engineering Technical Report 06-06-1, June 2006.

INDEX TERMS

Primary Classification:
  C. Computer Systems Organization
  C.2 COMPUTER-COMMUNICATION NETWORKS
      C.2.4 Distributed Systems

Additional Classification:
  D. Software
  D.2 SOFTWARE ENGINEERING
      D.2.8 Metrics
          Subjects: Performance measures

  G. Mathematics of Computing
  G.3 PROBABILITY AND STATISTICS

General Terms:
Algorithms, Performance, Theory

Keywords:
internal clock synchronization, peer-to-peer systems, theoretical analysis