We consider the problem of fault diagnosis in multiprocessor systems.
Processors fail with arbitrary probabilities and all failures are independent.
The goal is to identify correctly the status of all processors, based on the set of test results. We give a fast diagnosis algorithm and prove its optimality for arbitrary values of failure probabilities. This is the first time that optimal diagnosis is given for systems without any assumptions on the behavior of faulty processors or on the values of failure probabilities. We show a fast diagnosis which is always locally optimal. We even show examples that it may have arbitrarily small reliability when the number of processors increases, while optimal reliability remains constant.