Deadlock Analysis of Generalized Parameterized Discrete Event Systems with Ring Topology

Networks with arbitrarily large numbers of isomorphic subprocesses appear in areas such as computer software and hardware, transportation networks and manufacturing systems. Parameterized discrete event systems (PDES) provide a framework for modeling these networks. However, some key properties of these networks, such as nonblocking and deadlock-freedom, are undecidable. In our previous work we introduced a novel mathematical tool, weak invariant simulation, to support deadlock analysis of these networks. We used this simulation relation to define a tractable subclass of parameterized ring networks of isomorphic subprocesses in which all the reachable deadlocked states can be calculated. In this paper, we propose a generalized ring PDES: a ring consisting of a fixed number of ‘distinguished' finite subprocesses alternating with a fixed number of distinct parameterized discrete event systems. This framework allows for modeling of new problems such as production lines which include several machines and buffers. We show that within this framework, deadlock analysis is also decidable. Furthermore, we characterize all the reachable deadlocked states. An examples is given to illustrate the usage of the proposed framework.