Conditional diagnosability of arrangement graphs under the PMC model

Limei Lin, Shuming Zhou, Li Xu, Dajin Wang

Research output: Contribution to journalArticlepeer-review

31 Scopus citations


Processor fault diagnosis has played an important role in measuring the reliability of a multiprocessor system, and the diagnosabilities of many well-known multiprocessor systems have been investigated. The conditional diagnosability has been widely accepted as a measure of diagnosability by assuming an additional condition that any fault-set can't contain all the neighbors of any node in a multiprocessor system. This paper considers the conditional diagnosability of an (n, k)-arrangement graph An,k, a flexible interconnection network model for multiprocessor systems, under the classical PMC diagnostic model, and determines that the conditional diagnosability of An,k (k≥2, n≥k+2) is (4k-4)(n-k)-3, which is about four times its traditional diagnosability.

Original languageEnglish
Pages (from-to)79-97
Number of pages19
JournalTheoretical Computer Science
Issue numberC
StatePublished - 2014


  • Arrangement graphs
  • Conditional diagnosability
  • Fault tolerance
  • PMC model
  • System reliability


Dive into the research topics of 'Conditional diagnosability of arrangement graphs under the PMC model'. Together they form a unique fingerprint.

Cite this