Synchronization of fault-tolerant distributed real-time multicomputers.
A. Olson · Deep Blue (University of Michigan) · 1994
Synchronization is a basic and necessary service of real-time distributed systems. It allows the global ordering of events, and the coordination of schedules. This dissertation presents a number of different efficient and fault-tolerant algorithms that can be used in the synchronization of a fault-tolerant distributed real-time multicomputer. Use of the existing communications network, and avoiding the use of master clocks are primary considerations. Synchronization is divided into three distinct operations: distributing clock information, estimating clock skews, and adjusting clock values. A number of algorithms are presented which perform one or more of these operations. An algorithm for adjusting clock values is presented which relaxes the restrictions found in similar algorithms on the number and quality of clock skew estimates. Another adjustment algorithm is presented which relaxes the restrictions on the number of clock skew estimates even further. Neither algorithm depends on master clocks. Next is presented an efficient algorithm for distributing clock information which uses the existing network and requires no specialhardware. Two probabilistic estimation algorithms are presented which use this clock distribution algorithm. Analytical and simulation results demonstrate the efficiency of the clock distribution algorithm, and the effectiveness of the estimation algorithms. Finally, an algorithm for "continuous" distribution of clock information is presented. Normally, the clock distribution algorithm runs periodically, producing a heavy, periodic load on the system. Continuous operation results in a low-level near-constant load which causes less interference with system operation. The algorithms presented are complementary and work well together, but are still very much independent. One is free to select from among them only those algorithms which are advantageous, and to use them in concert with algorithms published elsewhere.