HAL will be down for maintenance from Friday, June 10 at 4pm through Monday, June 13 at 9am. More information
Skip to Main content Skip to Navigation

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.
Document type :
Complete list of metadata

Contributor : Rapport de Recherche Inria Connect in order to contact the contributor
Submitted on : Wednesday, May 24, 2006 - 12:01:26 PM
Last modification on : Friday, February 4, 2022 - 3:24:37 AM
Long-term archiving on: : Sunday, April 4, 2010 - 11:36:16 PM


  • HAL Id : inria-00073159, version 1


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



Record views


Files downloads