×

Some efficient computational algorithms related to phase models. (English) Zbl 0662.65130

This paper develops efficient computational algorithms for some models that utilize phase type distributions. As in other instances, such as matrix-geometric methods, where the PH-distribution lends itself to useful and efficient computational methods, we examine how certain probabilities based on these distributions may be efficiently computed. The examples that we consider include token ring networks, simple multiqueues, and order statistics. By exploiting the geometric nature of PH-densities, it is shown that certain exponential time computations can be reduced to linear time, if recursive algorithms are used. We demonstrate speedup with the aid of a practical example, using a recursive as well as a nonrecursive algorithm, in verifying the stability of a queue on a token ring network.
Reviewer: V.Rego

MSC:

65C99 Probabilistic methods, stochastic differential equations
62G30 Order statistics; empirical distribution functions
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] Coppersmith, D., Winograd, S.: Matrix multiplication via arithmetic progessions. Proceedings of the 19th Annual ACM Symposium on Theory of Computing, pp. 1-6 (1987) · Zbl 0702.65046
[2] Lai, T.L., Robbins, H.: A class of dependent random variables and their maxima. Z. Wahrscheinlichkeitstheorie Verw. Geb. 42, 89-111 (1978) · Zbl 0377.60022 · doi:10.1007/BF00536046
[3] Moore, F.: Computational model of a closed queueing network with exponential servers. IBM J. Res. Develop. 16, 567-572 (1972) · Zbl 0401.68011 · doi:10.1147/rd.166.0567
[4] Neuts, M.F.: Matrix-analytic methods in queueing theory. Eur. J. Operational Res. 15, 2-12 (1984) · Zbl 0525.90046 · doi:10.1016/0377-2217(84)90034-1
[5] Neuts, M.F.: Matrix-geometric solutions in stochastic models: An algorithmic approach. First Ed. Baltimore: The Johns Hopkins University Press 1981 · Zbl 0469.60002
[6] Rego, V.J., Szpankowski, W.: On the quality of approximations for high speed rings. Proceedings of the International Symposium on High Performance Computer Systems, Paris, France, 14-16 December 1987. Gelenbe, E. (ed.) Amsterdam: North Holland, p. 179-193 (1988)
[7] Rego, V.J., Ni, L.M.: Analytic models of cyclic service systems and their application to tokenpassing local networks. IEEE Trans. Comput. 37, 1224-1234 (1988) · doi:10.1109/12.5984
[8] Takagi, H.: Analysis of polling systems, First Ed. M.I.T. Press: Cambridge, MA 1986 · Zbl 0647.01001
[9] Trivedi, K.S.: Probability and statistics with reliability. Queueing, Comput. Sci. Appl. Englewood Cliffs, NJ: Prentice Hall 1982 · Zbl 0513.60001
[10] Williams, A., Bhandiwad, R.: A generating function approach to queueing network analysis of multiprogrammed computers. Networks 6, 1-22 (1976) · Zbl 0328.90032 · doi:10.1002/net.3230060102
[11] Szpankowski, W., Rego, V.J.: Ultimate stability conditions for some multidimensional distributed systems. Purdue CSD-TR 715, October 1987
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.