HOME

TheInfoList



OR:

Performance Evaluation Process Algebra (PEPA) is a
stochastic Stochastic (, ) refers to the property of being well described by a random probability distribution. Although stochasticity and randomness are distinct in that the former refers to a modeling approach and the latter refers to phenomena themselv ...
process algebra In computer science, the process calculi (or process algebras) are a diverse family of related approaches for formally modelling concurrent systems. Process calculi provide a tool for the high-level description of interactions, communications, and ...
designed for modelling computer and communication systems introduced by
Jane Hillston Jane Elizabeth Hillston (born 1963) is British professor of Quantitative research, Quantitative Scientific modelling, Modelling and Head of School in the University of Edinburgh School of Informatics, School of Informatics, University of Edinbur ...
in the 1990s. The language extends classical process algebras such as Milner's CCS and
Hoare Hoare is an English surname derived from Middle English '' hor(e)'' meaning grey- or white-haired. Notable people with the surname include: * Albert Alfred Hoare, known as Bert Hoare (1874–1962), South Australian politician * Des Hoare (born 19 ...
's CSP by introducing probabilistic branching and timing of transitions. Rates are drawn from the
exponential distribution In probability theory and statistics, the exponential distribution is the probability distribution of the time between events in a Poisson point process, i.e., a process in which events occur continuously and independently at a constant average ...
and PEPA models are finite-state and so give rise to a
stochastic process In probability theory and related fields, a stochastic () or random process is a mathematical object usually defined as a family of random variables. Stochastic processes are widely used as mathematical models of systems and phenomena that appea ...
, specifically a
continuous-time Markov process A continuous-time Markov chain (CTMC) is a continuous stochastic process in which, for each state, the process will change state according to an exponential random variable and then move to a different state as specified by the probabilities of ...
(CTMC). Thus the language can be used to study quantitative properties of models of computer and communication systems such as
throughput Network throughput (or just throughput, when in context) refers to the rate of message delivery over a communication channel, such as Ethernet or packet radio, in a communication network. The data that these messages contain may be delivered ov ...
, utilisation and
response time Response time may refer to: *The time lag between an electronic input and the output signal which depends upon the value of passive components used. * Responsiveness, how quickly an interactive system responds to user input * Response time (biolog ...
as well as qualitative properties such as freedom from
deadlock In concurrent computing, deadlock is any situation in which no member of some group of entities can proceed because each waits for another member, including itself, to take action, such as sending a message or, more commonly, releasing a lo ...
. The language is formally defined using a structured
operational semantics Operational semantics is a category of formal programming language semantics in which certain desired properties of a program, such as correctness, safety or security, are verified by constructing proofs from logical statements about its execu ...
in the style invented by
Gordon Plotkin Gordon David Plotkin, (born 9 September 1946) is a theoretical computer scientist in the School of Informatics at the University of Edinburgh. Plotkin is probably best known for his introduction of structural operational semantics (SOS) and hi ...
. As with most process algebras, PEPA is a parsimonious language. It has only four combinators, ''prefix'', ''choice'', ''co-operation'' and ''hiding''. Prefix is the basic building block of a sequential component: the process (''a'', ''r'').''P'' performs activity ''a'' at rate ''r'' before evolving to behave as component ''P''. Choice sets up a competition between two possible alternatives: in the process (''a'', ''r'').''P'' + (''b'', ''s'').''Q'' either ''a'' wins the race (and the process subsequently behaves as ''P'') or ''b'' wins the race (and the process subsequently behaves as ''Q''). The co-operation operator requires the two "co-operands" to join for those activities which are specified in the co-operation set: in the process ''P'' < ''a'', ''b''> ''Q'' the processes ''P'' and ''Q'' must co-operate on activities ''a'' and ''b'', but any other activities may be performed independently. The
reversed compound agent theorem In probability theory, the reversed compound agent theorem (RCAT) is a set of sufficient conditions for a stochastic process expressed in any formalism to have a product form stationary distribution (assuming that the process is stationary). The t ...
gives a set of sufficient conditions for a co-operation to have a
product form stationary distribution In probability theory, a product-form solution is a particularly efficient form of solution for determining some metric of a system with distinct sub-components, where the metric for the collection of components can be written as a product of the ...
. Finally, the process ''P''/ hides the activity ''a'' from view (and prevents other processes from joining with it).


Syntax

Given a set of action names, the set of PEPA processes is defined by the following BNF grammar: :P ::= (a,\lambda).P\,\,\, , \,\,\,P + Q\,\,\, , \,\,\,P\stackrelQ\,\,\, , \,\,\,P/L\,\,\,, \,\,\,A The parts of the syntax are, in the order given above ; action : the process (a,\lambda).P can perform an action ''a'' at rate \lambda and continue as the process ''P''. ; choice : the process ''P+Q'' may behave as either the process ''P'' or the process ''Q''. ; cooperation : processes ''P'' and ''Q'' exist simultaneously and behave independently for actions whose names do not appear in ''L''. For actions whose names appear in ''L'', the action must be carried out jointly and a race condition determines the time this takes. ; hiding : the process ''P'' behaves as usual for action names not in ''L'', and performs a silent action \tau for action names that appear in ''L''. ; process identifier : write A \overset P to use the identifier ''A'' to refer to the process ''P''.


Tools

* PEPA Plug-in for
Eclipse An eclipse is an astronomical event that occurs when an astronomical object or spacecraft is temporarily obscured, by passing into the shadow of another body or by having another body pass between it and the viewer. This alignment of three ce ...
* ipc: the imperial PEPA compiler * GPAnalyser for fluid analysis of massively parallel systems


References


External links


PEPA: Performance Evaluation Process Algebra
{{DEFAULTSORT:PEPA Process calculi Theoretical computer science