Partial syndrome-based system-level fault diagnosis using game theory

摘要

This paper introduces a novel diagnosis approach, using game theory, to solve the comparison-based system-level fault identification problem in distributed and parallel systems based on the asymmetric comparison model. Under this diagnosis model tasks are assigned to pairs of nodes and the results of executing these tasks are compared. Using the agreements and disagreements among the nodes' outputs, i.e. the input syndrome, the fault diagnosis algorithm identifies the fault status of the system's nodes, under the assumption that at most f of these nodes can permanently fail simultaneously. Since the introduction of the comparison model, significant progress has been made in both theory and practice associated with the original model and its offshoots. Nevertheless, the problem of efficiently identifying the set of faulty nodes when not all the comparison outcomes are available to the fault identification algorithm prior to initiating the diagnosis phase, i.e. partial syndromes, remains an outstanding research issue. In this paper, we first show how game theory can be adapted to solve the fault diagnosis problem by maximising the payoffs of all players (nodes). We then demonstrate, using results from a thorough simulation, the effectiveness of this approach in solving the fault identification problem using partial syndromes from randomly generated diagnosable systems of different sizes and under various fault scenarios. We have considered large diagnosable systems, and we have experimented extreme faulty situations by simulating all possible fault sets even those that are less likely to occur in practice. Over all the extensive simulations we have conducted, the new game-theory-based diagnosis algorithm performed very well and provided good diagnosis results, in terms of correctness, latency, and scalability, making it a viable addition or alternative to existing diagnosis algorithms.