Faulty node modeling and diagnosis in interconnection networks (extended abstract). (December 2019) - Cheng, E; Mao, Y P; Qiu, K; Shen, Z
Abstract: Faulty processing node analysis, in particular, self-diagnostic paradigm, is an important topic in the area of interconnection network studies. Several diagnostic models have been introduced, with the PMC and MM* models being two of the most popular ones. Researchers have also proposed various extensions and enhancements of fault-tolerance models to better capture the distribution, and identification, of faulty nodes in realistic scenarios. One of them is the g-extra fault-tolerance model, where each cluster in a network with faulty nodes contains at least g+1 fault-free nodes. This paper, following an analytical and constructive approach based on applied graph theory, suggests a general process to identify the maximum number of faulty nodes in a network in terms of the g-extra fault-tolerance model, and as a demonstrative example, provides a specific result for the (n, k)-star graphs.