Clock Synchronization of a Large Multiprocessor System in the Presence of Malicious Faults

Clock synchronization in the presence of malicious faults is one of the main problems associated with the design of a multiprocessor system. Although over the past few years many different algorithms have been proposed for overcoming this problem, they are not suitable for a large real-time multiprocessor system due to their excessive time overhead, asymmetric structure, and/or large number of interconnections. To remedy this problem, we propose a new method in this paper that i) requires little time overhead by using phase-locked clock synchronization, ii) needs a clock network very similar to the processor network, and iii) uses only 20-30 percent of the total number of interconnections required by a fully connected network for almost no loss in the synchronizing capabilities. Both ii) and iii) are made possible by grouping the various clocks in the system into many different clusters and then treating the clusters themselves as single clock units as far as the network is concerned. The method is significant in that regardless of their size multiprocessor systems can be built at an inexpensive cost without sacrificing both the synchronization and fault tolerance capabilities. To show the feasibility of our method, an example hardware implementation is presented. This implementation turns out to be much simpler than the other existing methods and also retains the symmetry and synchronizing capabilities of the network.