Lumping matrix diagram representations of markov models

Salem Derisavi, Peter Kemper, William H. Sanders

Research output: Contribution to conferencePaper

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.

Original languageEnglish (US)
Pages742-751
Number of pages10
DOIs
StatePublished - Nov 9 2005
Event2005 International Conference on Dependable Systems and Networks - Yokohama, Japan
Duration: Jun 28 2005Jul 1 2005

Other

Other2005 International Conference on Dependable Systems and Networks
CountryJapan
CityYokohama
Period6/28/057/1/05

Fingerprint

Markov processes
Resource allocation
Repair

ASJC Scopus subject areas

  • Software
  • Hardware and Architecture
  • Computer Networks and Communications

Cite this

Derisavi, S., Kemper, P., & Sanders, W. H. (2005). Lumping matrix diagram representations of markov models. 742-751. Paper presented at 2005 International Conference on Dependable Systems and Networks, Yokohama, Japan. https://doi.org/10.1109/DSN.2005.59

Lumping matrix diagram representations of markov models. / Derisavi, Salem; Kemper, Peter; Sanders, William H.

2005. 742-751 Paper presented at 2005 International Conference on Dependable Systems and Networks, Yokohama, Japan.

Research output: Contribution to conferencePaper

Derisavi, S, Kemper, P & Sanders, WH 2005, 'Lumping matrix diagram representations of markov models', Paper presented at 2005 International Conference on Dependable Systems and Networks, Yokohama, Japan, 6/28/05 - 7/1/05 pp. 742-751. https://doi.org/10.1109/DSN.2005.59
Derisavi S, Kemper P, Sanders WH. Lumping matrix diagram representations of markov models. 2005. Paper presented at 2005 International Conference on Dependable Systems and Networks, Yokohama, Japan. https://doi.org/10.1109/DSN.2005.59
Derisavi, Salem ; Kemper, Peter ; Sanders, William H. / Lumping matrix diagram representations of markov models. Paper presented at 2005 International Conference on Dependable Systems and Networks, Yokohama, Japan.10 p.
@conference{6bba2433bc5147ee9cce8edf0704ad38,
title = "Lumping matrix diagram representations of markov models",
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.",
author = "Salem Derisavi and Peter Kemper and Sanders, {William H.}",
year = "2005",
month = "11",
day = "9",
doi = "10.1109/DSN.2005.59",
language = "English (US)",
pages = "742--751",
note = "2005 International Conference on Dependable Systems and Networks ; Conference date: 28-06-2005 Through 01-07-2005",

}

TY - CONF

T1 - Lumping matrix diagram representations of markov models

AU - Derisavi, Salem

AU - Kemper, Peter

AU - Sanders, William H.

PY - 2005/11/9

Y1 - 2005/11/9

N2 - 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.

AB - 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.

UR - http://www.scopus.com/inward/record.url?scp=27544467971&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=27544467971&partnerID=8YFLogxK

U2 - 10.1109/DSN.2005.59

DO - 10.1109/DSN.2005.59

M3 - Paper

AN - SCOPUS:27544467971

SP - 742

EP - 751

ER -