Self Synchronizing Clocks for Real Time Systems

Abstract

The two functions achieved by clock synchronization algorithms are clock precision and clock accuracy. The former keeps the drift between any two clocks in a given set of clocks within defined limits; the latter maintains the drift between a given clock and a reference clock within defined limits. While distributed non real-time systems need only clock precision for their correct operation, clock accuracy is an absolute must for distributed real-time systems. Many of the existing software-based clock synchronization algorithms implement only clock precision, treating clock accuracy as a secondary problem, often solved at a high cost. As modern distributed real-time systems are emerging more and more, it becomes necessary to devise an approach that deals with the precision and accuracy issues equally and in an integrated way. The work presented in this paper consisted in the design and implementation of a software-based clock synchronization algorithm, which achieves at the same time clock accuracy and clock precision. The proposed algorithm is built upon a new mechanism, referred to as self synchronization, through which a clock can continuously synchronize itself relative to a reference clock, independently of the others and with minimal message exchange. An important aspect of this mechanism is to permit the implementation of a very low cost, fault-tolerant algorithm without resorting to any specific hardware. We finally show that, with proper architectural support, the level of attainable accuracy can match hardware-based solutions.