L. Capra (Italy)
Distributed systems, Petri Nets, quotient state-spaces, symmetries
The most useful qualitative/quantitative analysis tech niques for Discrete-Event Dynamic Systems are still state space based. It is well known that similar techniques suf fer from the possible state space combinatorial explosion. An approach to face the problem is the exploitation of be havioral symmetries of systems for building quotient (i.e. reduced) state-transition graphs. Behavioral symmetries can be naturally described using a high-level Petri Net formalism, Well-Formed Coloured Nets (WN). WNs ex ploit symmetries for the automatic generation of a quotient graph, the Symbolic Reachability Graph (SRG). The SRG provides a compact representation of the ordinary state transition graph of the modeled system. Performance anal ysis is possible with the SWN formalism (a stochastic ex tension of WNs), which allows to automatically build a lumped Continuous Time Markov Chain from the SRG. The SRG technique reveals very effective when applied to systems with a high degree of symmetry, but it looses most of its efficacy when considering partially symmetrical sys tems, namely systems mixing a (prevalent) symmetric be havior with some asymmetry. The intuitive explanation is that in WNs (a)symmetries are specified at syntax level as part of the model color (i.e. data) structure, on which the SRG definition relies. A first attempt of adding flexibility to the static symmetry approach (typical of the SRG), based on the very intuitive idea of taking into account asymmetries only when they ac tually take place, has lead to the so-called Extended Sym bolic Reachability Graph (ESRG). The ESRG gives a rep resentation of the system behavior significantly more com pact than the SRG in case of “nearly symmetrical” systems (a restricted class of partially symmetrical systems). The main ESRG limit lies in its reduced capability of capturing more general kinds of symmetries. In the paper the (E)SRG technique is surveyed and is ex tended to caught local symmetries, extremely frequent in real systems. A new high-level reachability graph is intro duced, which reveals more compact than the corresponding (E)SRG for SWN models exhibiting a diffuse asymmetric behavior. The extension retains the basic (E)SRG proper ties.
Important Links:
Go Back
