DIAGNOSABILITY OF CAYLEY GRAPH NETWORKS GENERATED BY TRANSPOSITION TREES UNDER THE COMPARISON DIAGNOSIS MODEL??

Mujiangshan Wang(School of Electrical Engineering&Computer Science, The University of Newcastle NSW 2308,Australia)Shiying Wang(Henan Engineering Laboratory for Big Data Statistical Analysis and Optimal Control, School of Math.andⅠnformation Science,Henan Normal University, Xinxiang,Henan 453007,PR China)

DIAGNOSABILITY OF CAYLEY GRAPH NETWORKS GENERATED BY TRANSPOSITION TREES UNDER THE COMPARISON DIAGNOSIS MODEL??

Mujiangshan Wang?
(School of Electrical Engineering&Computer Science, The University of Newcastle NSW 2308,Australia)
Shiying Wang
(Henan Engineering Laboratory for Big Data Statistical Analysis and Optimal Control, School of Math.andⅠnformation Science,Henan Normal University, Xinxiang,Henan 453007,PR China)

Diagnosability of a multiprocessor system is one important study topic. Cayley graph network Cay (Tn,Sn) generated by transposition trees Tnis one of the attractive underlying topologies for the multiprocessor system.In this paper,it is proved that diagnosability of Cay (Tn,Sn) is n?1 under the comparison diagnosis model for n≥4.

interconnection network;graph;diagnosability;comparison diagnosis model;Cayley graph

2000 Mathematics Subject Classification 05C25

1　Introduction

Many multiprocessor systems take interconnection networks (networks for short) as underlying topologies and a network is usually represented by a graph where vertices represent processors and edges represent communication links between processors.We use graphs and networks interchangeably.For a system,study on the topological properties of its network is important.Furthermore,some processors may fail in studying the system,so processor fault identification plays an important role for reliable computing.The first step to deal with faults is to identify the faulty processors from the testing of the fault-free ones.The identification process is calledthe diagnosis of the system.A system is said to be t-diagnosable if all faulty processors can be identified without replacement,provided that the number of presenting faults does not exceed t.The diagnosability of a system G is the maximum value of t such that G is t-diagnosable[4,5,7,11,19,20].

Several diagnosis models were proposed to identify the faulty processors.One major approach is the PMC diagnosis model introduced by Preparata et al.[13]. The diagnosis of the system was achieved through two linked processors by testing each other.Another important model,namely the comparison diagnosis model (MM model) ,was proposed by Maeng and Malek[12].In the MM model,to diagnose a system,a vertex sends the same task to two of its neighbors,and then compares their responses.Cayley graph network Cay (Tn,Sn) generated by transposition trees Tnis one of the attractive underlying topologies for the multiprocessor system.The star graph and the bubble-sort graph are two special cases of Cay (Tn,Sn) [1].In [18],Zheng et al.proved the n-dimensional star graph is (n?1) -diagnosable under the comparison diagnosis model when n≥4.In[8],Lee and Hsieh proved the ndimensional bubble-sort is (n?1) -diagnosable under the comparison diagnosis model when n≥4.In this paper,the diagnosability of Cay (Tn,Sn) under the comparison diagnosis model is studied.It is proved that Cay (Tn,Sn) is (n?1) -diagnosable under the comparison diagnosis model when n≥4.

2　Preliminaries

2.1The MM?model

In the MM model[12,17],to diagnose a system G,a vertex sends the same task to two of its neighbors,and then compares their responses.To be consistent with the MM model,we have the following assumptions:

a.All faults are permanent.

b.A faulty processor produces incorrect outputs for each of its given tasks.

c.The output of a comparison performed by a faulty processor is unreliable.

d.Two faulty processors given the same input and task do not produce the same output.

The comparison scheme of a system G is modeled as a multigraph,denoted by M (V (G) ,L) ,where L is the labeled-edge set.A labeled edge (u,v)w∈L represents a comparison in which two vertices u and v are compared by a vertex w,which implies uw,vw∈E (G) .The collection of all comparison results in M (V (G) ,L) is called the syndrome,denoted by σ?,of the diagnosis.If the comparison (u,v)wdisagrees, then σ?( (u,v)w) =1;otherwise,σ?( (u,v)w) =0.Hence,a syndrome is a function from L to {0,1} .The MM*model,denoted by M (V (G) ,L?) ,is a special case of theMM model.In the MM*model,all comparisons of G are in the comparison scheme of G,that is,if uw,vw∈E (G) ,then (u,v)w∈L.

2.2Definitions and notations

Given a system G= (V,E) and the comparison scheme M (V (G) ,L) ,for a vertex u∈V,let Xube the set of vertices such that Xu= {v:either uv∈E or (u,v)w∈L} .That is,a vertex in Xuis either linked to u or compared with u by some other vertex.Let Yube the set of edges among vertices of Xu,such that Yu= {vw:v,w∈Xuand (u,v)w∈L} .Define Gu= (Xu,Yu) .

For a graph G= (V,E) ,a subset K of V is called a vertex cover of G if every edge of E has at least one end in K.A vertex cover of minimum cardinality in G is called minimum vertex cover.For a vertex u∈V,the cardinality of a minimum vertex cover of Guis called the order of vertex u.

Denote T (X) to be the set of vertices that are outside of X and are compared with some vertices of X by some vertices of X (Fig.1) .Given G and M (V (G) ,L) , for a subset of vertices X?V,

Figure 1:An example and its T (X) .

2.3Cayley graphs generated by transposition trees

Let Q be a finite group,and S be a spanning set of Q such that S has no identical element.Directed Cayley graph Cay (S,Q) is defined as follows:its vertex set is Q,its arc set is { (g,gs) :g∈Q,s∈S} .Given t∈S,we call every arc in { (g,gt) :g∈Q} a t-arc.If for each s∈S we also have s?1∈S,then we say that this Cayley graph is an undirected Cayley graph.Every Cayley graph in this paper is an undirected Cayley graph.Suppose that every element of S is a transposition.Then the permutation group generated by S is a subgroup of the symmetric group Sn,whose identical element is denoted by (1) .It is easy to see that every undirected Cayley graph is vertex-transitive.The product στ of two permutations is the composition function τ followed by σ,that is, (1,2) (1,3) = (1,3,2) .For terminology and notation not defined here please see[6].The transposition set could be illustrated by a simple graph,and the following concepts are introduced.

Let H be a simple connected graph whose vertex set is {1,2,···,n} (n≥3) . Every edge of H can be considered as a transposition in Sn,and so the edge set of H corresponds to a transposition set S in Sn.In this sense,H is called a transposition simple graph.Cayley graph Cay (S,〈S〉) is called the corresponding Cayley graph of H.By[1],〈S〉=Sn.We denote Cay (S,〈S〉) by Cay (H,Sn) .When the transposition simple graph is a tree,it is called a transposition tree[1].When the transposition simple graph is a path,the corresponding Cayley graph is called a bubble-sort graph[1].When the transposition simple graph is a star,the corresponding Cayley graph is called a star graph[1].

Theorem 2.1[15,16]Let H be a simple connected graph with n=|V (H) |≥3.Ⅰf H1and H2are two different labelled graphs obtained by labelling H with {1,2,···,n} ,then Cay (H1,Sn) is isomorphic to Cay (H2,Sn) .

By Theorem 2.1,a simple connected graph H can be labelled properly.When n≥ 4,Cay (H,Sn) can be decomposed into smaller Cay (S?,Sn?1) ’s as follows, where S?is a spanning set of Sn?1.Given an integer p with 1≤p≤n,let Hibe the subgraph of Cay (H,Sn) induced by vertices with i in the pth position for 1≤i≤n.We say Cay (H,Sn) is decomposed along the pth position.When H is a transposition tree Tn,we assume that one vertex of degree one is labelled by n in Tn. If we decompose Cay (H,Sn) along the last position,then Hiand Cay (Tn?n,Sn?1) are isomorphic.The edges whose end vertices in different Hi’s are the cross-edges with respect to the given decomposition.For graph-theoretical terminology and notation not defined here please see[2].

Lemma 2.1[1]κ (Cay (Tn,Sn) =n?1.

Lemma 2.2[1]For any integer n≥1,Cay (Tn,Sn) is (n?1) -regular and vertex transitive.

2.4Components-composition graphs

Definition 2.1[3]The class of m-dimensional components-composition graphs, denoted by CCGm,is defined recursively as follows:1) CCG1= {K1} .2) Let m≥2 be a positive integer.Given l CCGm?1s G1,G2,···,Gl,where

a connected graph G constructed from G1,G2,···,Glby adding a perfect matching PM inis a graph in CCGm.For convenience,we use the notation PM (G1,G2,···,Gl) to represent such a graph.Note that

2.5 Relationshipbetweencomponents-compositiongraphs and Cayley graphs generated by transposition trees

Let Tnbe a transposition tree and i∈V (Tn) .Adding a new vertex n+1 and an edge i (n+1) to Tn,we obtain a new transposition tree,denoted by Tn+1.

Theorem 2.2Ⅰf Cay (Tn,Sn) ∈CCGn,then Cay (Tn+1,Sn+1) ∈CCGn+1.

Proof We decompose Sn+1along the last position.Let Hibe defined as above. Then Hiand Cay (Tn,Sn) are isomorphic,where i=1,2,···,n+1.It is easy to see that all cross-edges are a perfect matching PM of Cay (Xn+1,Sn+1) .Therefore, Cay (Xn+1,Sn+1) =PM (H1,H2,···,Hn+1) ∈CCGn+1.The proof is completed.

Let Tn(≥3) be a transposition tree and v be a vertex of degree one in Tn.Then Tn? {v} is still a transposition tree.Repeating the above procedures,we can obtain a transposition tree T3.Note that Cay (T3,S3) ∈CCG3.By Theorem 2.2,we have the following theorem.

Theorem 2.3 Cay (Tn,Sn) ∈CCGn.

3 Diagnosability of Cayley Graphs Generated by Transposition Trees under the Comparison Model

In this section,we will give the diagnosability of Cayley graphs generated by transposition trees under the comparison model.

Theorem 3.1[8]Let t≥3 be a positive integer and G1,G2,···,Glbe l components of a CCG G=PM (G1,G2,···,Gl) .Then,G is (t+1) -diagnosable under the MM?model if,for each i∈ {1,2,···,l} ,the following three conditions hold: (1) orderGi(v) ≥t for each vertex v∈V (Gi) ; (2) ν (V (Gi) ) ≥2t;and (3) κ (Gi) ≥t.

Theorem 3.2[10](P.Hall’s theorem) Let G= (U;W) be a bipartite graph.Then G has a matching covering U if and only if

Proposition 3.1 Let n≥3 be a positive integer.Then a vertex of Cay (Tn,Sn) has order n?1.

ProofBy Lemma 2.2,without loss of generality,it is sufficient to check the order for a vertex u= (1) .By the definition of Cay (Tn,Sn)u= (Xu,Yu) ,Xuconsists of those vertices that are either linked to u,denoted by X1,or being compared to u,denoted by X2.So,Xuis the union of two sets X1and X2.The total number of vertices in X1is n?1,and the total number of vertices in X2is at most (n?1) (n?2) . Yuconsists of all edges vw such that w is a comparator of u and v,that is,w is linked to u and v is linked to w.That is,Yu= {vw:w∈X1,v∈X2} .It can be seen that Cay (Tn,Sn)uis a bipartite graph.To find the order of u,we need to find the size of the minimum vertex cover.From the Konig-Egervary theorem,in a bipartite graph,the size of the minimum vertex cover is equal to the size of the maximum matching.A matching is a set of edges of the graph such that no two edges in the set share a common vertex.The matching is maximum if it has the maximum number of edges over all matchings in the graph.

Claim Let v,w∈X1with

In this case,u= (1) ∈N (v) ∩N (w) .Suppose,on the contrary,that|N (v) ∩ N (w) |≥3.Let a,b∈N (v) ∩N (w) withThen uvawu and uvbwu are cycles of length 4.Since u= (1) ,v and w are two transpositions.Let v= (ij) and w= (rt) .Since uvawu is a cycle of length 4,a= (ij) (rt) ,and (ij) and (rt) are disjoint.Thus,b= (ij) (rt) .This contradictsThe proof of this claim is complete.

Theorem 3.3 Cayley graphs Cay (Tn,Sn) generated by transposition trees Tnis (n?1) -diagnosable under the MM?model for n≥4.

Proof By Theorem 2.3,

By Proposition 3.1,orderCay (Tn?1,Sn?1)(v) ≥n?2 for each vertex v∈Sn?1where n≥4.By the definition of Cay (Tn?1,Sn?1) ,By Lemma 2.1,κ (Cay (Tn,Sn) ) =n?2.Thus,by Theorem 3.1 Cay (Tn,Sn) is (n?2) +1= (n?1) -diagnosable for n≥4.The proof is completed.

There are several different ways to characterize a t-diagnosable system under the comparison approach[14].In this study,we use one particular characterization givenin[14]which gives the three sufficient conditions for a system to be t-diagnosable.

Finally,we point out that Cay (T4,S4) is the least Cay (Tn,Sn) satisfying the three sufficient conditions in Theorem 3.1.Because Cay (T3,S3) is isomorphic to the star graph,by[18]Cay (T3,S3) is not 2-diagnosable.

Theorem 3.4[9]Let G= (V,E) be a graph representation of a system,where V represents the processors and E represents their interconnections.Then,d (G) ≤δ (G) under the MM?model.

Theorem 3.5 Diagnosability of Cay (Tn,Sn) is n?1 under the MM?model for n≥4.

Proof By Theorem 3.3,d (Cay (Tn,Sn) ) ≥n?1 for n≥4.Because Cay (Tn,Sn) (n≥1) is regular with the common degree n?1,δ (Cay (Tn,Sn) ) =n?1.By Theorem 3.4,d (Cay (Tn,Sn) ) ≤δ (Cay (Tn,Sn) ) =n?1.Therefore d (Cay (Tn,Sn) ) = n?1 for n≥4.

4　Conclusion

The diagnosability of Cayley graph network Cay (Tn,Sn) generated by transposition trees under the comparison diagnosis model is studied in this paper.Under this model,the system is self-diagnosable if we know the diagnosability of the system. We prove that a system with the Cay (Tn,Sn) structure is (n?1) -diagnosable under the comparison model if n≥4.Based on the result,a polynomial-time algorithm proposed in[14]can be directly used to diagnose the system if there are at most (n?1) faulty processors.The diagnosis involves only one test phase to identify the faulty processors and one repair/replacement phase.Thus it is applicable in the environment that the components are reliable and periodic and quick testings are affordable.Furthermore,the algorithm can be used as a component of a larger diagnosis scheme to perform a given phase of fault location,as opposed to being used as a stand-alone diagnosis tool.

References

[1]S.B.Akers,B.Krishnamurthy,A group-theoretic model for symmetric interconnection networks,ⅠEEE Transactions on Computers,38:4 (1989) ,555-566.

[2]J.A.Bondy,U.S.R.Murty,Graph Theory,Springer,New York,2007.

[3]C.Chen,S.Hsieh, (t,k) -diagnosis for component-composition graphs under the MM* model,ⅠEEE Transactions on Computers,60:12 (2011) ,1704-1717.

[4]A.T.Dahbura,G.M.Masson,An O (n2.5) faulty identification algorithm for diagnosable systems,ⅠEEE Transactions on Computers,33:6 (1984) ,486-492.

[5]J.Fan,Diagnosability of crossed cubes under the comparison diagnosis model,ⅠEEE Transactions on Parallel and Distributed Systems,13:10 (2002) ,1099-1104.

[6]T.W.Hungerford,Algebra,Springer,New York,1974.

[7]P.Lai,J.J.M.Tan,C.Chang,L.Hsu,Conditional diagnosability measures for large multiprocessor systems,ⅠEEE Transactions on Computers,54:2 (2005) ,165-175.

[8]C.Lee,S.Hsieh,Diagnosability of component-composition graphs in the MM?model, ACM Transactions on Design Automation of Electronic Systems 19 (3) ,Article 27.

[9]C.W.Lee and S.Y.Hsieh,Diagnosabiltiy of multiprocessor systems,In Scalable Computing and Communications:Theory and Practice,Wiley,2013.

[10]L.Lov′asz,M.D.Plummer,Matching Theory,Elsevier Science Publishing Company, Inc.,New York,1986.

[11]L.Lin,L.Xu,S.Zhou,Relating the extra connectivity and the conditional diagnosability of regular graphs under the comparison model,Theoretical Computer Science, 618 (2016) ,21-29.

[12]J.Maeng,M.Malek,A comparison connection assignment for self-diagnosis of multiprocessor systems,in:Proceeding of 11th International Symposium on Fault-Tolerant Computing,1981,pp.173-175.

[13]F.P.Preparata,G.Metze,R.T.Chien,On the connection assignment problem of diagnosable systems,ⅠEEE Transactions on Computers,16 (1967) ,448-454.

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

[15]M.Wang,W.Yang,and S.Wang,Conditional matching preclusion number for the Cayley graph on the symmetric group,Acta Math.Appl.Sin. (Chinese Series) , 36:5 (2013) ,813-820.

[16]M.Wang,W.Yang,Y.Guo,S.Wang,Conditional fault tolerance in a class of Cayley graphs,Ⅰnternational Journal of Computer Mathematics,93:1 (2016) ,67-82.

[17]J.Yuan,A.Liu,X.Ma,X.Liu,X.Qin,J.Zhang,The g-good-neighbor conditional diagnosability of k-ary n-cubes under PMC model and MM?,ⅠEEE Transactions on Parallel and Distributed Systems,26 (2015) ,1165-1177.

[18]J.Zheng,S.Latifi,E.Regentova,K.Luo,X.Wu,Diagnosability of star graphs under the comparison diagnosis model,Ⅰnformation Processing Letters,93:1 (2005) ,29-36.

[19]S.Zhou,L.Lin,L.Xu,D.Wang,The t/k-diagnosability of star graph networks,ⅠEEE Transactions on Computers,62:2 (2015) ,547-555.

[20]S.Zhou,J.Xu,Fault diagnosability of arrangement graphs,Ⅰnformation Sciences, 246 (2013) ,177-190.

(edited by Liangwei Huang)

?This work was supported by the National Natural Science Foundation of China (61370001,U1304601) .

?Manuscript March 24,2015;Revised April 27,2016

?.E-mail:wmjsdr@126.com