Simple Finite-State Fault Detectors for Communication Networks

This paper provides a framework for approaching the problem of fault detection in communication processes. Communication processes are modeled as finite state machines, and our model consists of two FSM's, one observing part of the behavior of the other. We prove that specific classes of faults are detectable, and give a procedure for constructing detectors, but the design of the minimum alphabet detector is NP-Complete. An example applicable to the 802.2 protocol is provided. © 1992 IEEE