PEPA
Encyclopedia
Performance Evaluation Process Algebra (PEPA) is a stochastic
process algebra designed for modelling computer and communication systems introduced by Jane Hillston
in the 1990s. The language extends classical process algebras such as Milner
's CCS
and Hoare's CSP
by introducing probabilistic branching and timing of transitions.
Rates are drawn from the exponential distribution
and PEPA models are finite-state and so give rise to a stochastic process
, specifically a continuous-time Markov process (CTMC). Thus the language can be used to study quantitative properties of models of computer and communication systems such as throughput
, utilisation
and response time
as well as qualitative properties such as freedom from deadlock
. The language is formally defined using a structured operational semantics
in the style invented by Gordon Plotkin
.
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. Finally, the process P/{a} hides the activity a from view (and prevents other processes from joining with it).
The parts of the syntax are, in the order given above
action : the process
can perform an action a at rate 
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 indepdendently 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
for action names that appear in L.
process identifier : write
to use the identifier A to refer to the process P.
Stochastic
Stochastic refers to systems whose behaviour is intrinsically non-deterministic. A stochastic process is one whose behavior is non-deterministic, in that a system's subsequent state is determined both by the process's predictable actions and by a random element. However, according to M. Kac and E...
process algebra designed for modelling computer and communication systems introduced by Jane Hillston
Jane Hillston
Jane Hillston is Professor of Quantitative Modelling and an EPSRC Advanced Research Fellow in the School of Informatics, University of Edinburgh, Scotland....
in the 1990s. The language extends classical process algebras such as Milner
Robin Milner
Arthur John Robin Gorell Milner FRS FRSE was a prominent British computer scientist.-Life, education and career:...
's CCS
Calculus of Communicating Systems
The Calculus of Communicating Systems is a process calculus introduced by Robin Milner around 1980 and the title of a book describing the calculus. Its actions model indivisible communications between exactly two participants. The formal language includes primitives for describing parallel...
and Hoare's CSP
Communicating sequential processes
In computer science, Communicating Sequential Processes is a formal language for describing patterns of interaction in concurrent systems. It is a member of the family of mathematical theories of concurrency known as process algebras, or process calculi...
by introducing probabilistic branching and timing of transitions.
Rates are drawn from the exponential distribution
Exponential distribution
In probability theory and statistics, the exponential distribution is a family of continuous probability distributions. It describes the time between events in a Poisson process, i.e...
and PEPA models are finite-state and so give rise to a stochastic process
Stochastic process
In probability theory, a stochastic process , or sometimes random process, is the counterpart to a deterministic process...
, specifically a continuous-time Markov process (CTMC). Thus the language can be used to study quantitative properties of models of computer and communication systems such as throughput
Throughput
In communication networks, such as Ethernet or packet radio, throughput or network throughput is the average rate of successful message delivery over a communication channel. This data may be delivered over a physical or logical link, or pass through a certain network node...
, utilisation
Utilisation
In relation to access to health care services and in the terminology of Aday and Andersen, utilisation reflects the extent to which "potential access" is converted into "realised access" .-References:...
and response time
Response time
In technology, response time is the time a system or functional unit takes to react to a given input.- Data processing :In data processing, the response time perceived by the end user is the interval between the instant at which an operator at a terminal enters a request for a response from a...
as well as qualitative properties such as freedom from deadlock
Deadlock
A deadlock is a situation where in two or more competing actions are each waiting for the other to finish, and thus neither ever does. It is often seen in a paradox like the "chicken or the egg"...
. The language is formally defined using a structured operational semantics
Operational semantics
In computer science, operational semantics is a way to give meaning to computer programs in a mathematically rigorous way. Operational semantics are classified into two categories: structural operational semantics formally describe how the individual steps of a computation take place in a...
in the style invented by Gordon Plotkin
Gordon Plotkin
Gordon D. Plotkin, FRS, FRSE is a Scottish computer scientist.Gordon Plotkin is best-known for his introduction of structural operational semantics and his work on denotational semantics. In particular, his notes on A Structural Approach to Operational Semantics of 1981 were very influential...
.
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. Finally, the process P/{a} hides the activity a from view (and prevents other processes from joining with it).
Syntax
Given a set of action names, the set of CCS processes is defined by the following BNF grammar:The parts of the syntax are, in the order given above
action : the process
can perform an action a at rate 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 indepdendently 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
for action names that appear in L.process identifier : write
to use the identifier A to refer to the process P.