The Minimal Representation of the Maximum of Erlang Distributions

Konferenz: MMB 2008 - 14th GI/ITG Conference - Measurement, Modelling and Evalutation of Computer and Communication Systems
31.03.2008 - 02.04.2008 in Dortmund, Germany

Tagungsband: MMB 2008

Seiten: 15Sprache: EnglischTyp: PDF

Persönliche VDE-Mitglieder erhalten auf diesen Artikel 10% Rabatt

Pulungan, Reza; Hermanns, Holger (Department of Computer Science, Saarland University, D-66123, Saarbrücken, Germany)

Analysis of models comprising concurrent stochastic processes leads to state space explosion, just like in many other areas of formal validation. The number of states grows exponentially in the number of involved processes. One of the principal constituents of many such processes is the so-called Erlang distribution, which is particularly well-suited as approximations for fixed delays - with adjustable accuracy. The concurrent execution of Erlang distributions corresponds to their maximum. In this paper, we show that an exponential growth of the Markov chain representation of the maximum of Erlang distributions is inevitable. This is because even its minimal representations grow exponentially.