Skip to main content
U.S. flag

An official website of the United States government

Official websites use .gov
A .gov website belongs to an official government organization in the United States.

Secure .gov websites use HTTPS
A lock ( ) or https:// means you’ve safely connected to the .gov website. Share sensitive information only on official, secure websites.

Using Markov Chain Analysis to Study Dynamic Behaviour in Large-Scale Grid Systems

Published

Author(s)

Christopher E. Dabrowski, Fern Y. Hunt

Abstract

In large-scale grid systems with decentralized control, the interactions of many service providers and consumers will likely lead to emergent global system behaviours that result in unpredictable, often detrimental, outcomes. This possibility argues for developing analytical tools to allow understanding, and prediction, of complex system behaviour in order to ensure availability and reliability of grid computing services. This paper presents an approach for using piece-wise homogeneous Discrete Time Markov chains to provide rapid, potentially scalable, simulation of large-scale grid systems. This approach, previously used in other domains, is used here to model dynamics of large-scale grid systems. In this approach, a Markov chain model of a grid system is first represented in a reduced, compact form. This model can then be perturbed to produce alternative system execution paths and identify scenarios in which system performance is likely to degrade or anomalous behaviours occur. The expeditious generation of these scenarios allows prediction of how a larger system will react to failures or high stress conditions. Though computational effort increases in proportion to the number of paths modelled, this cost is shown to be far less than the cost of using detailed simulation or testbeds. Moreover, cost is unaffected by size of system being modelled, expressed in terms of workload and number of computational resources, and is adaptable to systems that are non-homogenous with respect to time. The paper provides detailed examples of the application of this approach.
Proceedings Title
Proceedings of the 7th Australasian Symposium on Grid Computing and e-Research
Conference Dates
January 20-23, 2009
Conference Location
Wellington, -1
Conference Title
7th Australasian Symposium on Grid Computing and e-Research

Keywords

Grid computing, Perturbation analysis, Discrete Markov chain, Piece-wise homogenous Markov chain.

Citation

Dabrowski, C. and Hunt, F. (2009), Using Markov Chain Analysis to Study Dynamic Behaviour in Large-Scale Grid Systems, Proceedings of the 7th Australasian Symposium on Grid Computing and e-Research, Wellington, -1, [online], https://tsapps.nist.gov/publication/get_pdf.cfm?pub_id=890095 (Accessed June 15, 2021)
Created January 21, 2009, Updated February 19, 2017