A Protocol for Multi-Agent Diagnosis with Spatially Distributed Knowledge

In a large distributed system it is often infeasible or even impossible to perform diagnosis using a single model of the whole system. Instead, several spatially distributed local models of the system have to be used to detect possible faults. Traditional diagnostic tools, however, are not suitable to deal with such a set of spatially distributed local models. A Multi-Agent System of diagnostic agents, where each agent has a model of a subsystem, may be proposed as a solution for establishing global diagnoses of large distributed systems. Unfortunately, establishing a global minimal diagnosis is NP-Hard, even if every agent is able to determine local minimal diagnoses in polynomial time. Moreover, communication overhead in establishing a global diagnosis will be high: unless P = NP a super-polynomial number of messages between the agents will be required for establishing a global diagnosis. In this paper we present a protocol that overcomes this complexity issue by exchanging diagnostic precision for enables agents to determine local minimal diagnoses that are consistent with global diagnoses. Moreover, the protocol ensures that no agent acquires knowledge of global diagnoses. The protocol does not guarantee that a combination of the agents' local minimal diagnoses is also a global minimal diagnosis. However, for every global minimal diagnosis, there is a combination of local minimal diagnoses.