Information Technology Reference
In-Depth Information
Performance and dependability evaluation is a discipline that aims at analysing
these quantitative system aspects. Major strands of performance evaluation ap-
proaches are measurement-based and model-based techniques. In
measurement-
based evaluation
, experiments are performed on a concrete (often prototypical)
realisation of the system, and timing information is gathered, which is then
analysed to evaluate measure(s) of interest. These techniques are routinely prac-
ticed in the systems engineering world. They provide specific, precise and very
concrete insights into the functioning of a real system. The drawback of these
approaches is mainly the fact that they are not reproducible, are hard to scale,
and dicult to generalise beyond the concrete setup experimented with. In order
to increase reproducibility and reduce costs of larger experiments, distributed
systems researchers often resort to
emulation
studies, where the real system code
is executed on a virtualised hardware, instead of distributing it physically on the
target systems. This especially allows for better concurrency control and thus
improved reproducibility. However, it remains notoriously unclear to what extent
the imposed control mechanisms tamper the validity of the obtained measures.
In
model-based performance evaluation
, a more general, and thus more ab-
stract approach is taken. A model of the system is constructed that is deemed
just detailed enough to evaluate the measure(s) of interest with the required ac-
curacy. In this context the modelling process is an additional step that needs to
be performed, and this is a non-trivial task. Process calculi [5] provide a formal
basis for designing models of complex systems, especially those involving com-
municating and concurrently executing components. The underlying basis is the
model of labelled transition systems, which represent system behaviour as tran-
sitions representing discrete system moves from state to state. The consideration
of stochastic phenomena has led to a plethora of stochastic process calculi, cf.
the survey in [36]. One of their semantical models is the topic of this paper:
in-
teractive Markov chains
(IMCs, for short) [35]. It stands out in the sense that it
extends classical labeled transition systems in a simple yet conservative fashion.
IMCs arise from classical concurrency models by incorporating a second type of
transitions, denoted
s
s
, that embodies a random delay governed by a nega-
tive exponential distribution with parameter
λ
λ
−−→
∈
R
>
0
. This twists the model to
one that is running on a continuous timeline, and where the execution of actions
is supposed to take no time —unless they can be blocked by the environment.
(This is linked to the notion of maximal progress.) By dropping the new type
of transitions, labeled transition systems are regained in their entirety. By in-
stead dropping the old-fashioned action-labeled transitions, one arrives at one of
the simplest but also most widespread class of performance and dependability
models,
continuous-time Markov chains
(CTMCs). They can be considered as
labeled transition systems, where the transition labels —rates of negative expo-
nential distributions— indicate the speed of the system evolving from one state
to another. Their benefits for stochastic process calculi is summarised in [16].
While this simple combination of LTS and CTMCs was at first viewed as a
rather academic distinction, the last decade has shown and stressed its
importance. First and foremost, IMCs have shown their practical relevance in
