Multiple fault diagnostics for communicating nondeterministic finite state machines

During the last decade, different methods were developed to produce optimized test sequences for detecting faults in communication protocol implementations. However, the application of these methods gives only limited information about the location of detected faults. In this paper, we propose a complementary step, which localizes the faults, once detected. It consists of a generalized diagnostic algorithm for the case where more than one fault may be present in the transitions of a system represented by communicating nondetermistic finite state machines. If existing faults are. detected, this algorithm permits the generation of a minimal set of diagnoses, each of which is formed by a set of transitions suspected of being faulty. A simple example is used to demonstrate the functioning of the proposed diagnostic algorithm. The complexity of each step in the algorithm are calculated.