Research Of T/s-diagnosable Strategy Based On Networks System

With the rapid development of multiprocessor systems,the multiprocessor systems based on connection need have the ability of diagnosing the faulty processors?nodes?in the systems.And t/s-diagnosable strategy?the system can isolate all the faulty nodes in the system within a subset of cardinality s provided the number of faulty nodes in the system does not exceed t?is a self-diagnose strategy with high efficiency.According to that there are few research on t/s-diagnosable strategy,therefore,this paper will do a comprehensive research on this strategy and apply them to the practical networks such as hypercube networks and star graph networks.To begin with,this paper proposes the characterization of t/s-diagnosable system?sufficient condition and necessary condition?.Combining the characterization,this paper introduces a method to calculate the diagnosability of t/s-diagnosable strategy for the given networks.And we derive the novel properties of hypercube networks and star graph networks relative to their connection,neighbor nodes and largest component.Combining the calculating method,we prove that for an n-dimensional?n?5?hypercube network,it is(kn-^k?k+1?/2+1)/?kn-^k?k+1?/2?+k-1)-diagnosable,where 2?k?n-2 under both PMC model and MM*model.And for an n-dimensional?n?5?star graph network,it is?kn-??k+2?²?/3?/(kn-^?k+2?2/3+k-2)-diagnosable under both PMC model and MM*model,where 2?k?n-2.Finally,for n-dimensional?n?5?hypercube networks and n-dimensional?n?5?star graph networks,we respectively present an algorithm to diagnose faulty nodes based on t/s-diagnosable strategy which are feasible both under the PMC model and MM*model.And the time complexity of the algorithms are O?n²n?and O?N log₂ N?,where N=n!.Meanwhile,from two aspects of mathematical and computer simulation,we verify that the algorithm is feasible and efficient.