inria-00264219, version 1
Clock Synchronization in the Byzantine-Recovery Failure Model
Emmanuelle Anceaume
a, 1Carole Delporte-Gallet
a, 2Hugues Fauconnier a, 2Michel Hurfin b, 1Josef Widder c, 3
OPODIS (2007)
Résumé : We consider the problem of synchronizing clocks in synchronous systems prone to transient and dynamic process failures, i.e., we consider systems where all processes may alternate correct and Byzantine behaviors. We propose a clock synchronization algorithm based on periodical resynchronizations which is based on the assumption that no more than f < n/3 processes (with n the number of processors in the system) are simultaneously faulty. Both, accuracy (clocks being within a linear envelope of real-time) and precision (maximum deviation between clocks) perpetually hold for processes which sufficiently long follow their algorithm. We provide expressions for both the recovery time and the failure turn-over rates. Both expressions are independent of f, and are less than the time needed to execute 3 resynchronizations.
- a – CNRS
- b – INRIA
- c – Technische Universitat Wien, Vienna (Austria)
- 1 : ADEPT (INRIA - IRISA)
- CNRS : UMR6074 – INRIA – Université de Rennes 1
- 2 : Laboratoire d'informatique Algorithmique : Fondements et Applications (LIAFA)
- CNRS : UMR7089 – Université Paris VII - Paris Diderot
- 3 : Institut für Diskrete Mathematik und Geometrie
- Technische Universität Wien
- Domaine : Informatique/Calcul parallèle, distribué et partagé
- inria-00264219, version 1
- http://hal.inria.fr/inria-00264219
- oai:hal.inria.fr:inria-00264219
- Contributeur : Emmanuelle Anceaume
- Soumis le : Vendredi 14 Mars 2008, 15:31:06
- Dernière modification le : Vendredi 14 Mars 2008, 15:32:48






Documents associés
Exporter