Random and Conditional (t, k)-Diagnosis of Hypercubes

Chia Chen Wei, Sun Yuan Hsieh

Research output: Contribution to journalArticle

Abstract

Under the PMC model, we consider the (t, k)-diagnosability of a hypercube under the random fault model and conditional fault model separately. A system is called random (t, k)-diagnosable [or conditionally (t, k)-diagnosable] if at least k faulty vertices that can be identified in each iteration under the assumption that there is no any restriction on the fault distribution (or every vertex is adjacent to at least one fault-free vertex), provided that there are at most t faulty vertices, where t≥ k. When the remaining number of faulty vertices is lower than k, all of them can be identified. In this paper, under the PMC and random fault models, we show that the sequential t-diagnosis algorithm for hypercubes proposed by [35] can be extended to the (t, k)-diagnosis algorithm for hypercubes, and we show that the n-dimensional hypercubes are randomly ((nn2),n)-diagnosable if n is even, and randomly (2·(n-1n-12),n)-diagnosable if n is odd, where (pq)=p!q!(p-q)!. Moreover, we propose a conditional (t, k)-diagnosis algorithm for hypercubes by using properties of the conditional fault model and show that n-dimensional hypercubes are conditionally ((nn2),2n-2)-diagnosable if n is even, and conditionally (2·(n-1n-12),2n-2)-diagnosable if n is odd. Furthermore, under the PMC model, our results improve the previous best low bounds on t under the random and conditional fault models.

Original languageEnglish
Pages (from-to)625-644
Number of pages20
JournalAlgorithmica
Volume79
Issue number3
DOIs
Publication statusPublished - 2017 Nov 1

All Science Journal Classification (ASJC) codes

  • Computer Science(all)
  • Computer Science Applications
  • Applied Mathematics

Fingerprint Dive into the research topics of 'Random and Conditional (t, k)-Diagnosis of Hypercubes'. Together they form a unique fingerprint.

Cite this