On the conditions of guaranteed k-fault tolerant systems supporting on-the-fly repairs

This paper presents the necessary and sufficient conditions for a system with n functioning Processing Elements (PE´s), κ spare PE´s, to be k-fault tolerant (κ-FT). A repair is carried out by a "replacement chain" of PE´s, starting with a spare, each taking over the task of the next one, to eventually reaching a faulty PE. In this paper, a Task-PE relationship model is proposed, based on which a "replacement chain algebra" can be formulated. This makes it possible to calculate precisely how a repair will affect all the other potential repairs in the future, and to determine whether the system remains repairable for subsequent faults. In the end, two equivalent conditions (both necessary and suficient) are presented and proven in this paper to make a system guaranteed k-FT, supporting on-the-fly repair after every fault occurrence.