Performance Evaluation of Clock Synchronization Algorithms

Emmanuelle Anceaume 1 Isabelle Puaut 1
1 SOLIDOR - Design of Distributed Operating Systems
IRISA - Institut de Recherche en Informatique et Systèmes Aléatoires, INRIA Rennes
Abstract : Clock synchronization algorithms ensure that physically dispersed processors have a common knowledge of time. This report proposes a survey of software fault-tolerant clock synchronization algorithms: deterministic, probabilistic and statistical ; internal and external ; and resilient from crash to Byzantine failures. Our survey is based on a classification of clock synchronization algorithms (according to their internal structure and to three orthogonal and independent basic building blocks we have identified), and on a performance evaluation of algorithms constructed from these building blocks. The performance evaluation is achieved through the simulation of a panel of fault-tolerant clock synchronization algorithms (LL88, ST87, PB95, GZ89). The algorithms behavior is analyzed in the presence of various kinds of failures (crash, omission, timing, performance, Byzantine), both when the number and type of failures respect the fault assumptions made by the algorithm and when fault assumptions are exceeded. Our survey will help the designer in choosing the most appropriate structure of algorithm and the best building blocks suited to his/her hardware architecture, failure model, quality of synchronized clocks and message cost induced. Moreover, our classification uses a uniform notation that allows to compare existing clock synchronization algorithms with respect to their fault model, the building blocks they use, the properties they ensure and their cost in terms of message exchanges.
Type de document :
[Research Report] RR-3526, INRIA. 1998
Liste complète des métadonnées
Contributeur : Rapport de Recherche Inria <>
Soumis le : mercredi 24 mai 2006 - 12:01:26
Dernière modification le : mercredi 16 mai 2018 - 11:23:05
Document(s) archivé(s) le : dimanche 4 avril 2010 - 23:36:16



  • HAL Id : inria-00073159, version 1


Emmanuelle Anceaume, Isabelle Puaut. Performance Evaluation of Clock Synchronization Algorithms. [Research Report] RR-3526, INRIA. 1998. 〈inria-00073159〉



Consultations de la notice


Téléchargements de fichiers