The H-extra Conditional Diagnosability Of Two Class Of Interconnection Networks Under The PMC Model

Fault diagnosis of multiprocessor system mainly depends on testing each other processors to identify the fault processors,so as to guarantee the reliability and stability of the system.Because the topology structure of multiprocessor systems is a graph,the properties of interconnection networks are directly impact on the structural performance of multiprocessor systems.The h-extra conditional diagnosability is an important parameter to measure the reliability of multiprocessor system and able to measure evaluate the reliability of interconnection network better compared with the traditional diagnosability.So this paper selects Burnt pancake networks and Bijective connection networks as the research objects,for their favourable structure properties,and explores the h-extra conditional diagnosability of the two networks under the PMC model respectively.The main work is summarized as follows:First,this paper proved the 3-extra connectivity of Burnt pancake networks.By the definition and topological structures of Burnt pancake networks,we explored the 3-extra connectivity of Burnt Pancake networks on the basis of the results by Zhou Shuming that the {1,2}-extra connectivity of Burnt Pancake networks,and got the accurate value of the3-extra connectivity of Burnt Pancake networks.Secondly,this paper researched from the topological structure of Burnt Pancake networks to get a part of the minimum boundary number,and explored the of monotonicity of the minimum boundary number function.Then we adopt the constructing method and the contradiction to proof the h-extra connectivity of Burnt Pancake networks when the h increased.The results showed that the(h-1)-extra connectivity of Burnt Pancake networks was equal to its' h-minimum boundary number when the h was not more than 6 and the dimension of the networks was not less than 8.Thirdly,this paper explored the h-extra conditional diagnosability of Burnt pancake networks under the PMC model through a series of lemmas,and got the result that the h-extra conditional diagnosability of Burnt pancake networks under the PMC model was equal to the sum of the h-extra connectivity of Burnt Pancake networks and the h,where h was not more than 6 and the dimension of the networks was not less than 8.Fourthly,this paper explored the h-extra connectivity and the h-extra edge connectivity of Bijective connection networks,and got the result that the(h-1)-extra connectivity and the(h-1)-extra edge connectivity of Bijective connection networks were equal to the h-minimum boundary number and the h-minimum boundary edge number respectively,where h was not more than 3 and the dimension of the networks was not less than 6.Fifthly,this paper explored the h-extra conditional diagnosability of a more complex network,Bijective connection networks,under the PMC model,and got the result that the h-extra conditional diagnosability of Bijective connection networks was equal to the sum of the h-extra connectivity of Bijective connection and the h,where h was not more than 3 and the dimension of the networks was not less than 6.