RR-3526 : Performance Evaluation of Clock Synchronization Algorithms

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 synchroni- zation 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.

Résumé : Les algorithmes de synchronisation d'horloges offrent une notion commune du temps à des processeurs n'ayant pas accès à une horloge globale partagée. Ce rapport propose un état de l'art des algorithmes de synchronisation d'horloges implantés par logiciel, qu'ils soient déterministes, probabilistes ou statistiques, qu'ils assurent une synchronisation interne ou externe, et qu'ils soient résilients aux défaillances par arrêt, par omission ou Byzantines. Cet état de l'art repose sur une classification de ces algorithmes et sur une évaluation de leur performance effectuée à partir de cette classification. Cette évaluation de performance est obtenue par simulation d'une sélection d'algorithmes de synchronisation d'horloges (LL88, ST87, PB95, GZ89). Le comportement de ces algorithmes est analysé en présence de différents types de fautes (arrêt, omission, performance, Byzantines), à la fois lorsque le nombre et le type des fautes générées lors de l'évaluatio- n respectent les hypothèses faites par les algorithmes et également lorsque ces hypothèses sont violées. Cet état de l'art est destiné à guider le concepteur d'un algorithme de synchronisation d'horloges dans le choix de la technique la mieux adaptée à son architecture matérielle, le modèle de défaillances visé, la qualité de la synchronisation obtenue ainsi que le coût résultant en terme de nombre de messages échangés.

RR-3526 - Performance Evaluation of Clock Synchronization Algorithms