DocumentCode :
3549481
Title :
Lumping matrix diagram representations of Markov models
Author :
Derisavi, Salem ; Kemper, Peter ; Sanders, William H.
Author_Institution :
Coordinated Sci. Lab., Illinois Univ., Urbana, IL, USA
fYear :
2005
fDate :
28 June-1 July 2005
Firstpage :
742
Lastpage :
751
Abstract :
Continuous-time Markov chains (CTMCs) have been used successfully to model the dependability and performability of many systems. Matrix diagrams (MDs) are known to be a space-efficient, symbolic representation of large CTMCs. In this paper, we identify local conditions for exact and ordinary lumpings that allow us to lump MD representations of Markov models in a compositional manner. We propose a lumping algorithm for CTMCs that are represented as MDs that is based on partition refinement, is applied to each level of an MD directly, and results in an MD representation of the lumped CTMC. Our compositional lumping approach is complementary to other known model-level lumping approaches for matrix diagrams. The approach has been implemented, and we demonstrate its efficiency and benefits by evaluating an example model of a tandem multi-processor system with load balancing and failure and repair operations.
Keywords :
Markov processes; fault tolerant computing; matrix algebra; multiprocessing systems; resource allocation; compositional lumping; continuous-time Markov chains; load balancing; matrix diagram; model-level lumping; partition refinement; symbolic representation; tandem multiprocessor system; Algebra; Algorithm design and analysis; Automata; Computational modeling; Computer simulation; Equations; Load management; Partitioning algorithms; Size measurement; Stochastic processes;
fLanguage :
English
Publisher :
ieee
Conference_Titel :
Dependable Systems and Networks, 2005. DSN 2005. Proceedings. International Conference on
Print_ISBN :
0-7695-2282-3
Type :
conf
DOI :
10.1109/DSN.2005.59
Filename :
1467848
Link To Document :
بازگشت