($t$,$k$)-Diagnosability of Multiprocessor Systems with Applications to Grids and Tori
Resource
SIAM Journal on Computing, vol. 37, no. 4, pp. 1280-1298
Journal
SIAM Journal on Computing
Pages
1280-1298
Date Issued
2007
Date
2007
Author(s)
Chang G. Y.
Abstract
(t, k)-diagnosis, which is a generalization of sequential diagnosis, requires at least k faulty processors identified and replaced (or repaired) in each iteration provided there are at most t faulty processors, where t ≥ k. This paper suggests lower bounds on the degrees of (t, k)diagnosability of multiprocessor systems under both the PMC and the MM* models. As a consequence, grids and tori of d dimensions are shown to be (Ω(N d/d+1), Ω(d))-diagnosable and (Ω(Nd/d+1), Ω(2d))-diagnosable, respectively, where N is the number of processors. © 2007 Society for Industrial and Applied Mathematics.
Type
journal article
File(s)![Thumbnail Image]()
Loading...
Name
11.pdf
Size
23.39 KB
Format
Adobe PDF
Checksum
(MD5):9ce54c0c0372d588b1fae62bfd51bd22