A Note on the Pessimistic Diagnosability of Augmented Cubes

作者：RONG-XIA, HAO; MEI-MEI, GU; HUAN, LUO; AI-MEI, YU

来源：Journal of Interconnection Networks, 2016, 16(03n04): 1671001.

DOI：10.1142/s0219265916710018

<jats:p> A system is t/t-diagnosable if, provided the number of faulty processor is bounded by t, all faulty processors can be isolated within a set of size at most t with at most one fault-free node mistake as a faulty one. The pessimistic diagnosability of a system G, denoted by <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML" display="inline" overflow="scroll" altimg="eq-00001.gif"><mml:mrow><mml:msub><mml:mi>t</mml:mi><mml:mi>p</mml:mi></mml:msub><mml:mo stretchy="false">(</mml:mo><mml:mi>G</mml:mi><mml:mo stretchy="false">)</mml:mo></mml:mrow></mml:math>, is the maximal number of faulty processors so that the system G is t/t-diagnosable. The augmented cube <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML" display="inline" overflow="scroll" altimg="eq-00002.gif"><mml:mrow><mml:mi>A</mml:mi><mml:msub><mml:mi>Q</mml:mi><mml:mi>n</mml:mi></mml:msub></mml:mrow></mml:math>, proposed by Choudum and Sunitha [Networks 40 (2) (2002) 71–84], has many attractive properties such as regularity, strong connectivity and symmetry. In this paper, we determine the pessimistic diagnosability of the n-dimensional augmented cube <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML" display="inline" overflow="scroll" altimg="eq-00003.gif"><mml:mrow><mml:mi>A</mml:mi><mml:msub><mml:mi>Q</mml:mi><mml:mi>n</mml:mi></mml:msub></mml:mrow></mml:math> and prove that <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML" display="inline" overflow="scroll" altimg="eq-00004.gif"><mml:mrow><mml:msub><mml:mi>t</mml:mi><mml:mi>p</mml:mi></mml:msub><mml:mo stretchy="false">(</mml:mo><mml:mi>A</mml:mi><mml:msub><mml:mi>Q</mml:mi><mml:mi>n</mml:mi></mml:msub><mml:mo stretchy="false">)</mml:mo><mml:mo>=</mml:mo><mml:mn>4</mml:mn><mml:mi>n</mml:mi><mml:mo>−</mml:mo><mml:mn>8</mml:mn></mml:mrow></mml:math> for <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML" display="inline" overflow="scroll" altimg="eq-00005.gif"><mml:mrow><mml:mi>n</mml:mi><mml:mo>≥</mml:mo><mml:mn>5</mml:mn></mml:mrow></mml:math>. </jats:p>

• 出版日期2016-9
• 单位北京交通大学