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