Most analysis techniques for discrete-event systems rely on building the system state-transition graphs. A known critical issue is represented by the state-space explosion. One way to face this problem is the exploitation of behavioral symmetries. Well-formed coloured Petri nets (WN) (thanks to their particular syntax) allow the automatic building of a quotient graph, called a symbolic reachability graph (SRG), able to exploit the structural symmetries of systems. The SRG reduction power vanishes when the modeled system evolves in an asymmetric way. Some proposals to enhance the SRG have been shown to be effective only when applied to nearly symmetric systems. A quotient graph, still relying on the WN formalism, is semi-formally introduced; it tries to exploit local symmetries, rather diffuse in real systems. The model of an asymmetric distributed algorithm is used as a running example, a preliminary benchmark for the technique being presented.
A quotient graph for asymmetric distributed systems / C. Bellettini, L. Capra - In: MASCOTS 2004 : proceedings of the twelth IEEE International Symposium on Modeling, Analysis, and Simulation of Computer and Telecommunications Systems : 4-8 october 2004, Volendam, The Netherlands / [a cura di] D. DeGroot, P.G. Harrison. - Los Alamitos : IEEE Computer Society, 2004. - ISBN 0769522513. - pp. 560-568 (( Intervento presentato al 12. convegno International Symposium on Modeling, Analysis, and Simulation of Computer and Telecommunications Systems (MASCOTS) tenutosi a Volendam, The Netherlands nel 2004.
|Titolo:||A quotient graph for asymmetric distributed systems|
BELLETTINI, CARLO NICOLA MARIA (Secondo)
CAPRA, LORENZO (Primo)
|Parole Chiave:||Asymmetric systems; Colored Petri Nets; Quotient state-spaces|
|Settore Scientifico Disciplinare:||Settore INF/01 - Informatica|
|Data di pubblicazione:||2004|
|Enti collegati al convegno:||IEEE Computer Society|
|Digital Object Identifier (DOI):||http://dx.doi.org/10.1109/MASCOT.2004.1348313|
|Tipologia:||Book Part (author)|
|Appare nelle tipologie:||03 - Contributo in volume|