article

Free access

Aggregation with an error of O(ε²)

Author:

Hendrik VantilborghAuthors Info & Claims

Journal of the ACM (JACM), Volume 32, Issue 1

Pages 162 - 190

https://doi.org/10.1145/2455.214107

Published: 01 January 1985 Publication History

Abstract

An aggregative technique to obtain an improved approximation of the equilibrium vector of a Markov chain with a nearly completely decomposable transition matrix is presented. The technique is demonstrated on a model of a multiprogrammed computer system.

References

[1]

ANDO, A., FISHER, F. M., AND SIMON, H. A.Essays on the Structure of Social Science Models. The M.I.T. Press, Cambridge, Mass., 1963.

[2]

BARD, Y.The VM/370 performance predictor. Comput. Surv. 10 (1978), 333-342.

[3]

CHUNG, K. L.Markov Chains with Stationary Transition Probabilities. 2nd ed. Springer-Verlag, New York, 1967.

[4]

COHEN, J. W.The Single Server Queue. Elsevier North-Holland, New York, 1969.

[5]

COURTOIS, P.-J.On the near-complete-decomposability of networks of queues and of stochastic models of muitiprogramming computing systems. Rep. CMU-CS-72-111, Dept. Computer Science, Carnegie-Mellon Univ., Pittsburgh, Pa., 1971.

[6]

COURTOIS, P.-J.Decomposability, instabilities, and saturation in multiprogramming systems. Commun. ACM 18, 7 (July 1975), 371-377.

[7]

COURTOIS, P.-J.Error analysis in nearly-completely decomposable stochastic systems. Econometrica 43 (1975), 691-709.

[8]

COURTOIS, P.-J.Decomposability with applications to queueing network and computer system analysis. Th6se de Docteur en Sciences Appliqu6es, Facult6 des Sciences Appliqu6es, Universit6 Catholique de Louvain, Louvain-la-Neuve, Belgium, 1976.

[9]

COURTOIS, P.-J.Decomposability. Queueing and Computer System Applications. Academic Press, New York, 1977.

[10]

COURTOIS, P.-J.The error of aggregation. Comments on Zarling's analysis. Rep. R345, M.B.L.E Research Lab., Brussels, Belgium, 1977.

[11]

COtJRTOIS, P.-J. 'Exact aggregation in queueing networks. In Proceedings of the First Meeting of the AFCET-SMF on Applied Mathematics (Palaiseau, France, Sept. 4-8). Tome I. Imprimerie de I' Ecole Polytechnique, Palaiseau, France, 1978, pp. 35-51.

[12]

COURTOIS, P.-J., AND GEORGES, J.An evaluation of the stationary behaviour of computations in multiprogramming computer systems. In Proceedings of the International Computing Symposium (Bonn, Germany, May 21-22). W.D. Itzfeldt, Ed. German Chapter of the ACM, Frankfurt, Germany, 1970, p:p. 174-182.

[13]

COURTOIS, P.-J., AND LOUCHARD G.Approximation of eigencharacteristics in nearly-completely decomposable stochastic systems. Stoch. Processes Appl. 4 (1976), 283-296.

[14]

COURTOIS, P.-J., AND VANTILBORGH, H.A decomposable model of program paging behaviour. Acta Inf. 6 (1976), 251-275.

[15]

GOODWIN, R. M.Dynamical coupling with especial reference to markets having production lags. Econometrica 15 (1947), 181-204.

[16]

KEMENV, J. G., AND SNELL, J. L.Finite Markov Chains. Springer-Verlag, New York, 1976.

[17]

KIMBLETON, S.R.A fast approach to computer performance prediction. Rep. ISI/RR-74-20. USC/Informationld Science institute, 1974.

[18]

LATOUCHE, G., AND LOUCHARD, G.Return times in nearly-completely decomposable stochastic processes. J. Appl. Probab. 15 (1978), 251-267.

[19]

MUNTZ, R. R.Analytic modeling of interactive systems. Proc. IEEE 63 (1975), 946-953.

[20]

PRINGLE, R. M., AND RAYNER, A. A.Generalized Inverse Matrices with Applications to Statistics. Griffin, London, 1971.

[21]

REISER, M., AND SAUER, C. H.Queueing network models: Methods of solution and their program implementation. In Current Trends in Programming Methodology. Volume III. Software Modeling. K. M. Chandy and R. T. Yeh, Ed. Prentice-Hall, Englewood Cliffs, N.J., 1978, pp. 115-167.

[22]

SCHWETMAN, H. D. Hybrid simulation models of computer systems. Commun. ACM 21, 9 (Sept. 1978), 718-723.

[23]

VANTILBORGH, H.Exact aggregation in exponential queueing networks. J. ACM 25, 4, (Oct. 1978), 620-629.

[24]

VANTILBORGH, H. On a taboo quantity. Tech. Note N125, M.B.L.E Research Lab., Brussels, Belgium, 1978.

[25]

VANTILBORGH, H.The error of aggregation. A contribution to the theory of decomposable systems, and applications. Th/~se de Docteur en Sciences Appliqures, Facult6 des Sciences Appliqures, Universit6 Catholique de Louvain, Louvain-la-Neuve, Belgium, 1981.

[26]

VARGA, R. S.Matrix lterative Analysis. Prentice-Hall, Englewood Cliffs, N.J., 1962.

[27]

WILKINSON, J. H.The Algebraic Eigenvalue Problem. Clarendon Press, Oxford, Great Britain, 1965.

[28]

ZARLING, R. L.Numerical solution of nearly decomposable queuing networks. Ph.D. Dissertation, Dept. Computer Science, Univ. North Carolina, Chapel Hill, N.C., 1976.

Cited By

Sledge IPríncipe J(2019)Reduction of Markov Chains Using a Value-of-Information-Based ApproachEntropy10.3390/e2104034921:4(349)Online publication date: 30-Mar-2019
https://doi.org/10.3390/e21040349
Dayar TDayar T(2018)Steady-State AnalysisKronecker Modeling and Analysis of Multidimensional Markovian Systems10.1007/978-3-319-97129-2_6(179-227)Online publication date: 20-Sep-2018
https://doi.org/10.1007/978-3-319-97129-2_6
Silvestrov DSilvestrov SSilvestrov DSilvestrov S(2017)Nonlinearly Perturbed Birth-Death-Type Semi-Markov ProcessesNonlinearly Perturbed Semi-Markov Processes10.1007/978-3-319-60988-1_5(81-106)Online publication date: 7-Sep-2017
https://doi.org/10.1007/978-3-319-60988-1_5
Show More Cited By

Index Terms

Aggregation with an error of O(ε²)

Recommendations

Estimation of Energy Aliasing Error for Nonbandlimited Signals

In this paper, we investigate the problem of approximating a given (not necessarily bandlimited) signal, x( t ), by a (bandlimited) “interpolation” or “sampling” series of the form: {\rm {x}}_{\sigma} (t) \underline{\underline {\Delta}}\sum_{-\infty}^{\...
Aggregation Error in Bayesian Analysis of Reliability Systems

Perfect aggregation in Bayesian system reliability analysis has been shown to be extremely unlikely. In other words, aggregation error is almost inevitable. Consequently, analysts have to deal with the following dilemma: on one hand, an aggregate ...
Error-Sensitive adaptive frame aggregation in 802.11n WLAN
WWIC'10: Proceedings of the 8th international conference on Wired/Wireless Internet Communications

IEEE 802.11n is an emerging standard for high data-rate wireless local area networks (WLAN). Frame aggregation is vital for enhancing its MAC layer efficiency. A large frame size can usually boost network throughput, yet it also causes a high frame-...

Comments

Information & Contributors

Information

Published In

cover image Journal of the ACM

Journal of the ACM Volume 32, Issue 1

Jan. 1985

246 pages

ISSN:0004-5411

EISSN:1557-735X

DOI:10.1145/2455

Issue’s Table of Contents

Copyright © 1985 ACM.

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 01 January 1985

Published in JACM Volume 32, Issue 1

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Qualifiers

Article

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

38
Total Citations
View Citations
472
Total Downloads

Downloads (Last 12 months)66
Downloads (Last 6 weeks)5

Reflects downloads up to 28 Feb 2025

Other Metrics

View Author Metrics

Citations

Cited By

Sledge IPríncipe J(2019)Reduction of Markov Chains Using a Value-of-Information-Based ApproachEntropy10.3390/e2104034921:4(349)Online publication date: 30-Mar-2019
https://doi.org/10.3390/e21040349
Dayar TDayar T(2018)Steady-State AnalysisKronecker Modeling and Analysis of Multidimensional Markovian Systems10.1007/978-3-319-97129-2_6(179-227)Online publication date: 20-Sep-2018
https://doi.org/10.1007/978-3-319-97129-2_6
Silvestrov DSilvestrov SSilvestrov DSilvestrov S(2017)Nonlinearly Perturbed Birth-Death-Type Semi-Markov ProcessesNonlinearly Perturbed Semi-Markov Processes10.1007/978-3-319-60988-1_5(81-106)Online publication date: 7-Sep-2017
https://doi.org/10.1007/978-3-319-60988-1_5
Silvestrov DSilvestrov SSilvestrov DSilvestrov S(2017)Asymptotic Expansions for Stationary Distributions of Nonlinearly Perturbed Semi-Markov ProcessesNonlinearly Perturbed Semi-Markov Processes10.1007/978-3-319-60988-1_4(67-79)Online publication date: 7-Sep-2017
https://doi.org/10.1007/978-3-319-60988-1_4
Silvestrov DSilvestrov SSilvestrov DSilvestrov S(2017)Asymptotic Expansions for Moments of Hitting Times for Nonlinearly Perturbed Semi-Markov ProcessesNonlinearly Perturbed Semi-Markov Processes10.1007/978-3-319-60988-1_3(37-66)Online publication date: 7-Sep-2017
https://doi.org/10.1007/978-3-319-60988-1_3
Silvestrov DSilvestrov SSilvestrov DSilvestrov S(2017)Laurent Asymptotic ExpansionsNonlinearly Perturbed Semi-Markov Processes10.1007/978-3-319-60988-1_2(17-35)Online publication date: 7-Sep-2017
https://doi.org/10.1007/978-3-319-60988-1_2
Silvestrov DSilvestrov SSilvestrov DSilvestrov S(2017)IntroductionNonlinearly Perturbed Semi-Markov Processes10.1007/978-3-319-60988-1_1(1-15)Online publication date: 7-Sep-2017
https://doi.org/10.1007/978-3-319-60988-1_1
Silvestrov DSilvestrov S(2017)Asymptotic Expansions for Stationary Distributions of Perturbed Semi-Markov ProcessesEngineering Mathematics II10.1007/978-3-319-42105-6_10(151-222)Online publication date: 11-Feb-2017
https://doi.org/10.1007/978-3-319-42105-6_10
Louchard GLatouche G(2016)Geometric bounds on iterative approximations for nearly completely decomposable Markov chainsJournal of Applied Probability10.2307/321453827:03(521-529)Online publication date: 14-Jul-2016
https://doi.org/10.2307/3214538
Truffet L(2016)Near Complete Decomposability: Bounding the Error by a Stochastic Comparison MethodAdvances in Applied Probability10.2307/142808729:03(830-855)Online publication date: 1-Jul-2016
https://doi.org/10.2307/1428087
Show More Cited By

View Options

View options

PDF

View or Download as a PDF file.

eReader

View online with eReader.

Login options

Check if you have access through your login credentials or your institution to get full access on this article.

Full Access

Get this Article

Figures

Tables

Media

View Issue’s Table of Contents