Search

Positive systems naturally arise in situations where the model tracks physical quantities. Although the linear case is well understood, analysis and controller design for nonlinear positive systems remain challenging. Model reduction methods can help tame this problem. Here, we propose a notion of model reduction for a class of positive bilinear systems with (bounded) matrix and exogenous controls. Our reduction, called proper positive lumping, aggregates the original system such that states of the corresponding reduced model represent nonnegative linear combinations of original state variables. In this article, we prove a characterization result showing that the reductions by proper positive lumping are exactly those preserving the optimality of a suitable class of value functions. Moreover, we provide an efficient polynomial-time algorithm for the computation of the minimal lumping. We numerically evaluate our approach by applying it to a number of benchmark case studies.

The assumption of perfect knowledge of rate parameters in continuous-time Markov chains (CTMCs) is undermined when confronted with reality, where they may be uncertain due to lack of information or because of measurement noise. Here, we consider uncertain CTMCs (UCTMCs), where rates are assumed to vary nondeterministically with time from bounded continuous intervals. A UCTMC can be, therefore, seen as a specific type of Markov decision process for which the analysis is computationally difficult. To tackle this, we develop a theory of minimization, which generalizes the notion of lumpability for CTMCs. Our first result is a quantitative and logical characterization of minimization. Specifically, we show that the reduced UCTMC model has a macrostate for each block of a partition of the state space, which preserves value functions and logical formulae whenever rewards are equal within each block. The second result is an efficient minimization algorithm for UCTMCs by means of partition refinement. As an application, we show that reductions in a number of CTMC benchmark models are robust with respect to uncertainties in original rates.

It is well known that exact notions of model abstraction and reduction for dynamical systems may not be robust enough in practice because they are highly sensitive to the specific choice of parameters. In this paper we consider this problem for nonlinear ordinary differential equations (ODEs) with polynomial derivatives. We introduce a model reduction technique based on approximate differential equivalence, i.e., a partition of the set of ODE variables that performs an aggregation when the variables are governed by nearby derivatives. We develop algorithms to (i) compute the largest approximate differential equivalence; (ii) construct an approximately reduced model from the original one via an appropriate perturbation of the coefficients of the polynomials; and (iii) provide a formal certificate on the quality of the approximation as an error bound, computed as an over-approximation of the reachable set of the reduced model. Finally, we apply approximate differential equivalences to case studies on electric circuits, biological models, and polymerization reaction networks.

Fluid semantics for Markovian process algebra have recently emerged as a computationally attractive approximate way of reasoning about the behaviour of stochastic models of large-scale systems. This interpretation is particularly convenient when sequential components characterised by small local state spaces are present in many independent copies. While the traditional Markovian interpretation causes state-space explosion, fluid semantics is independent from the multiplicities of the sequential components present in the model, just associating a single ordinary differential equation (ODE) with each local state. In this paper we analyse the case of a process algebra model inducing a large ODE system. Previous work, known as exactfluid lumpability, requires two symmetries: ODE aggregation is possible for processes that i) are isomorphic and that ii) are present with the same multiplicities. We first relax the latter requirement by introducing the notion of ordinaryfluid lumpability, which yields an ODE system where the sum of the aggregated variables is preserved exactly. Then, we consider approximatevariants of both notions of lumpability which make nearby processes symmetric after a perturbation of their parameters. We prove that small perturbations yield nearby differential trajectories. We carry out our study in the context of a process algebra that unifies two synchronisation semantics that are well studied in the literature, useful for the modelling of computer systems and chemical networks, respectively. In both cases, we provide numerical evidence which shows that, in practice, many heterogeneous processes can be aggregated with negligible errors.

In this paper we present a class of nested automata for the modelling of performance, availability, and reliability of software systems with hierarchical structure, which we call systems of systems . Quantitative modelling provides valuable insight into the dynamic behaviour of software systems, allowing non-functional properties such as performance, dependability and availability to be assessed. However, the complexity of many systems challenges the feasibility of this approach as the required mathematical models grow too large to afford computationally efficient solution. In recent years it has been found that in some cases a fluid, or mean field, approximation can provide very good estimates whilst dramatically reducing the computational cost. The systems of systems which we propose are hierarchically arranged automata in which influence may be exerted between siblings, between parents and children, and even from children to parents, allowing a wide range of complex dynamics to be captured. We show that, under mild conditions, systems of systems can be equipped with fluid approximation models which are several orders of magnitude more efficient to run than explicit state representations, whilst providing excellent estimates of performability measures. This is a significant extension of previous fluid approximation results, with valuable applications for software performance modelling. [ABSTRACT FROM AUTHOR]

AbstractManufacturing systems and their control software exhibit a large number of variants, which evolve over time in order to meet changing functional and non-functional requirements. To handle the resulting complexity, we propose a multi-perspective modeling approach with different viewpoints regarding workflow, architecture and component behavior. We combine it with delta modeling to seamlessly capture variability and evolution by the same means on each of the viewpoints. We show how the separation in different viewpoints enables early performance analysis as well as code generation. The approach is illustrated using a case study.

Describing exogenous variability in the resources used by a cloud application leads to stochastic performance models that are difficult to solve. In this paper, we describe the blending algorithm, a novel approximation for queueing network models immersed in a random environment. Random environments are Markov chain-based descriptions of timevarying operational conditions that evolve independently of the system state, therefore they are natural descriptors for exogenous variability in a cloud deployment. The algorithm adopts the principle of solving a separate transient-analysis subproblem for each state of the random environment. Each subproblem is then approximated by a system of ordinary differential equations formulated according to a fluid limit theorem, making the approach scalable and computationally inexpensive. A validation study on several hundred models shows that blending can save up to two orders of magnitude of computational time compared to simulation, enabling efficient exploration of a decision space, which is useful in particular at design-time.

The PEPA Eclipse Plug-in supports the creation and analysis of performance models, from small-scale Markov models to large-scale simulation studies and differential equation systems. Whichever form of analysis is used, models are expressed in a single highlevel language for quantitative modelling, Performance Evaluation Process Algebra (PEPA).

Mean field approximation is a powerful tool to study the performance of large stochastic systems that is known to be exact as the system's size N goes to infinity. Recently, it has been shown that, when one wants to compute expected performance metric in steady-state, mean field approximation can be made more accurate by adding a term in 1/N to the original approximation. This is called the refined mean field approximation in [7]. In this paper, we show how to obtain the same result for the transient regime and we provide a further refinement by expanding the term in 1/N2 (both for transient and steady-state regime). Our derivations are inspired by moment-closure approximation. We provide a number of examples that show this new approximation is usable in practice for systems with up to a few tens of dimensions.

We propose a model-based approach to analysing the performance of mobile applications where physical mobility and state changes are modelled by graph transformations from which a model in the Performance Evaluation Process Algebra (PEPA) is derived. To fight scalability problems with state space generation we adopt a modular solution where the graph transformation system is decomposed into views, for which labelled transition systems (LTS) are generated separately and later synchronised in PEPA.We demonstrate that the result of this modular analysis is equivalent to that of the monolithic approach and evaluate practicality and scalability by means of a case study.

We propose a model-based approach to analysing the performance of mobile applications where physical mobility and state changes are modelled by graph transformations from which a model in the Performance Evaluation Process Algebra (PEPA) is derived. To fight scalability problems with state space generation we adopt a modular solution where the graph transformation system is decomposed into views, for which labelled transition systems (LTS) are generated separately and later synchronised in PEPA. We demonstrate that the result of this modular analysis is equivalent to that of the monolithic approach and evaluate practicality and scalability by means of a case study.