Separability and Response Times in Stochastic Models (SPARTACOS)

Lead Research Organisation: Imperial College London
Department Name: Dept of Computing


Quantitative methods are vital for the design of efficient systems: in ICT, communication networks and other logistical areas such as business processes and healthcare systems. However, the resulting models need to be both accessible to the designer, rather than only to the performance specialist, and efficient. A sufficiently expressive formalism is needed that can specify models at a high level of description and also facilitate separable -- and hence efficient -- mathematical solutions. Stochastic process algebra is a formalism that has the potential to meet these requirements and will be applied to system-state probabilities.To date, SPA has not addressed response times, a critical QoS metric, quantile targets of which are set in almost all transaction processing systems and others highly topical at the present time, e.g. the NHS. Separable solutions for (Laplace transforms of) response time density functions in networks will be sought in MPA using reversed processes, analogous to the method of RCAT. In addition, discrete state models are not always the most appropriate: it may be preferable to aggregate many objects of the same type into a single quantity, leading to a continuous state, or fluid model; cf. large numbers of gas molecules represented by a volume. Separable solutions will therefore be sought for both (Laplace transforms of) network response time density functions and for fluid SPA.Four main research areas are identified: theory and development of MPA, with respect to semantics, other formalisms like stochastic Petri-nets and efficient solution methods; algorithms for response time distributions and their moments in complex, single nodes; development of a theory and methodology to analyse response times in networks of interacting nodes; and a parallel theme on fluid process algebraic models.Regarding the first area, it is important to obtain a syntactic mapping from the most general form of MPA suitable for our separability analysis into established formalisms, both process algebraic and other. Application of our MPA formalism will be implemented as computer programs to find both product-forms as well as new, separable, non-product-forms.The study of response times will involve first analysis of single components and then interaction of components in an MPA framework. We will focus on direct methods to obtain the moments, from which often quantiles can also be estimated accurately.These results will be incorporated into networks: to give exact, separable results (analogous to conventional product-forms for state probabilities) in special cases, using reversed processes, and approximate results otherwise.Finally, a PhD student will explore the new area of fluid MPA where models have a continuous (real number) state and so are analysed through coupled differential equations. One objective is to find a separable solution as for state probabilities (above).The theoretical output offers the prospect of a revolutionary new approach to the quantitative design of systems of interacting processes: in ICT, commerce, the environment and perhaps biology through the fluid models. The practical impact will be to endow diverse system design tools with a powerful and efficient performance analysis capability. This will be overseen and disseminated through active collaboration with IBM and Metron Technology, culminating in a workshop to be hosted by IBM at Hursley Park in the final year of the project.


10 25 50
publication icon
Balsamo S (2010) A unifying approach to product-forms in networks with finite capacity constraints in ACM SIGMETRICS Performance Evaluation Review

publication icon
Harrison P (2009) A unified approach to modelling the performance of concurrent systems in Simulation Modelling Practice and Theory

publication icon
Harrison P (2009) Product-forms and functional rates in Performance Evaluation