Characterization of Diagnosability Under the Bounded Comparison Model

The <inline-formula xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink"><tex-math notation="LaTeX">$(f_{1},f_{2})$</tex-math></inline-formula>-bounded symmetric comparison (<inline-formula xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink"><tex-math notation="LaTeX">$(f_{1}, f_{2})$</tex-math></inline-formula>-BSC) model, proposed by Fuhrman and Nussbaumer in 1996, is a hybrid of the symmetric comparison model and asymmetric one, which assumes that at most <inline-formula xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink"><tex-math notation="LaTeX">$f_{1}$</tex-math></inline-formula> processors fail while the upper threshold of faulty processors producing identical outcomes is <inline-formula xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink"><tex-math notation="LaTeX">$f_{2}$</tex-math></inline-formula>. Based on the <inline-formula xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink"><tex-math notation="LaTeX">$(f_{1},f_{2})$</tex-math></inline-formula>-BSC model, a novel model, abbreviated as the <inline-formula xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink"><tex-math notation="LaTeX">$f$</tex-math></inline-formula>-BSC model, is proposed by dropping the restriction on <inline-formula xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink"><tex-math notation="LaTeX">$f_{1}$</tex-math></inline-formula> but highlighting the hypothesis on maximum number of faulty processors producing identical outcomes is <inline-formula xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink"><tex-math notation="LaTeX">$f$</tex-math></inline-formula>. As a generalization of this model, a variant of MM<inline-formula xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink"><tex-math notation="LaTeX">$^*$</tex-math></inline-formula> model abbreviated as the <inline-formula xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink"><tex-math notation="LaTeX">$f$</tex-math></inline-formula>-BMM<inline-formula xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink"><tex-math notation="LaTeX">$^*$</tex-math></inline-formula> model is proposed by adding an upper threshold <inline-formula xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink"><tex-math notation="LaTeX">$f$</tex-math></inline-formula> to the number of faulty processors producing identical comparison outcomes, which are executed by a faulty comparator on two faulty neighbouring processors. Under this restriction, fewer possible syndromes are generated and therefore faulty processors can be diagnosed faster and more accurately. Subsequently, we present diverse characterizations regarding system-level diagnosis under the two new models. Moreover, we further establish the metric correlation between <inline-formula xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink"><tex-math notation="LaTeX">$g$</tex-math></inline-formula>-good-neighbor (<inline-formula xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink"><tex-math notation="LaTeX">$g$</tex-math></inline-formula>-GN) diagnosability under <inline-formula xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink"><tex-math notation="LaTeX">$f$</tex-math></inline-formula>-BMM<inline-formula xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink"><tex-math notation="LaTeX">$^*$</tex-math></inline-formula> model and <inline-formula xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink"><tex-math notation="LaTeX">$R^{g}$</tex-math></inline-formula>-connectivity of general networks. Finally, the <inline-formula xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink"><tex-math notation="LaTeX">$g$</tex-math></inline-formula>-GN diagnosabilities under <inline-formula xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink"><tex-math notation="LaTeX">$f$</tex-math></inline-formula>-BMM<inline-formula xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink"><tex-math notation="LaTeX">$^*$</tex-math></inline-formula> model are characterized among five preeminent interconnection networks.