On the diagnosis of Byzantine faults

The class of evidence-based diagnosis algorithms is developed to identify Byzantine (and any other faulty) processors. Such algorithms are said to be fair if they identify no failure-free processor as faulty. This paper makes two significant contributions: (i) it introduces a very general and simple formal model of the evidence-based diagnosis algorithms; and (ii) it derives a simple fair diagnosis algorithm, which is proved optimal for a large class of algorithms. It is further demonstrated that no fair evidence-based diagnosis algorithm can guarantee the identification of all faulty processors (completeness). Several insights into the behavior of the algorithm are presented