The Minimal Representation of the Maximum of Erlang Distributions

Conference: MMB 2008 - 14th GI/ITG Conference - Measurement, Modelling and Evalutation of Computer and Communication Systems
03/31/2008 - 04/02/2008 at Dortmund, Germany

Proceedings: MMB 2008

Pages: 15Language: englishTyp: PDF

Personal VDE Members are entitled to a 10% discount on this title

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

Abstract:
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.