Reflection symmetry detection to reduce the state space of Markovian models

ABSTRACT

A model-based evaluation of a system's design often considers to what degree components need to be available multiple times in order to reach a desired level of availability, reliability or dependability. Multiple components of the same kind then lead to models with regular structures. In stochastic models, especially Markovian models, such regularities have been studied for a long time and are used to establish lumpability results that help to achieve a significant state space reduction and alleviate the effects of the infamous state space explosion problem. In this paper, we introduce a new procedure to identify and reduce Markovian models that are built in a compositional manner based on sharing state variables. This procedure can also detect symmetries based on reflection in spatial models where state variables can commute. The results extend existing work of Obal, McQuinn, and Sanders and will contribute to Möbius, a multi-paradigm, multi-solution framework for the model-based dependability and performance assessment of systems.

REFERENCES

• 1: G. Chiola , C. Dutheillet , G. Franceschinis , S. Haddad, Stochastic Well-Formed Colored Nets and Symmetric Modeling Applications, IEEE Transactions on Computers, v.42 n.11, p.1343-1360, November 1993 [doi>10.1109/12.247838]
• 2: Graham Clark , Tod Courtney , David Daly , Dan Deavours , Salem Derisavi , Jay M. Doyle , William H. Sanders , Patrick Webster, The Möbius Modeling Tool, Proceedings of the 9th international Workshop on Petri Nets and Performance Models (PNPM'01), p.241, September 11-14, 2001
• 3: S. Derisavi. A symbolic algorithm for optimal Markov chain lumping. Lecture Notes in Comp. Sci., 4424:139--154, 2007.
• 4: Salem Derisavi , Holger Hermanns , William H. Sanders, Optimal state-space lumping in Markov chains, Information Processing Letters, v.87 n.6, p.309-315, 30 September 2003 [doi>10.1016/S0020-0190(03)00343-0]
• 5: W. Douglas II Obal , Michael G. McQuinn , William H. Sanders, Detecting and Exploiting Symmetry in Discrete-state Markov Models, Proceedings of the 12th Pacific Rim International Symposium on Dependable Computing, p.26-38, December 18-20, 2006 [doi>10.1109/PRDC.2006.26]
• 6: W. H. Sanders and J. F. Meyer. Reduced base model construction methods for stochastic activity networks. IEEE Journal on Selected Areas in Communications, 9(1):25--36, Jan. 1991.

INDEX TERMS

Primary Classification:
  G. Mathematics of Computing
  G.3 PROBABILITY AND STATISTICS

Additional Classification:
  C. Computer Systems Organization
  C.4 PERFORMANCE OF SYSTEMS

General Terms:
Algorithms, Performance, Reliability

Keywords:
Markovian model, dependable computing, spatial model, state space reduction, symmetry detection