Generating a fault tolerant global clock in a high speed distributed system

Abstract

A technique is described for constructing a fault-tolerant global clock in a point-to-point distributed system with an arbitrary topology, which constitutes a wide-area network. It is assumed that the network is constructed of optical links with very high transmission rates. The approach used is to generate a global clock from the ensemble of the local transmission clocks, and not to synchronize these high-speed clocks directly. The steady-state algorithm which generates the global system clock is executed in hardware by the network interface of each node. As a result, it is possible to estimate accurately intermodal delays and thereby to achieve a much tighter synchronization than with other methods. The basic synchronization time step is proportional to the error or uncertainty in the measurement of the end-to-end network delay rather than to the actual value of the end-to-end network delay. Node and network models are presented, and the synchronization condition is defined. The synchronization algorithm, its bound, and its correctness proof are presented. A procedure is described for detecting and isolating a faulty component, while maintaining the integrity of the global clock.