Pancake graphs: Structural properties and conditional diagnosability

Because of the increasing size of multi-processor systems, processor-fault diagnosis has played critical role in measuring reliability. The diagnosability of numerous well-known multiprocessor systems has been widely investigated. The conditional diagnosability is a new measure of diagnosability by restricting an additional condition under which any fault set cannot contain all the neighbors of any node in a system. This study evaluated the conditional diagnosability for pancake graphs in the PMC model. First, several properties of pancake graphs were derived and, based on these properties, the conditional diagnosability of an n-dimensional pancake graph was shown to be 2 for n = 3 and 8n - 21 for n >= 4.

Automated summary

Due to the growing size of multi-processor systems, processor-fault diagnosis plays a critical role in measuring reliability. This study evaluated the conditional diagnosability of pancake graphs in the PMC model and derived specific numerical results.