Summary Processor fault diagnosis takes a key role in fault‐tolerant computing on multiprocessor systems. Thet/kdiagnosis strategy which is a generalization of the precise and pessimistic diagnosis strategies can significantly improve the self‐diagnosing capability of the system. Using this tool, it is possible to deal with large faults in the system. This paper presents at/kdiagnosis algorithm onn‐dimensional hypercube‐like networks (include Hypercubes, Crossed cubes, Möbius cubes, Locally Twisted cubes, and Twisted cubes) for anyk∈[0,n−2]. The algorithm can correctly identify all nodes except at mostknodes undiagnosed. It runs inO(N) time, whereN=2nis the total number of nodes ofn‐dimensional hypercube‐like networks. To the best of our knowledge, in the casek≥4, there is no knownt/kdiagnosis algorithm for general diagnosable system or any specific system.

Diagnosis by comparison is a realistic approach to detect faults of multiprocessor systems. This paper considers a pessimistic diagnostic strategy for hypercube-like multiprocessor systems under the comparison model. The pessimistic strategy is a diagnostic process whereby all faulty nodes can be correctly identified and at most one fault-free node may be misjudged as a faulty node. We propose a pessimistic diagnosis algorithm based on the largest component in the faulty system. For a system with$N=2^n$nodes and$n\ge 5$, when the number of faulty nodes is bounded by$2n-2$, the algorithm can correctly identify all nodes except at most one node left undiagnosed. The time complexity of the algorithm is$O(Nlog_2N)$.

In this paper, we propose a novel method to deal with a large number of faults existing in the system based on the PMC model. We derive a fault bound T for a N-node ring based on cycle partition and Pigeonhole principle. Under this fault bound, it is guaranteed that at least one sequence obtained from cycle partition can be picked out and all nodes in this sequence can be identified. The corresponding ring diagnosis algorithm is then provided. Using this ring diagnosis method, we propose a five-round adaptive diagnosis scheme for networks containing Hamiltonian cycle. Simulations show that for Hamiltonian networks with node degree more than 3, it can achieve almost complete diagnosis.