Relating Diagnosability, Strong Diagnosability and Conditional Diagnosability of Strong Networks
Lists
Only you see this
Abstract
An interconnection network’s diagnosability is an important measure of its self-diagnostic capability. Based on the classical notion of diagnosability, strong diagnosability and conditional diagnosability were proposed later to better reflect the networks’ self-diagnostic capability under more realistic assumptions. In this paper, we study a class of interconnection networks called strong networks, which are <formula formulatype="inline" xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink"><tex Notation="TeX">$n$</tex> </formula> -regular, <formula formulatype="inline" xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink"><tex Notation="TeX">$(n - 1)$</tex> </formula> -connected, and with <formula formulatype="inline" xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink"><tex Notation="TeX">$cn$</tex> </formula> -number no more than <formula formulatype="inline" xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink"><tex Notation="TeX">$n - 3$</tex> </formula> . We build a relationship among the three diagnosability measures for strong networks. Under both PMC and <formula formulatype="inline" xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink"><tex Notation="TeX">${\rm MM}^{\ast}$</tex> </formula> models, given a strong network <formula formulatype="inline" xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink"><tex Notation="TeX">$G$</tex> </formula> with diagnosability <formula formulatype="inline" xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink"><tex Notation="TeX">$t$</tex> </formula> , we prove that <formula formulatype="inline" xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink"><tex Notation="TeX">$G$</tex> </formula> is strongly <formula formulatype="inline" xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink"><tex Notation="TeX">$t$</tex> </formula> -diagnosable if and only if <formula formulatype="inline" xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink"><tex Notation="TeX">$G$</tex> </formula> ’s conditional diagnosability is greater than <formula formulatype="inline" xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink"><tex Notation="TeX">$t$</tex> </formula> . A simple check can show that almost all well-known regular interconnection networks are strong networks. The significance of this paper’s result is that it reveals an important relationship between strong and conditional diagnosabilities, and the proof of strong diagnosability for many interconnection networks under <formula formulatype="inline" xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink"><tex Notation="TeX">${\rm MM}^{\ast}$</tex> </formula> or PMC model is not necessary if their conditional diagnosability can be shown to be strictly larger than their diagnosability.
BibTeX
@article{zhu2014relating,
author = {Qiang Zhu and Guodong Guo and Dajin Wang},
title = {{Relating Diagnosability, Strong Diagnosability and Conditional Diagnosability of Strong Networks}},
journal = {IEEE Trans. Computers},
year = {2014},
url = {https://openreview.net/forum?id=1KbLXPiAE4},
}Loading related content...