The Reliability And Diagnosis Of Hypercubes And Exchanged Crossed Cubes

With the widely application of multiprocessor systems,the size of the system is rapidly in-crease.For processor with a limited service life and other effect of different factors,the processor faults are inevitable in a multiprocessor system.And with the increases of the processors number in a multiprocessor system,the probability that some processors in the system fail increases.Therefore,in the process of design and implementation of multi-processor systems,the crucial issues are reliability and availability of these systems.The process of identifying faulty processors is called the diagnosis of the system.The diagnosis of systems plays an important role for the reliability of these systems.In a system,the maximal number of faulty nodes that can be guaranteed to be diagnosed is called the diagnosability of the system.Diagnosability is an important measure of the diagnosis capability of a system.To better measure the diagnosis ability of multiprocessor systems,Zhang et al.introduced a new measure of diagnosabiltiy named h-extra conditional diagnosability,denoted by th(G).They studied the h-extra conditional diagnosability of hypercubes and obtained that:under the PMC model,th(Qn)=(h + 1)n-h-Ch2 when n ? 4 and 0 ? h ? n-4.In this paper,we extend their result by determining the parameter with a wider range of h.And we have that under the PMC model,th(Qn)=kh(Qn)+ h when n-3 ? h ?3n-7,n?9.Under the MM*model,the parameter they determined is not the h-extra conditional diagnosability since it requires more conditions.In this paper,we introduce h-extra k-vertex-restricted diagnosability of a system G,denoted by t(h,k)(G).And we showed that Zhang et al.determined under the MM*model is actually the h-extra[n-1/2]-vertex-restricted diagnosability of hypercubes.Then we extend their result and we have t(h,2n)(Qn)= kh(Qn)+ h when 3?h?n/2-1,n?9.In this paper,we also study the diagnosis of hypercubes.Since when a network is put into use link faults may also happen.It is necessary to study the diagnosis of interconnection networks with both node and link faults.In this paper,we introduce the h-edge tolerance diagnosability of a system G,denoted by teh(G).In a system G,if the faulty edge is not more than h then the maximal number of faulty nodes that can be guaranteed to be identified is called the h-edge tolerance diagnosability of the system G.Obviously,the 0-edge tolerance diagnosability is the traditional diagnosability.We also study the h-edge tolerance diagnod-ability of n-dimensional hypercube under the PMC model and we have teh(Qn)= n-h,where 1 ? h<n,n ? 3.At last,we study the 2-extra connectivity of Exchanged Crossed cubes.Connectivity and edge connectivity have been employed as traditional measures to evaluate the fault tolerance ability of multiprocessor systems.However,it is hardly probable that all of a processor's neighbours are faulty.In order to better measure the fault tolerance ability of multiprocessor systems G,Harary study the conditional connectivity by requiring that the disconnected components of G-F have certain properties,where F is the faulty vertices set of G.The h-extra connectivity introduced by Fabrega and M.A.Fiol is a special case of conditional connectivity.The exchanged crossed cube is a variation of the basic hypercube,and it has the better properties than the hypercube such as smaller diameter,fewer links,lower cost factor and so on.In this paper,we determine the 2-extra connectivity of ECQ(s,t)and obtain k2(ECQ(s,t))= 3s-2 for 3 ? s ? t.