Hybrid PMC (HPMC) fault model and diagnosability of interconnection networks

Abstract

System level diagnosis, an area pioneered by Preparata, Metze and Chien, has been a dominant area of research in the broader area of fault-tolerant computing since the proposition of the PMC model. In this paper, we study the fault diagnosis problem for systems in hybrid fault circumstances where both node and link faults may occur. Under our diagnosis model, a test involves two adjacent processors and the link between them. We propose the definition of consistent faulty pairs and distinguishable faulty pairs. Given an assignment of testing links, we establish necessary and sufficient conditions for distinguishable faulty pairs. Finally, we introduce parameters to measure the fault diagnosis capability of multiprocessor systems under this model and as an application the fault diagnosis capability of hypercubes under this model has been evaluated.

Keywords

• interconnection networks
• pmc model
• hybrid pmc model
• multiprocessor systems
• fault diagnosis
• diagnosability
• graph theory