| Popis: |
Processor fault identification in a multiprocessor system plays an important role in reliable computing. The process of identifying faulty processors is called the diagnosis of the system. Several diagnostic models have been proposed, the most popular being the PMC (Preparata, Metze and Chen) diagnostic model proposed in 1967. The precise strategy and the pessimistic strategy are two classical diagnostic strategies based on the PMC model. The precise strategy correctly identifies all faulty nodes. The pessimistic diagnosis strategy isolates all faulty nodes within a set containing at most one fault-free node. General biswapped networks were proposed in 2007 as interconnection networks amenable to implementation using a mix of electronic and optical communication links. The model is inspired by and extended from biswapped networks and OTIS networks. In this paper, we focus on the diagnosabilities of general biswapped networks under the precise and pessimistic strategies based on the PMC diagnostic model. It is proved that the general biswapped network Gbsw(G,H) with @d(G)>=1 and @d(H)>=1 is t-diagnosable and t"1/t"1-diagnosable under the precise and the pessimistic strategies, respectively, where t is the minimum node degree of the network and t"1 is the minimum number of neighbors of any pair of nodes. In addition, a pessimistic diagnosis algorithm for general biswapped networks is proposed and the algorithm can run in O(t"1N) time where N denotes the total number of nodes in the network. |
Full Text from ScienceDirect