Probabilistic diagnosis of clustered faults for hypercube-based multiprocessor system

Mengjie Lv, Shuming Zhou, Xueli Sun, Guanqin Lian, Jiafei Liu, Dajin Wang

Research output: Contribution to journalArticlepeer-review

4 Scopus citations


As the sizes of multiprocessor systems grow, chances of processors becoming faulty increase, making it an important issue to diagnose faulty nodes in the system. Different models have been proposed and studied. One proposed by Huang et al. employed a probabilistic fault model to determine the status of a cluster of nodes in rectangular grid structures [8]. Later, Tang et al. extended the diagnosis algorithm to more general, regular topologies, in which any pair of adjacent nodes has no common neighbors [25]. In a recent work by Lu et al., the algorithm was further extended to regular topologies where any pair of adjacent nodes has a certain number of common neighbors [18]. In this paper, we extend the threshold to apply the probabilistic diagnosis algorithm for hypercube-based multiprocessor system, and carry out an analysis on the algorithm's effectiveness. The analysis shows a very high rate of correct diagnosis, both for an individual node and for nodes as a whole. Although the analysis is done for a particular regular network (the hypercube), the outcome can serve as a useful reference, and can shed light on the effectiveness of the probabilistic diagnosis for a large group of triangle-free multiprocessor systems.

Original languageEnglish
Pages (from-to)113-131
Number of pages19
JournalTheoretical Computer Science
StatePublished - 12 Nov 2019


  • Clustered faults
  • Diagnosis algorithm
  • Fault tolerance
  • Hypercube
  • Probabilistic diagnosis model
  • Reliability


Dive into the research topics of 'Probabilistic diagnosis of clustered faults for hypercube-based multiprocessor system'. Together they form a unique fingerprint.

Cite this