Clock synchronization in fault-tolerant systems
M.J. Pfluegl · 1992
Synchronous clocks are an essential requirement for a variety of distributed computer systems. Many of their system applications are safety-critical, and the systems including their clock synchronization algorithms must be capable of tolerating faults. In this dissertation, faulty behavior affecting clock synchronization is studied, and a fault categorization is established. Based on this categorization, a comprehensive general probabilistic clock synchronization model is developed. This model is uniformly probabilistic, incorporating random message transmission times, random clock drifts, and random fault occurrences. The model is completely general in that faults can occur in any system component and can be of any type (transient, intermittent, or permanent). Byzantine faults are considered as well. A new clock synchronization algorithm (SWA) is presented. It offers two significant advantages. First, it can tolerate considerably higher percentages of faults than any known algorithm. In addition, it achieves clock synchronization tightness that is tighter than or as tight as that of other algorithms. Our model is ideally suited for a probabilistic evaluation and comparison of a wide range of clock synchronization algorithms in a variety of environments. A discrete-event-simulation-based software package was designed according to the model for a quantitative evaluation and comparison of SWA. It shows that the Sliding Window Algorithm is capable of tolerating more than 50 percent of the nodes being faulty at any time and short fault bursts that affect all nodes. The evaluation also shows that it can synchronize up to 38 percent tighter than other algorithms. SWA is also studied under static worst-case assumptions for both completely and not-completely connected networks. Proof is given that the Sliding Window Algorithm can guarantee clock synchronization in either environment if a fourth or less of all nodes are maliciously faulty. The worst-case analysis includes theorems on the best achievable clock synchronization tightness and the optimal choice of the window size. For not-completely connected networks a communication protocol is presented that utilizes SWA to achieve tight clock synchronization efficiently in a system with n nodes and a communication cost that is nearly on the order of $n\sp2$ messages.