Fault Tolerance Of Large Networks

With the fast increasing demand for large parallel computing,large multiple pro-cessor systems arise.We can model an interconnection as a graph G=(V,E),where the processors can be represented by the vertex set V,and the physical communication links can be represented by the edge set E.The processors in the system can't always be working in normal and stable state.Once there are faulty processors,the whole system might be affected.Therefore,to identify faulty processors is very important to maintain the reliability of a system.The process of identifying faulty nodes from fault-free nodes is called diagnosis of a system.The diagnosability of a system is defined as the maximum number of faulty nodes that the system is guaranteed to identify.There are two frequently used model to determine the diagnosability of a system:the PMC model and the MM*model.The g-good-neighbor conditional faulty set is a special faulty set which guarantee that every fault-free processor has at least g fault-free neighbors.The g-good-neighbor conditional diagnosability is the maximum size of g-good-neighbor conditional faulty set that the system is guaranteed to identify.In this thesis,we study n-dimensional star graph S _n and n-dimensional crossed cube CQ_nto determine their g-good-neighbor conditional diagnosability under the PMC model and the MM*model:1)For n?4 and 0?g?n-2,the g-good-neighbor conditional diagnosability of S_n under both models is t_g(S _n)=(n-g)(g+1)!-1;2)For n?4(PMC model),n?5(MM*model),the g-good-neighbor conditional diagnosability of CQ_n under both models is(?)...