**Paolo Ballarini and András Horváth**

We consider a class of Markov chains modelling concurrent activities with
phase-type (PH) distributed duration. Specifically we focus on systems
whose dynamics is characterised by the parallel execution of a number of
*active* jobs and such that the termination of an active job causes
the remaining active jobs to be restarted from scratch (preemptive restart
policy) or deactivated and can lead to the activation of new jobs. In such
a framework, the state-space can be partitioned into disjoint sets (called
macrostates). Each macrostate represents the parallel execution of the
(currently) active jobs and a transition to another macrostate corresponds
to termination of one of the active job. Models of this kind are subject
to the phenomenon of state space explosion, to an extent which is
proportional both to the level of concurrency (i.e., the number of active
jobs in a macrostate) and to the dimension of the phase-type timing (i.e.,
the number of phases used to model jobs' execution). Although techniques
exist that allow for handling the infinitesimal generator matrix of such
models in a memory efficient manner (e.g., in terms of Kronecker
expressions), classical Markovian analysis remains hindered by the memory
requirements for storing the vector of the steady-state or transient
probabilities.

In this paper we show that a Markov chain satisfying the above assumptions can be analysed by calculations performed on the (small) matrices describing the durations of the jobs without the explicit storage of the (large) vectors of transient of steady state probabilities.