Generalised Markovian analysis of timed transition systems

Simple item page
dc.contributor.advisorKritzinger, Pieter Sen_ZA
dc.contributor.authorKnottenbelt, William Johnen_ZA
dc.date.accessioned2015-07-14T09:03:21Z
dc.date.available2015-07-14T09:03:21Z
dc.date.issued1996en_ZA
dc.descriptionBibliography: leaves 149-157.en_ZA
dc.description.abstractThis dissertation concerns. analytical methods for assessing the performance of concurrent systems. More specifically, it focuses on the efficient generation and solution of large Markov chains which are derived from models of unrestricted timed transition systems. Timed transition systems may be described using several high-level formalisms, including Generalised Stochastic Petri nets, queueing networks and Queueing Petri nets. A system modelled with one of these formalisms may be mapped onto a Markov chain through a process known as state space generation. The Markov chain thus generated can then be solved for its steady-state distribution by numerically determining the solution to a large set of sparse linear equations known as the steady-state equations. Existing techniques of state space generation are surveyed and a new space-saving probabilistic dynamic state management technique is proposed and analysed in terms of its reliability and space complexity. State space reduction techniques involving on-the-fly elimination of vanishing states are also considered. Linear equation solvers suitable for solving large sparse sets of linear equations are surveyed, including direct methods, classical iterative methods, Krylov Subspace techniques and decomposition-based techniques. Emphasis is placed on Krylov subspace techniques and the Aggregation-Isolation technique, which is a recent decomposition-based algorithm applicable to solving general Markov chains. Since Markov chains derived from real life models may have very large state spaces, it is desirable to automate the performance analysis sequence. Consequently, the new state management technique and several linear equation solvers have been implemented in the Markov chain analyser DNAmaca. DNAmaca accepts a high-level model description of a timed transition system, generates the state space, derives and solves the steady-state equations and produces performance statistics. DNAmaca is described in detail and examples of timed transition systems which have been analysed with DNAmaca are presented.en_ZA
dc.identifier.apacitationKnottenbelt, W. J. (1996). <i>Generalised Markovian analysis of timed transition systems</i>. (Thesis). University of Cape Town ,Faculty of Science ,Department of Computer Science. Retrieved from http://hdl.handle.net/11427/13525en_ZA
dc.identifier.chicagocitationKnottenbelt, William John. <i>"Generalised Markovian analysis of timed transition systems."</i> Thesis., University of Cape Town ,Faculty of Science ,Department of Computer Science, 1996. http://hdl.handle.net/11427/13525en_ZA
dc.identifier.citationKnottenbelt, W. 1996. Generalised Markovian analysis of timed transition systems. University of Cape Town.en_ZA
dc.identifier.ris TY - Thesis / Dissertation AU - Knottenbelt, William John AB - This dissertation concerns. analytical methods for assessing the performance of concurrent systems. More specifically, it focuses on the efficient generation and solution of large Markov chains which are derived from models of unrestricted timed transition systems. Timed transition systems may be described using several high-level formalisms, including Generalised Stochastic Petri nets, queueing networks and Queueing Petri nets. A system modelled with one of these formalisms may be mapped onto a Markov chain through a process known as state space generation. The Markov chain thus generated can then be solved for its steady-state distribution by numerically determining the solution to a large set of sparse linear equations known as the steady-state equations. Existing techniques of state space generation are surveyed and a new space-saving probabilistic dynamic state management technique is proposed and analysed in terms of its reliability and space complexity. State space reduction techniques involving on-the-fly elimination of vanishing states are also considered. Linear equation solvers suitable for solving large sparse sets of linear equations are surveyed, including direct methods, classical iterative methods, Krylov Subspace techniques and decomposition-based techniques. Emphasis is placed on Krylov subspace techniques and the Aggregation-Isolation technique, which is a recent decomposition-based algorithm applicable to solving general Markov chains. Since Markov chains derived from real life models may have very large state spaces, it is desirable to automate the performance analysis sequence. Consequently, the new state management technique and several linear equation solvers have been implemented in the Markov chain analyser DNAmaca. DNAmaca accepts a high-level model description of a timed transition system, generates the state space, derives and solves the steady-state equations and produces performance statistics. DNAmaca is described in detail and examples of timed transition systems which have been analysed with DNAmaca are presented. DA - 1996 DB - OpenUCT DP - University of Cape Town LK - https://open.uct.ac.za PB - University of Cape Town PY - 1996 T1 - Generalised Markovian analysis of timed transition systems TI - Generalised Markovian analysis of timed transition systems UR - http://hdl.handle.net/11427/13525 ER - en_ZA
dc.identifier.urihttp://hdl.handle.net/11427/13525
dc.identifier.vancouvercitationKnottenbelt WJ. Generalised Markovian analysis of timed transition systems. [Thesis]. University of Cape Town ,Faculty of Science ,Department of Computer Science, 1996 [cited yyyy month dd]. Available from: http://hdl.handle.net/11427/13525en_ZA
dc.language.isoengen_ZA
dc.publisher.departmentDepartment of Computer Scienceen_ZA
dc.publisher.facultyFaculty of Scienceen_ZA
dc.publisher.institutionUniversity of Cape Town
dc.subject.otherComputer Scienceen_ZA
dc.titleGeneralised Markovian analysis of timed transition systemsen_ZA
dc.typeMaster Thesis
dc.type.qualificationlevelMasters
dc.type.qualificationnameMScen_ZA
uct.type.filetypeText
uct.type.filetypeImage
uct.type.publicationResearchen_ZA
uct.type.resourceThesisen_ZA
Files
Original bundle
Now showing 1 - 1 of 1
Thumbnail Image
Name:
thesis_sci_1996_knottenbelt_wj.pdf
Size:
2.68 MB
Format:
Adobe Portable Document Format
Description:
Download
Collections
Masters