Edinburgh Research Explorer

Contextual Lumpability

Research output: Chapter in Book/Report/Conference proceedingConference contribution

Related Edinburgh Organisations

Open Access permissions

Open

Documents

Original languageEnglish
Title of host publicationProceedings of ValueTools 2013
PublisherICST
Number of pages10
Edition7th
DOIs
Publication statusPublished - 9 Dec 2013
EventValueTools 2013 -- 7th International Conference on Performance Evaluation Methodologies and Tools - Lingotto, Torino, Andorra
Duration: 10 Dec 201312 Dec 2013

Conference

ConferenceValueTools 2013 -- 7th International Conference on Performance Evaluation Methodologies and Tools
CountryAndorra
CityTorino
Period10/12/1312/12/13

Abstract

Quantitative analysis of computer systems is often based on Markovian models. Among the formalisms that are used in practice, Markovian process algebras have found many applications, also thanks to their compositional nature that allows one to specify systems as interacting individual automata that carry out actions. Nevertheless, as with all state-based modelling techniques, Markovian process algebras suer from the well-known state space explosion problem. State aggregation, specifically lumping, is one of the possible methods for tackling this problem. In this paper we revisit the notion of Markovian bisimulation which has previously been shown to induce a lumpable relation in the underlying Markov process. Here we consider the coarser relation of contextual lumpability, and taking the specific example of strong equivalence in PEPA, we propose a slightly relaxed denition of Markovian bisimulation, named lumpable bisimilarity, and prove that this is a characterisation of the notion of contextual lumpability for PEPA components. Moreover, we show that lumpable bisimilarity induces the largest contextual lumping over the Markov process underlying any PEPA component. We provide an algorithm for lumpable bisimilarity and study both its time and space complexity.

    Research areas

  • stochastic process algebra, lumpability, aggregation

Download statistics

No data available

ID: 11873624