Characterization of Diagnosabilities on the Bounded PMC Model. (18th December 2019) - Lian, Guanqin; Zhou, Shuming; Hsieh, Sun-Yuan; Chen, Gaolin; Liu, Jiafei; Gu, Zhendong
Abstract: In this paper, we propose a new digragh model for system level fault diagnosis, which is called the $(f_1, f_{2})$ -bounded Preparata–Metze–Chien (PMC) model (shortly, $(f_1, f_{2})$ -BPMC). The $(f_1, f_{2})$ -BPMC model projects a system such that the number of faulty processors that test faulty processors with the test results $0$ does not exceed $f_{2}$ $(f_2≤ f_{1})$ provided that the upper bound on the number of faulty processors is $f_{1}$ . This novel testing model compromisingly generalizes PMC model (Preparata, F.P., Metze, G. and Chien R.T. (1967) On the connection assignment problem of diagnosable systems. IEEE Tran. Electron. Comput., EC-16, 848–854) and Barsi–Grandoni–Maestrini model (Barsi, F., Grandoni, F. and Maestrini, P. (1976) A theory of diagnosability of digital systems. IEEE Trans. Comput. C-25, 585–593). Then we present some characterizations for one-step diagnosibility under the $(f_1, f_{2})$ -bounded PMC model, and determine the diagnosabilities of some special regular networks. Meanwhile, we establish the characterizations of $f_1/(n-1)$ -diagnosability and three configurations of $f_1/(n-1)$ -diagnosable system under the $(f_1, f_{2})$ -BPMC model.