Diagnosable evaluation of DCC linear congruential graphs under the PMC diagnostic model

Abstract: A DCC (disjoint consecutive cycles) linear congruential graph G(F, n) consists of n nodes and is generated by a set of linear functions F with special properties. It was proved that G(F, n) is a 2t-regular graph and has connectivity 2t, where and ( for some integer p). For a multiprocessor system, its diagnosability is critical to measure the performance. In this paper, we study the diagnosability of under the precise and pessimistic diagnosis strategies based on the PMC (Preparata, Metze, and Chien) diagnostic model. It is proved that is 2t-diagnosable and -diagnosable under the two diagnosis strategies, respectively, where and . In addition, the diagnosability of DCC linear congruential graphs is compared with that of BC (bijective connection) graphs. [Copyright &y& Elsevier]