( t , k )-Diagnosability of Multiprocessor Systems with Applications to Grids and Tori

(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+1), Ω(d))-diagnosable and (Ω(Nᵈ/d+1), Ω(2d))-diagnosable, respectively, where N is the number of processors.