Reliable distributed computing in parallel processing systems

Abstract

This thesis presents a software approach which uses efficient diagnosis along with a recovery strategy to achieve fault tolerance in a multiprocessor system. It proposes two algorithms: a hybrid diagnosis algorithm, and an adjacent checkpointing and recovery synchronisation algorithm for multiprocessor systems. The hybrid diagnosis algorithm is t diagnosable, and is able to identify hardware faults or errors correctly, given t processor failures in a k-regular connected network (where t= ᵏ/₂). It requires only one broadcast message to determine the global state in the absence of failures, and 2k+2 messages to detect a failure in the worst case. The number of messages required is constant as the size of the network varies. Compared to other algorithms that require at least O(n) messages for deciding the global state, this algorithm offers a significant improvement. The adjacent checkpointing and recovery synchronisation algorithm is designed for dynamic partial failure recovery in an array parallel processing system. This algorithm can be incorporated into a parallel operating system, and be independent of the application. It provides continuing operation in the presence of multiple processor failures, or failed inter-processor links, without the requirement for spare hardware modules. The algorithm is constructed by combining a process replication strategy and a process migration technique. The discussion is centered on two issues: efficient checkpointing, and network synchronisation for failure recovery. The algorithm uses neighbouring nodes to store recovery points, and checkpointing is executed in parallel. In the thesis, we estimate the performance penalty imposed by the fault-tolerant algorithm in the fault-free situation and judge the performance degradation when the system suffers one or more processor failures. The thesis also presents a fault tolerant numerical weather prediction system designed for the New Zealand Meterological Service.