Abstract: Clock synchronization algorithms ensure that physically dispersed processors have a common knowledge of time. This paper proposes a taxonomy adapted to all published software fault-tolerant clock synchronization algorithms: deterministic and probabilistic, internal and external, and resilient from crash to Byzantine failures. We classify clock synchronization algorithms according to their internal structure and to three othogonal and independent basic building blocks. Our taxonomy 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.

Keywords: Clock synchronization, distributed systems, real-time systems, deterministic, probabilistic.