Diagnosabilities ofexchanged hypercube networks under the pessimistic one-step diagnosis strategy

Schoolof Computer,Electronics and Information,Guangxi University,Nanning 530004,China

Diagnosabilities ofexchanged hypercube networks under the pessimistic one-step diagnosis strategy

Jiarong Liang?,Ying Huang,and Liangcheng Ye

Schoolof Computer,Electronics and Information,Guangxi University,Nanning 530004,China

The exchanged hypercube EH(s,t)(where s≥1 and t≥1)is obtained by systematically reducing links from a regular hypercube Q s+t+1.One-step diagnosis ofexchanged hypercubes which involves only one testing phase during which processors test each other is discussed.The diagnosabilities of exchanged hypercubes are studied by using the pessimistic one-step diagnosis strategy under two kinds ofdiagnosis models:the PMC model and the MM?model.The main results presented here are the two proofs thatthe degree of diagnosability ofthe EH(s,t)under pessimistic one-step t1/t1 fault diagnosis strategy is 2s where 1≤s≤t(respectively,2t,where 1≤t≤s)based on the PMC model and that it is also 2s where 1≤s≤t(respectively,2t, where 1≤t≤s)based on the MM?model.

pessimistic diagnosis strategy,exchanged hypercube network,PMC model,MM?model,interconnection networks.

1.Introduction

With the rapid development of the very large scale integration(VLSI)technology,a multiprocessor system may contain hundreds or even thousands of processors.It is inevitable that the processors in the system become faulty. Before being repaired,allthe faultprocessors in the system must be diagnosed.The problem of fault self-diagnosis in multiprocessorsystems has gained increasing importance.

Severaldifferentstrategies have been developed forselfdiagnosis in multiprocessor systems.Preparata et al.[1] fi rst proposed a model called PMC model.Under this model,processors test each other if they are adjacent directly.It assumes that the tests performed by fault-free nodes are always correct,whereas tests performed by faulty nodes are unreliable.The PMC model was also adopted in[2-9].Maeng and Malek[10]proposed another model,called the MM model.It performs the diagnosis by allocating the same task to pairs of adjacentprocessors and comparing theirresponses.Sengupta and Dahbura[11] suggested a modi fi cation of the MM model,called the MM?model,in which a comparison can be performed by each processor to each pair of distinct neighbors with which itcan communicate directly.The MM?modelwas also adopted in[12-14].

Preparata et al.[1]de fi ned the notion of the tpdiagnosable system in which all the faulty processors can be identi fi ed provided the numberoffaulty processorsdoes notexceed tp.The maximum number tpsuch thatthe system is tp-diagnosable is called tp-diagnosability.In order to improve the capability of self-diagnosis,Friedman and Kavianpour[15,16]introduced the concept of the t1/t1-diagnosable system in which all the faults can be isolated within a set of at most t1nodes provided the number of faulty nodes does notexceed t1.The maximum number t1such that the system is t1/t1-diagnosable is called t1/t1-diagnosability(or pessimistic diagnosability).Yang et al. [17]proved thatatmostone fault-free node may be identifi ed as faulty in the t1/t1-diagnosable system.

It is widely known that the hypercube Qnhas been one of the most popular interconnection networks for the parallel computer system and its diagnosability under the pessimistic one-step diagnosis strategy based on the PMC model has been studied in[8].As the variants of the hypercube,the exchanged hypercube,denoted as EH(s,t), proposed by Loh etal.[18],is a spanning subgraph of the Qs+t+1with aboutone halfofits edges[19],butstillkeeps many desirable properties of the hypercube.Ithas received a great deal of attention and researches.The connectivity and conditionalconnectivity were determined in[20-22]. The topologicalproperties and embedding issues were investigated in[23].However,the pessimistic diagnosability of exchanged hypercube has notbeen studied yet.

In this paper,we fi rst investigate the pessimistic diagnosability of the exchanged hypercube and determine thatdiagnosabilities of EH(s,t)underthe PMC modeland the MM?modelare 2s where 1≤s≤t.In Section 2,some necessary de fi nitions and backgrounds are given.In Section 3,we prove the 2s/2s-diagnosability of the EH(s,t) under the two diagnosis models using the pessimistic onestep diagnosis strategy.We conclude our paper in Section 4.

2.Preliminaries

An interconnection network can be modeled by an undirected graph G=(V,E),where V is the setof processors and E is the set of communication links.For graph terminology and notation not de fi ned here we follow[24]. The neighbor-set of V＇in G is de fi ned asΓ(G,V＇)= {v∈V(G)|(u,v)∈E(G),u∈V＇,V＇?V(G)}-V＇. N(u)={v∈V(G)|v is adjacentto u}.

Definition 1The exchanged hypercube is de fi ned as an undirected graph EH(s,t)=(V,E)(s≥1,t≥1). The setofvertices V is V={as···a1bt···b1c|ai,bj,c∈{0,1}for i∈[1,s],j∈[1,t]}.The setof edges E is composed of three disjointtypes E0,E1and E2.

where⊕denotes the XOR operator and v[x:y]denotes the bit pattern of v from dimension y to dimension x.H(x,y)denotes the Hamming distance between nodes x and y.The two exchanged hypercubes EH(1,1)and EH(1,2)are shown in Fig.1.

Fig.1 Two exchanged hypercubes EH(1,1)and EH(1,2)

The following three properties which can concise our proof are obtained by Loh etal.[18]and Ma[21].

Property 1EH(s,t)can be decomposed into two copies of EH(s,t-1)or EH(s-1,t).

Property 2EH(s,t)is isomorphic to EH(t,s).

Property 3The connectivity and the edge connectivity of EH(s,t)are s+1 where 1≤s≤t.

The super connectivityκ＇(G)of a graph G is the minimum numberof vertices whose removalleaves the remaining graph disconnected and every component contains at leasttwo vertices.

Lemma 1[22]The super connectivity of EH(s,t) (s≥1,t≥1)isκ＇(EH(s,t))=2s.

Under the PMC model,a node can test another node if they are adjacent.Letσ(u,v)=0(or 1)represent that u evaluates v as fault-free(or faulty).The collection of all test results forms a test syndrome,denoted asσ.The PMC model assumes that a test result is 0 if the two involved nodes are fault-free,1 if the tester is fault-free and the tested node is faulty,and unpredictable if the tester is faulty(see Table 1).

Table 1 The PMC model

Under the MMmodel,two nodes are allocated the same task and their responses are compared by a comparator.A node is a comparator of two nodes if it is a common neighbor of them.Letσ(u,v;w)=0(or 1)represent that w evaluates u and v as agreement(or disagreement). The collection of all comparison results forms a comparison syndrome,denoted asσ.The MM?modelassumes thata comparison resultis 0 if the three nodes involved are all fault-free,1 if the comparator is fault-free and at least one of the two nodes being compared is faulty,and unpredictable if the comparatoris faulty(see Table 2).

Table 2 The MM?model

For F?V(G),letΩ(F)denote the set of syndromes thatcan be produced if F is the setof allfaulty nodes.We say two distinctsubsets F1,F2?V(G)are indistinguishable ifΩ(F1)∩Ω(F2)/=?,and distinguishable otherwise.

For a t1/t1-diagnosable system,Chwa and Hakimi[25] provided necessary and suf fi cientconditions.

Lemma 2Let the graph G=(V,E)be the testing graph of a system S of N units.Then S is pessimistically one-step t1/t1-diagnosable if and only if for any integer p in the range 1≤p≤t1,and for any setof nodes V＇?V, |V＇|=2p,such that|Γ(G,V＇)|≥t1-p+1.

The following resultstates a suf fi cientcondition for the t1/t1-diagnosable system.

Lemma 3[2]A system G=(V,E)is t1/t1-diagnosable underthe pessimistic diagnosis strategy,if for any two distinct subsets F1and F2of V with|F1|≤t1, |F2|≤t1,and|F1∪F2|＞t1,F1and F2are distinguishable.

The following characterization is usefulfor distinguishing two sets under the MM?model.For any two distinct sets F1and F2,F1ΔF2=(F1∪F2)-(F1∩F2).

Lemma 4[11]Letthe graph G=(V,E)be a testing graph underthe MM?model.Forany subsets F1,F2,such that F1,F2?V(G)and F1/=F2,are distinguishable iff there exists a vertex u∈V-(F1∪F2),atleastone ofthe three conditions holds:

3.Main results

In this section,we will show that EH(s,t)(1≤s≤t)is 2s/2s-diagnosable underthe two diagnosis models.To be-

gin with,some notations need to be explained.is a subgraph of EH(s+1,t)where t+1≤r≤t+s(respectively EH(s,t+1)where 1≤r≤t),induced by allvertices whose dimension r is

0(or 1).Forsimplicity we write

as EH0(s,t)(or EH1(s,t)).To prove ourmain results,some lemmas need to be prepared:

Lemma 5For any V＇?V(EH(s,t))(1≤s≤t) with|V＇|=2,|Γ(EH(s,t),V＇)|≥2s.

ProofWe fi rst prove that for any V＇?V(EH(1,t)) (1≤t)with|V＇|=2,|Γ(EH(1,t),V＇)|≥2 by induction on t.Itis easy to check thatitholds for EH(1,1).Suppose thatthe lemma is true for t-1(t≥2).Let V＇={u,v}?V(EH(1,t)).Decompose EH(1,t)into EH0(1,t-1) and EH1(1,t-1)along dimension i,i∈[1,t].Now we consider the following two cases:

Case 1u and v are in the same subgraph.

Without loss of generality,we suppose u,v∈V(EH0(1,t-1)).By the induction hypothesis, |Γ(EH0(1,t-1),V＇)|≥2.Hence|Γ(EH(1,t),V＇)|= |Γ(EH0(1,t-1),V＇)|+|Γ(EH1(1,t-1),V＇)|≥2.

Case 2u and v are notin the same subgraph.

Without loss of generality,we suppose u∈V(EH0(1,t-1),v∈V(EH1(1,t-1)).By the property of the exchanged hypercube,|Γ(EH0(1,t-1),u)|≥2 and|Γ(EH1(1,t-1),v)|≥2.Thus,|Γ(EH(1,t),V＇)|≥|Γ(EH0(1,t-1),u)|+|Γ(EH1(1,t-1),v)|≥2.

Now,we proceed to prove that the lemma is true for EH(s,t)by induction on s.The process of proof is similarwith the prooffor EH(1,t).Forsimplicity,we can omit the detail.

Lemma 6For any V＇?V(EH(2,t))(2≤t),|V＇|≤3, if EH(2,t)-V＇is disconnected,then EH(2,t)-V＇has exactly two components.

ProofWe use induction on t.Forany V＇with|V＇|≤3, itcan be checked that EH(2,2)-V＇has exactly two components if EH(2,2)-V＇is disconnected.Suppose the resultis true for EH(2,t-1)(3≤t).Decompose EH(2,t) into EH0(2,t-1)and EH1(2,t-1)along the dimension i,i∈[1,t].Without loss of generality,we may as-EH0(2,t-1)are both connected by Property 3,which is a contradiction with the disconnectivity of EH(2,t)-V＇.is connected.Since EH(2,t)-V＇is disconnected and EH1connected,EH0(2,t-1)mustbe disconnected.By the induction hypothesis,EH0(2,t-1)has exactly two components.Hence,the disconnected EH(2,t)-V＇has exactly two components.The process of our proof is illustrated in Fig.2.

Fig.2 Proof of Lemma 6

Lemma 7For any V＇?V(EH(s,t))(2≤s≤t), |V＇|≤2s-1,if EH(s,t)-V＇is disconnected,then EH(s,t)-V＇has exactly two components.

ProofWe prove this by induction on s.When s=2, the lemma is clearly true according to Lemma 6.Assume that the lemma is true for s-1(s≥3).Without loss of generality,we may assumeWe deal with two cases separately:

Case 3There exists some dimension i,i∈[t+1,t+s], such that2 by decomposing EH(s,t)along dimension i.

Decompose EH(s,t)into EH0(s-1,t)and EH1(s-

1,t)along this dimension i.From

|V＇|≤2s-1,it follows that≤s-1.By Property 3,EH1(s-1,t)is connected.As EH1(s-1,t)is connected and EH(s,t)-V＇is disconnected,is disconnected.According to the induction hypothesis,has two components.As a result EH(s,t)-V＇has exactly two components.

Case 4Decomposing EH(s,t)along any dimension i

Case 4.1There exists some dimension i,such thatby decomposing EH(s,t)along the dimension i.

Decompose EH(s,t)into EH0(s-1,t)and EH1(s-1, t)along this dimension i.With similar argument of Case 3,we see that EH1(s-1,t)-is connected,≤ 2(s-1)and EH0(s-1,t)-is disconnected.Then we decompose EH0(s-1,t)into EH00(s-1,t-1)and EH01(s-1,t-1)along the dimension j,j∈[1,t],such thatItis easy to see that EH01(s-1,t-1) is connected,EH00(s-1,t-1) is disconnected andBy the induction hypothesis,EH00(s-1,t-1)has two components.As a result EH(s,t)-V＇has two components.

Case 4.2Decomposing EH(s,t)along any dimen-

Afterdecomposing along dimension i and j in Case 4.1, we decompose EH00(s-1,t-1)into EH000(s-1,t-2) and EH001(s-1,t-2)along the dimension k,k/=j,k∈ [1,t],such thatWe can obtain that EH001(s-1,t-2)-nected,EH000(s-1,t-2)-is disconnected andBy the induction hypothesis,has two components.As a result EH(s,t)-V＇has two components.The process of ourproof of Case 4.2 is illustrated in Fig.3.

Fig.3 Proofof Case 4.2 in Lemma 7

Lemma 8For any two distinct sets F1,F2?V(EH(s,t))(1≤s≤t)with|F1|≤2s and|F2|≤2s but|F1∪F2|＞2s,then there exists a node x∈F1ΔF2adjacentto some node y∈/F1∪F2.

ProofBy the conditions,F1∩F2is a proper set of F1and F2,therefore,|F1∩F2|≤2s-1 and |F1ΔF2|≥2.For the sake of contradiction,suppose no nodes in F1ΔF2is adjacentto nodes not in F1∪F2,then Γ(EH(s,t),F1ΔF2)?F1∩F2implying EH(s,t)-F1∩F2is disconnected.Consider the following two cases:

Case 52≤s≤t

By Lemma 7,EH(s,t)-F1∩F2has two components, one is F1ΔF2,the other is EH(s,t)-F1∩F2-F1ΔF2. Since the connectivity of EH(s,t)is s+1,implying that |F1∩F2|≥s+1,and consequently|F1ΔF2|≤2(s-1). Hence|EH(s,t)-F1∩F2-F1ΔF2|≥|EH(s,t)|-|F1∩F2|-|F1ΔF2|=2s+t+1-(2s-1)-(2s-2)≥2. It follows that the super connectivity of the EH(s,t)is κ＇(G)≤|F1∩F2|≤2s-1,a contradiction with Lemma 1.

Case 61=s≤t

In this case,|F1|=2,|F2|=2 and|F1∪F2|＞2.Itfollows that|F1∩F2|=1.Since the connectivity of EH(1,t) is 2,EH(1,t)-F1∩F2is connected,a contradiction.

According to Lemma 8 and Lemma 3 aboutthe diagnosability of a multiprocessor system under the PMC model, we obtain the following results.

Theorem 1EH(s,t)(1≤s≤t)is 2s/2sdiagnosable under the PMC model using the pessimistic one-step diagnosis strategy.

ProofTo the contrary,we suppose that EH(s,t)is not2s/2s-diagnosable.Then,by Lemma 3,there existtwo distinctsets F1and F2with|F1|≤2s and|F2|≤2s but |F1∪F2|＞2s,which are indistinguishable.According to Lemma 8,there exists a node y∈F1ΔF2adjacent to some x/∈F1∪F2.We may assume that y∈F1-F2.Selecta syndromeσ∈Ω(F1)∩Ω(F2).Ifσ(x,y)=0(resp. σ(x,y)=1),then F1(resp.F2)is not an allowable fault setwith respecttoσ,a contradiction.Hence,EH(s,t)is 2s/2s-diagnosable under the PMC model.

Next,we establish diagnosability for EH(s,t)under the MM?model.

Theorem 2EH(s,t)(1≤s≤t)is 2s/2sdiagnosable under the MM?modelusing the pessimistic one-step diagnosis strategy.

ProofTo the contrary,we suppose that EH(s,t)is not 2s/2s-diagnosable.Then there existtwo indistinguishable and distinctsets F1and F2with|F1|≤2s and|F2|≤2s but|F1∪F2|＞2s.By Lemma 8,F1ΔF2has atleast one vertex u adjacentto some vertex w/∈F1∪F2.Denote F3as the setofallsuch vertices w.From Lemma 4,itfollows thatfor any vertex v∈F3,

(i)|N(v)∩(F1-F2)|≤1.

(ii)|N(v)∩(F2-F1)|≤1.

(iii)N(v)?F1∪F2.

We can derive that F3=Γ(EH(s,t),F1ΔF2)-F1∩F2,Γ(EH(s,t),(F1ΔF2)∪F3)?F1∩F2which implies that EH(s,t)-F1∩F2is disconnected.We considerthe following two cases.

Case 72≤s≤t

According to Lemma 7,EH(s,t)-F1∩F2has two components that one is(F1ΔF2)∪F3,the other is EH(s,t)-F1∩F2-(F1ΔF2)∪F3.Itcan be seen that s+1≤|F1∩F2|≤2s-1,2≤|F1ΔF2|≤2(s-1), |F3|≤|N(F1ΔF2)|≤2(s-1)(s+1).Hence,2≤|(F1ΔF2)∪F3|≤2(s-1)+2(s-1)(s+1)=2s2+ 2s-4≥2,and|EH(s,t)-((F1ΔF2)∪F3)-F1∩F2|≥2s+t+1-(2s2+2s-4)-(2s-1)≥2.Itfollows thatthe super connectivity isκ＇(EH(s,t))≤|F1∩F2|≤2s-1, a contradiction with Lemma 1.

Case 81=s≤t

In this case,|F1|=2,|F2|=2 and|F1∪F2|＞2.Itfollows that|F1∩F2|=1.Since the connectivity of EH(1,t) is 2,EH(1,t)-F1∩F2is connected,a contradiction.

4.Conclusions

The exchanged hypercubes have been shown to have some similar and differentproperties compared to hypercubes in [18].The pessimistic diagnosability of the exchanged hypercubes is studied in this paper.It has been shown that the degree ofdiagnosability ofthe EH(s,t)underthe pessimistic one-step t1/t1faultdiagnosis strategy is 2s where 1≤s≤t based on the PMC modeland the MM?model. So far,some properties of the exchanged hypercubes,such as super connectivity,conditional diagnosability,topologicalproperties,and embedding issues,have been studied. Butthey still have many other unknown properties.These properties of the exchanged hypercubes are waiting to revealthemselves to us.

[1]F.P.Preparata,G.Metze,R.T.Chien.On the connection assignment problem of diagnosable systems.IEEE Trans.on Electronic Computers,1967,16(6):848-854.

[2]G.Y.Chang,G.J.Chang,G.H.Chen.Diagnosabilities of regularnetworks.IEEE Trans.on Paralleland Distributed Systems,2005,16(4):314-323.

[3]C.K.Lin,T.L.Kung,J.J.M.Tan.An algorithmic approach to conditional-fault local diagnosis of regular multiprocessor interconnected systems under the PMC model.IEEE Trans.on Computers,2013,62(3):439-451.

[4]C.H.Tsai.A quick pessimistic diagnosis algorithm for hypercube-like multiprocessorsystems underthe PMC model. IEEE Trans.on Computers,2013,62(2):259-267.

[5]S.L.Peng,C.K.Lin,J.J.M.Tan.The g-good-neighbor conditional diagnosability of hypercube under PMC model.Applied Mathematics and Computation,2012,218(21):10406-10412.

[6]N.W.Chang,S.Y.Hsieh.Conditional diagnosability of augmented cubes underthe PMC model.IEEE Trans.on Dependable and Secure Computing,2012,9(1):46-60.

[7]T.K.Li,C.H.Tsai,H.C.Hsu.A fastfault-identi fi cation algorithm for bijective connection graphs using the PMC model. Information Sciences,2012,187:291-297.

[8]A.Kavianpour,K.H.Kim.Diagnosabilities ofhypercubes underthe pessimistic one-step diagnosis strategy.IEEE Trans.on Computers,1991,40(2):232-237.

[9]M.C.Yang.Conditional diagnosability of balanced hypercubes underthe PMC model.Information Sciences,2013,222: 754-760.

[10]J.Maeng,M.Malek.A comparison connection assignmentfor self-diagnosis ofmultiprocessorsystems.Proc.ofDigestofthe International Sympsium on Fault Tolerant Computing,1981: 173-175.

[11]A.Sengupta,A.T.Dahbura.On self-diagnosable multiprocessor systems:diagnosis by the comparison approach.IEEE Trans.on Computers,1992,41(11):1386-1396.

[12]W.S.Hong,S.Y.Hsieh.Strong diagnosability and conditional diagnosability ofaugmented cubes underthe comparison diagnosis model.IEEE Trans.on Reliability,2012,61(1):140-148.

[13]M.C.Yang.Conditional diagnosability of matching composition networks under the MM*model.Information Sciences, 2013,233:230-243.

[14]S.Y.Hsieh,C.Y.Kao.The conditionaldiagnosability ofk-ary n-cubes under the comparison diagnosis model.IEEE Trans. on Computers,2013,62(4):839-843.

[15]A.Kavianpour,A.D.Friedman.Ef fi cient design of easily diagnosable systems.Proc.of the Third USA-Japan Computer Conference,1978:251-257.

[16]A.D.Friedman.A new measure of digital system diagnosis. Proc.of Digest of the International Sympsium on Fault TolerantComputing,1975:167-170.

[17]C.L.Yang,G.M.Masson,R.A.Leonetti.On fault isolation and identi fi cation in t1/t1-diagnosable systems.IEEE Trans. on Computers,1986,100(7):639-643.

[18]P.K.K.Loh,W.J.Hsu,Y.Pan.The exchanged hypercube. IEEE Trans.on Parallel and Distributed Systems,2005,16(9): 866-874.

[19]Y.W.Chen.A commenton“the exchanged hypercube”.IEEE Trans.on Parallel and Distributed Systems,2007,18(4):576-576.

[20]X.J.Li,J.M.Xu.Generalized measures of faulttolerance in exchanged hypercubes.Information Processing Letters,2013, 113(14/15/16):533-537.

[21]M.Ma.The connectivity of exchanged hypercubes.Discrete Mathematics Algorithms and Applications,2010,2(2):213-220.

[22]M.Ma,L.Zhu.The super connectivity of exchanged hypercubes.Information Processing Letters,2011,111(8):360-364.

[23]X.Y.Wang,J.R.Liang,Q.L.Dou.Research on topological properties and embedding issues of the exchanged hypercube. Acta Electronica Sinica,2012,40(4):669-673.(in Chinese) [24]R.J.Trudeau.Introduction to graph theory.New York: Courier Dover Publications,2013.

[25]K.Y.Chwa,S.L.Hakimi.On faultidenti fi cation in diagnosable systems.IEEE Trans.on Computers,1981,100(6):414-422.

Biographies

Jiarong Liang was born in 1966.He received his B.E.degree in mathematics from Central China Normal University in 1991.He furtherreceived his M.S.degree in applied mathematics from Northwest University,China,in 1994 and Ph.D.degree in Institute of Automation from South China University of Technology in 1998.From 2002 to 2003, he was a postdoctoral at Korea Advance Institute of Science and Technology.Currently he is a professor and doctoral supervisor in Schoolof Computer,Electronics and Information,Guangxi University.His research interests include parallel and distributed wireless sensor network and network reliability analysis,and singular controlsystems.He has published over 180 papers in the above areas.

E-mail:gxuliangjr@163.com

Ying Huang was born in 1990.She received her B.E.degree in computer science and technology from Shijiazhuang Tiedao University in 2012.She is currently working towards her M.S.degree in School of Computer,Electronics and Information, Guangxi University.Her research interests focus on paralleland distributed computing and network fault tolerance.

E-mail:huangying11290@126.com

Liangcheng Ye was born in 1988.He received his B.E.degree in computer science and technology from Zhejiang University of Techonlogy in 2011. He is currently working towards his M.S.degree in School of Computer,Electronics and Information, Guangxi University.His research interests include graph theory,network faulttolerance,and faultdiagnosis.

E-mail:yeliangcheng707@qq.com

10.1109/JSEE.2015.00048

Manuscriptreceived April14,2014.

*Corresponding author.

This work was supported by the National Natural Science Fundation of China(61363002).