Abstract:
We consider the fault diagnosis problem: how to use parallel testing rounds to identify which processors in a set are faulty. We prove that 4 rounds suffice when 3% or less of the processors are faulty, and 4 rounds are necessary when any nontrivial constant fraction of the processors are faulty. In addition we prove that 10 rounds suffice when less than half of the processors are faulty, and 5 rounds are necessary when at least 49% of the processors are faulty.