Reasch On G-good-neighbor Local Fault Diagnosis And T/k-fault Diagnosis Of Regular Networks

With the increasing scale of multiprocessor systems,the risk of processor faults appearing in the system is also increasing,and the impact of faulty processors on the system is obvious.Therefore,ensuring the reliability of the system is becoming more and more important.System-level fault diagnosis can make full use of the capability of the system's own processors for fault diagnosis,which is an efficient and economical way of fault diagnosis,so it has been widely concerned and studied.For system-level fault diagnosis research,this dissertation has done the following work:(1)In the past,system-level fault diagnosis researches mostly focused on the diagnostic characteristics of the whole system,while ignoring important local information about the system.In response to this problem,combined with the latest g-good-neighbor diagnosis theory,a new concept of fault diagnosis-g-good-neighbor local fault diagnosis is proposed,which is used to study the local diagnosis of the system under the g-good-neighbor condition.Using the proposed definition,criteria theorem and properties to study the regular network——hypercube network Qn,the following conclusions are drawn:Under the PMC model,when 0?g?n-3,the g-good-neighbor local diagnosability of Qn at each vertex is at least 2g(n-g+1)-1;when n-2?g?n-1,the g-good-neighbor local diagnosability of Qn at each vertex is 2n-1-1.Further,it is easy to derive the g-good-neighbor conditional diagnosability of Qn.In addition,a corresponding algorithm is proposed for obtaining the g-good-neighbor local diagnosability.(2)The t/k-diagnosis strategy greatly improves the diagnostic capability of the system by allowing at most k fault-free processors to be misdiagnosed as faulty processors.The m-ary n-cube Qnm is a significant and common network topology,which is used as the underlying network in the construction of many distributed memory multiprocessors.Based on these advantages,research on the t/k-diagnosis of Qnm is carried out.According to some lemmas and the criteria condition of t/k-diagnosable,analyzing the structural differences between m-ary n-cube(m?4)and 3-ary n-cube,the following conclusions can be drawn respectively:when m?4,n?2 and 0?k?2n,the t/k-diagnosability of Qnm is 2(k+1)n-1/2(k+1)(k+2)+1;when n?3 and 0?k?n,the t/k-diagnosability of Qn3 is 2(k+1)n-(k+1)(k+2).After comparison,this result is far greater than t-diagnosability and t1/t1-diagnosability of m-ary n-cube.Finally,a t/k-diagnosis algorithm suitable for m-ary n-cube networks is proposed.