At/kdiagnosis algorithm on hypercube‐like networks
Min Xie, Liang-Cheng Ye, Jiarong Liang · Concurrency and Computation Practice and Experience · 2017
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.