Towards Model-Based Diagnosis of Coordination Failures

Abstract

With increasing deployment of multi-agent and distributed systems, there is an increasing need for failure diagnosis sys-tems. While successfully tackling key challenges in multi-agent settings, model-based diagnosis has left open the di-agnosis of coordination failures, where failures often lie in the boundaries between agents, and thus the inputs to the model—with which the diagnoser simulates the system to de-tect discrepancies—are not known. However, it is possible to diagnose such failures using a model of the coordination between agents. This paper formalizes model-based coor-dination diagnosis, using two coordination primitives (con-currence and mutual exclusion). We define the consistency-based and abductive diagnosis problems within this formal-ization, and show that both are NP-Hard by mapping them to other known problems.