Minimization of communication in distributed discrete event systems

In this paper, the problem of minimizing communication in distributed systems is considered in a discrete-event formalism where the system is modeled as a finite-state automaton. There is a set of n communicating agents observing the behavior of the system for purposes of control or diagnosis. A set of communication policies for the agents is said to be minimal if communications cannot be removed without affecting the correctness of the solution. A more general formulation of the communication structure than prior works on this problem is considered. Under an assumption on the absence of cycles (other than self-loops) in the system model, an algorithm that computes a set of minimal communication policies in polynomial-time in the number of states of the system is presented. This is the first algorithm of its kind that achieves this complexity result.