Correct and almost complete diagnosis of processor grids

A new diagnosis algorithm for square grids is introduced. The algorithm alw ays provides correct diagnosis if the number of faulty processors is below T, a bound with T is an element of Theta (n(2/3)), which was derived by wor st-case analysis. A more effective tool to validate the diagnosis correctne ss is the syndrome dependent bound T-sigma, with T-sigma greater than or eq ual to T, asserted by the diagnosis algorithm itself for every given diagno sis experiment. Simulation studies provided evidence that the diagnosis is complete or almost complete if the number of faults is below T. The fractio n of units which cannot be identified as either faulty or nonfaulty remains relatively small as long as the number of faults is below n/3 and, as long as the number of faults is below n/2, the diagnosis is correct with high p robability.