Cybernetics and Information Technologies
Volume 2, No 2. Sofia, 2002, Bulgarian Academy of Sciences

Clock Synchronization with Independent Adjustment in Distributed Systems

Krassimir Djambazov, Edita Djambazova

Institute of Computer and Communication Systems, 1113 Sofia

The clock synchronization algorithm with independent adjustment is presented. It uses the cyclic nature of the TDMA strategy for continuous collection of time differences among the nodes' clocks and applies an independent adjustment. Nodes decide locally when to apply the adjustment. The correction term is calculated as in the fault-tolerant algorithms and is applied not periodically but upon exceeding one phase bit. Two variants for algorithms implementation are presented - fixed-point and checked adjustment.
A classification of the clock synchronization algorithms is presented. Two main groups of algorithms are distinguished: with direct and with interactive synchronization. The fault tolerance support, referred to as convergent and consistent, is introduced as an upgrade of the basic algorithms. The proposed validity measure, local time rate of change, is used along with the skew distribution to estimate the influence of the failures and of the fault tolerance of the clock synchronization algorithms.
The algorithm is compared with other clock synchronization algorithms for distributed hard real-time control systems. A simulation model of clock synchronization algorithms that includes failure injection properties is used. The reported results from the experiments with the simulator program give a base to make the conclusion that the proposed algorithm for clock synchronization with independent adjustment tolerates input omission, output omission, and bad clock failures to the same extent as the Fault-Tolerant Average algorithm.

Key words: fault tolerance, clock synchronization, distributed systems, hard real time.