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 journalArticle

Abstract

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
Volume793
DOIs
Publication statusPublished - 12 Nov 2019

    Fingerprint

Keywords

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

Cite this