Diagnosis of Communicating Systems: Dealing with Incompleteness and Uncertainty

Abstract

Systems with state, such as simple sequential circuits, can sometimes be modelled at a high-level of abstraction or encapsulated as a single component in order to diagnose their behaviour. However, for distributed systems and complex state machines, such encapsulation may not be appropriate and high-level abstraction may offer insufficient detail for diagnosis. Here state evolution must be dealt with more directly. This paper presents a novel algorithm, called HMDP (Heuristic Model-based Diagnosis of communication Protocols), for device-independent interpretation of observations and diagnosis of communicating agents1 in distributed discrete systems, such as communication networks. A fundamental motivation of the HMDP is to deal with problems of incompleteness and uncertainty of observations, and tractability problems incurred by detailed diagnosis . These problems are addressed by: heuristic and approximate matching and interpretation techniques; an incremental propagation technique; use of temporal information; and reiteration on subsets of conflicts.