(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.
|頁（從 - 到）||1280-1298|
|期刊||SIAM Journal on Computing|
|出版狀態||已出版 - 2007|