Deadlock Analysis of Parameterized-Chain Networks
| Autor: | J. G. Thistle, M. H. Zibaeenejad |
|---|---|
| Rok vydání: | 2017 |
| Předmět: |
030213 general clinical medicine
0209 industrial biotechnology Theoretical computer science Computer science Parameterized complexity Ring network 02 engineering and technology Deadlock Network topology Computer Science Applications Undecidable problem 03 medical and health sciences Arbitrarily large 020901 industrial engineering & automation 0302 clinical medicine Dependency graph Control and Systems Engineering Isomorphism Electrical and Electronic Engineering Invariant (mathematics) Finite set |
| Zdroj: | IEEE Transactions on Automatic Control. 62:2064-2070 |
| ISSN: | 1558-2523 0018-9286 |
| DOI: | 10.1109/tac.2016.2596758 |
| Popis: | In areas such as computer software and hardware, manufacturing systems, and transportation, engineers encounter networks with arbitrarily large numbers of isomorphic subprocesses. Parameterized systems provide a framework for modeling such networks. The analysis of parameterized systems is a challenge as some key properties such as nonblocking and deadlock-freedom are undecidable even for the case of a parameterized system with ring topology. Here, we introduce Parameterized-Chain Networks (PCN) for modeling of systems with more generalized topologies, consisting of a finite number of ‘distinguished’ subprocesses, and a finite number of parameterized linear subnetworks. Since deadlock analysis is undecidable, to achieve a tractable subproblem, we limit the behavior of subprocesses of the network using our previously developed mathematical notion, ‘weak invariant simulation.’ We develop a dependency graph for analysis of PCN and show that partial and total deadlocks of the proposed PCN are characterized by full, consistent subgraphs of the dependency graph. We investigate deadlock in a traffic network as an illustrative example. |
| Databáze: | OpenAIRE |
| Externí odkaz: |
|