Partial syndrome-based system-level fault diagnosis using game theory. Issue 1 (2nd January 2018)

• Record Type: Journal Article
• Authors: Elhadef, Mourad; Grira, Sofiane
• Is Part Of: International journal of parallel, emergent and distributed systems. Volume 33:Issue 1(2018)
• Page Start: 69
• Page End: 86
• Publication Date: 2018-01-02
• Subjects: Fault tolerance -- system-level fault diagnosis -- distributed and parallel systems -- asymmetric comparison model -- partial syndrome -- game theory; Parallel computers -- Periodicals; Electronic data processing -- Distributed processing -- Periodicals; Computer algorithms -- Periodicals; 004.35
• DOI: 10.1080/17445760.2017.1284213
• Languages: English
• ISSNs: 1744-5760

Abstract

Abstract: 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 t 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. Graphical Abstract: A Comparison Graph and an Asymmetric Comparison Syndrome.