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