PEPA Model Theory Of Large Deviations

The stochastic process algebra PEPA is a powerful modeling formalism, through the combination way to describe some concurrent systems, such as distributed computer and mobile communication system, etc. PEPA can be used to derive and analyze the system’s features, e.g. deadlock checking throughput and response time.Underling every PEPA model is a continuous time Markov chain (CTMC). By solving this Markov chain’s steady state probability distribution, we can obtain the average performance measures of this modeling system, such as throughput etc. But this calculation way is limited by the influence of rapid growth of the state space’s scale, so the steady state probability distribution is difficult to be solved out. J. Ding proposed a method in his doctoral thesis to overcome this weak point by using the Markov chain stochastic simulation to derive the performance of the system, and gives a stochastic simulation algorithm to simulate the empirical performance measures of the PEPA model. Since the stochastic simulation will stop after finite steps or iterations, the simulated results are not the precise but an approximate value. In the following work part of J. Ding’s doctoral thesis, he pointed out that the deviation of the simulated value from the real value can be described by the large deviation theory in probability theory. And from the known knowledge of the large deviation, we know that the large deviation theory of Markov chain is mainly to solve the corresponding rate function of this Markov chains. Though the large deviation theory has been applied to the modeling languages such as queuing networks, but to the best of our knowledge, there are very few studies of large deviation theory in the stochastic process algebra field.In this thesis we mainly consider to establish large deviation theory for stochastic process algebra PEPA models, namely, large deviation theory for empirical steady state probability distribution and empirical average performance of PEPA models. In this thesis we introduce the large deviation theory theorem of empirical steady state probability distribution and empirical average performance, we obtain the expression of rate function of steady state probability distribution and average performance in the large deviation theory. Thus we can depict the deviation of the simulated value from the precise value. In addition, we present an example case of a PEPA model for which the model’s performance are analyzed concretely. At first, in Chapter3we derive a CTMC model from this PEPA model, and show the steady state probability distribution and average performance of this model. Then, in Chapter5, by the proving the Theorem5.2.1and Theorem5.1.2, we get the rate function of steady-state probability distribution and average performance respectively.This thesis is organized as the following.In Chapter1, the background, research history about the related works and the origin of our question are introduced and the major works of this thesis are presented.In Chapter2, we devote to introducing PEPA, explaining the state-space explosion problem and point out the methods of quantitative and qualitative analysis for PEPA models.In Chapter3, we present the concepts of performance measure and a simulation algorithm to get performance measures. Then we take a PEPA model as an example to calculate the performance measures, and get the result of the steady state probability distribution and the average performance.In Chapter4, we briefly introduce the large deviation theory of random variables and some basic theorems for large deviations.In Chapter5, we give the large deviation theory of empirical steady-state probability distribution and empirical average performance for PEPA models, then, with a PEPA model as an example to show the large deviation theory, and get rate function of the empirical steady-state probability distribution and empirical average performance.Finally in Chapter6, we will conclude this thesis and propose some future works.