The relationship between extra connectivity and t/k-diagnosability under the PMC model①

XIAO Zhifang(肖志芳), ZHONG Guoxuan, CHEN Jianqi, GUO Chen②, PENG Shuo

(?School of Electronic and Information Engineering, Jinggangshan University, Ji'an 343009, P.R.China)

(??Jiangxi Engineering Laboratory of IoT Technologies for Crop Growth, Ji'an 343009, P.R.China)

Abstract It is well-known that connectivity is closely related to diagnosability.If the relationships between them can be established, many kinds of diagnosability will be determined directly.So far,some notable relationships between connectivity and diagnosability had been revealed.This paper intends to find out the relationship between extra connectivity and t/k-diagnosability under the PMC(Preparata, Metze, and Chien) model.Then, applying this relationship, the t/k-diagnosability of bijective connection (BC) networks are determined conveniently.

Key words: extra connectivity, t/k-diagnosability, the PMC model

0 Introduction

Connectivity and diagnosability are generally considered as two important indicators that are used to evaluate the reliability of multiprocessor computer systems.They are also considered as two closely related parameters.So far, some important results had been achieved in the study of connectivity and diagnosability.But there are still some outstanding diagnosability measurement problems, especially for interconnection networks with insufficient regularity and symmetry.

Research shows that the various diagnosability of the interconnection network will increase with the improvement of the relevant connectivity, and show an obvious linear relationship.If it can be found out the relationship between diagnosability and related connectivity, it can be greatly simplified the measurement process of diagnosabilities and quickly calculate various diagnosabilites of a series of interconnection networks.Therefore, it is a very important and valuable scientific issue to study the relationship between connectivity and diagnosability.

1 Preliminaries

In general, a multiprocessor system can be modeled byG(V,E),whereV(G) andE(G) are the node set and the edge set, respectively.Letx∈V(G) andA,B?V(G),N(x) is the set of all the neighbors ofx,N(A)= ∪a∈A N(a)-AandNB(A)=N(A) ∩B.

The connectivityk(G) ofGis an important measure for fault tolerance ofG.However, connectivity underestimates the resilience of large networks[1].To compensate for this shortcoming,many kinds of connectivity are introduced,such as conditional connectivity[2],restricted connectivity[3], super connectivity[4], extra connectivity[5], et al.Among them, g-extra connectivity ofG,written askg(G),is the minimum size over all the g-extra cuts ofG.Any subsetF?V(G)is a g-extra cut ofGifG-Fis disconnected and each component ofG-Fhas size at leastg+1.Clearly,k0(G)=k(G).

In the operation of multiprocessor systems, identifying faulty processors is an important problem.In the process of identifying faulty processors, a fault diagnosis model and a diagnosis strategy are indispensible.At present, one of the widely adopted fault diagnosis model is PMC (Preparata, Metze, and Chien) model[6].Under the PMC model,each pair of adjacent nodes can be allowed to test each other.If the tester is fault-free(faulty), its outcomes are correct(unreliable, respectively).For any edge(u,v) ∈E(G),u→0v(u→1v)represents the outcome of testu→vis fault-free (faulty, respectively).In addition,u?00vrepresentsu→0vandv→0u.A collection of all the test results is called a syndromeσ.Ref.[7] introduced thet/k-diagnosis strategy, which requires that when the number of fault nodes does not exceedt,all fault nodes can be isolated in a set of node and at mostknodes might be misdiagnosed.Thet/k-diagnosability ofG,is the maximum oftsuch thatGist/k-diagnosable[7].Thet/k-diagnosability of a series of regular networks under PMC model is determined[8-15].It is well-known that the constraints oft/k-diagnosability and k-extra connectivity are basically the same.Therefore, Refs[11] and [12] believe that it is an interesting direction to analyze the relationship between extra connectivity andt/k-diagnosability.In this paper, the relationship between g-extra connectivity andt/k-diagnosability under the PMC model are revealed.

2 σ-0-test subgraph

Under the PMC model, given a graphGand a syndromeσ, each connected subgraphs or isolated points is called aσ-0 -test subgraph ofGby removing all those edges whose outcomes are ‘1’[16].The set of all theσ-0-test subgraph ofGis denoted byTσ(G).Then,V(Tσ(G))=V(G) andE(Tσ(G))= {(u,v)∈E(G),u?00v} (see Fig.1).

Given a syndromeσ, for anyσ-0-test subgraphS∈Tσ(G), all the nodes inShave the same status(fault-free or faulty).Then, under the PMC model,the following properties are shown as follows.

Property 1Given a syndromeσ, letFbe a fault set ofG.Then any componentCofG-Fis aσ-0-test subgraph ofGand each node inCis fault-free.

Property 2Given a syndromeσ, letFbe a fault set ofG.ThenFwill be divided into one or severalσ-0-test subgraphs ofG.

3 The relationship between extra connectivity and t/k-diagnosability under the PMC model

LetXnbe ann-dimensional interconnection network andXncan be divided into to copies ofXn-1,written asLandR.Then, the following four conditions will be used in the rest of this paper.

(1) LetS?V(R) (orS?V(L) ) with|S|=g≥1,|NR(S)|+|NL(S)|≥kg-1(Xn) forn≥8 and 1 ≤g≤n-4.

(2) For any positive integersg,g0andg1withg,g0,g1≥1.Ifg=g0+g1, thenkg0-1(Xn-1)+kg1-1(Xn-1) ≥kg-1(Xn) forn≥8 and 1 ≤g≤n-4.

(3) The functionf(g)=kg(Xn) increases with increasinggforn≥8 and 1 ≤g≤n-4.

(4)kg+1(Xn)≥kg(Xn)+n-g-4 forn≥8 and 1 ≤g≤n-5.

Theorem 1LetS?V(Xn) with|S|=g.IfXnsatisfies the conditions (1) and (2),|N(S)|≥kg-1(Xn) forn≥8 and 1 ≤g≤n-4.

ProofThe proof is by induction on g.Ifg= 1,|S|= 1.Then|N(S)|≥k(Xn)=k0(Xn).Hence, the theorem is true forg= 1.Assume that|N(S)| ≥kh-1(Xn)with|S|=hand 2 ≤h≤g-1.

DecomposeXninto two copies ofXn-1,denoted byLandR.LetS0=S∩V(L) andS1=S∩V(R).Let|S0|=g0and|S1|=g1.Theng0+g1=g.Without loss of generality, let|S0|≤|S1|.

Case 1|S0|= 0.

Since|S0|= 0,|S1|=gand|N(S)|≥|NR(S1)|+|NL(S1)|.By condition (1),|NR(S)|+|NL(S)| ≥kg-1(Xn).So,|N(S)|≥kg-1(Xn).

Case 2|S0|≥1.

Since|S0|≥1,|N(S)|≥|NL(S0)|+|NR(S1)| such thatNL(S0)=N(S0) ∩V(L) andNR(S1)=N(S1)∩V(R).By the induction hypothesis,|NL(S0)|≥kg0-1(Xn-1) and|NR(S1)|≥kg1-1(Xn-1).By condition (2),|NL(S0)|+|NR(S1)| ≥kg0-1(Xn-1)+kg1-1(Xn-1)≥kg-1(Xn).So,|N(S)|≥kg-1(Xn).

The theorem holds.

Theorem 2IfXn(n≥8) satisfies the conditions(1) -(3), letS?V(Xn) and 2 ≤g+1 ≤|S|≤n-4.Then|N(S)|≥kg(Xn).

ProofLet|S|=h.By Theorem 1,|N(S)|≥kh-1(Xn).By condition (3),kh-1(Xn) ≥kg(Xn).Hence,|N(S)|≥kg(Xn).

Theorem 3IfXn(n≥8) satisfies the conditions(1) -(4) and|V(Xn)|> 2kg(Xn)+g-1,letF?V(Xn) with|F|≤kg(Xn)-1 and 1 ≤g≤n/2-3.IfXn-Fis disconnected,Xn-Fhas a largest componentC1(|C1|≥g+1) and the union of the remaining components has at mostgnodes.

ProofLet all the components ofXn-FbeC1,C2,…,Cmwith|C1|≥|C2|≥…≥|Cm|.Suppose that|C1|,|C2|,…,|Cr-1|≥g+ 1 and|Cr|,|Cr+1|,…,|Cm|≤gforr≥1.

Thus,|F|≥|N(Cr∪Cr+1∪…∪Cm)|.Suppose thatg+1 ≤|Cr|+|Cr+1|+…+|Cm|≤n-4.By Theorem 2,|F|≥|N(Cr∪Cr+1∪… ∪Cm)|≥kg(Xn),which contradicts|F|≤kg(Xn)-1.Therefore, either|Cr|+|Cr+1|+ …+|Cm|≥n- 3 or|Cr|+|Cr+1|+ …+|Cm|≤g.Suppose that|Cr|+|Cr+1|+…+|Cm|≥n-3.Since|Cr|,|C2|,…,|Cr-1|≤g≤n/2-3, (n-4)- (g+1)=n-g-5 ≥(2g+6)-g-5>g.Therefore, there exists a unionHof some components ofCr,Cr+1,…,Cm,such thatn-4 ≥|H|≥g+1(see Fig.2).By Theorem 2,|N(H)|≥kg(Xn),which contradicts|F|≤kg(Xn)-1.Therefore,|Cr|+|Cr+1|+…+|Cm|≤g.

Fig.2 The illustration of| H|

Since|Cr|+|Cr+1|+…+|Cm|≤gand|F|≤kg(Xn)-1 and|V(Xn)|> 2kg(Xn)+g-1,|C1|+|C2|+ …+|Cr-1|=|V(Xn)|-|F|- (|Cr|+|Cr+1|+…+|Cm|)> 2kg(Xn)+g-1-(kg(Xn)-1)-g>kg(Xn)> 0.Therefore, there exists at least a componentC1ofXn-Fsuch that|C1|≥g+1 nodes.

which contradicts|F|≤kg(Xn)-1.So,Xn-Fhas exactly one component which have at leastg+1 nodes.

Theorem 4IfXn(n≥8) satisfies the conditions(1) -(4) with|V(Xn)|> 2kg(Xn)+g-1 and 1 ≤g≤n/2-3,letFbe a fault set with|F|≤kg(Xn)-1.Then, under any syndromeδproduced byF, the maximalσ-0-test subgraph ofXnis fault-free.

ProofIfXn-Fis connected,|V(Xn)-F|=|V(Xn)|-|F|≥2kg(Xn)+g-1-(kg(Xn)-1)=kg(Xn)+g.Since|F|≤kg(Xn)-1,|Xn-F|>|F|.By Property 1,Xn-Fis a the maximalσ-0-test subgraph ofXnand each node ofXn-Fis faultfree.IfXn-Fis disconnected, by Theorem 3,Xn-Fhas a largest componentC(|C|≥g+ 1) and the union of the remaining components has at mostgnodes.By Property 1,Cis aσ-0-test subgraph.Since

Theorem 5IfXn(n≥8) satisfies the conditions(1) -(4) with|V(Xn)|> 2kg(Xn)+g-1,thenXniskg(Xn)-1/g-diagnosable for 1 ≤g≤n/2-3.

ProofLetFbe a fault set ofXnwith|F|≤kg(Xn)-1.By Theorem 3,Xn-Fhas a largest componentC(|C|≥g+1) and the union of the remaining components has at mostgnodes.By Theorem 4,Cis the maximalσ-0-test subgraph and every node inCis fault-free.Therefore, there are|F|+gnodes undiagnosed.Then, all the faulty nodes can be isolated to within a set of at most|F|+gnodes.

There are at mostgnodes might be misdiagnosed.Therefore,Xniskg(Xn)-1/g-diagnosable.

4 Application to BC networks

Ann-dimensional bijective connection (BC) network is denoted byBnwith|V(Bn)|= 2n.Bncan be divided into two copies ofBn-1, written asLandR,and there exists a perfect matching betweenLandR(see Fig.3).ThenBnhas the following lemmas.

Fig.3 The topology of B3

5 Conclusion

In the design and operation of large-scale multiprocessor systems, reliability is a key issue to be considered.It is well-known that connectivity and diagnosability are two crucial subjects for reliability and fault tolerability and they are closely related to each other.This paper establishes a relationship between extra connectivity andt/k-diagnosability under the PMC model.Then, using this relationship, it is proved thatBnis(kg(Bn) -1)/g-diagnosable.