Compositional solution of stochastic process algebra models
type: CreativeWork
description: This dissertation is about the solution of Markovian stochastic process algebra (SPA) models and the avoidance of the state-space explosion problem. We try to answer the question whether the compositionality of SPA models can be exploited to overcome the largeness problems appearing when evaluating such models. First, instead of a global view, we take up a local view, i.e. we focus on components of SPA models, and derive some general results about the relation between components. We identify waiting times, throughputs, and branching probabilities as the three quantities that should be known for a compositional performance evaluation strategy. Then, we consider a special class of SPA processes that describe semi-Markov processes. SPA processes in this class are suitable to be solved by a very efficient new technique. An important step in applying this technique is the computation of the mean value of the maximum of phase-type distributed random variables. A naive approach for a computation would require exponential space, but we present an efficient algorithm of polynomial complexity in time and space in the number of considered random variables. Finally, we consider a true-concurrency semantics for SPA models and investigate its use for an efficient solution of SPA models. We identify three important quantities to express performance measures in this semantics. Unfortunately, as we will show, only for very restricted cases the true-concurrency-view on SPA models allows the actual computation of measures.
abstract: This dissertation is about the solution of Markovian stochastic process algebra (SPA) models and the avoidance of the state-space explosion problem. We try to answer the question whether the compositionality of SPA models can be exploited to overcome the largeness problems appearing when evaluating such models. First, instead of a global view, we take up a local view, i.e. we focus on components of SPA models, and derive some general results about the relation between components. We identify waiting times, throughputs, and branching probabilities as the three quantities that should be known for a compositional performance evaluation strategy. Then, we consider a special class of SPA processes that describe semi-Markov processes. SPA processes in this class are suitable to be solved by a very efficient new technique. An important step in applying this technique is the computation of the mean value of the maximum of phase-type distributed random variables. A naive approach for a computation would require exponential space, but we present an efficient algorithm of polynomial complexity in time and space in the number of considered random variables. Finally, we consider a true-concurrency semantics for SPA models and investigate its use for an efficient solution of SPA models. We identify three important quantities to express performance measures in this semantics. Unfortunately, as we will show, only for very restricted cases the true-concurrency-view on SPA models allows the actual computation of measures.
author: Bohnenkamp, Henrik
language: eng
keywords: info:eu-repo/classification/ddc/004, Informatik
date published: 2002
date modified: 2026-07-30T19:43:10Z
provider: RWTH Aachen University
publisher: Networked Digital Library of Theses and Dissertations
type: WebPage
source organization: Publikationsserver der RWTH Aachen University