Full Text Available
Note: Clicking the button above will open the full text document at the original institutional repository in a new window.
Distributed analysis of Markov chains
Bibliography: leaves 88-91.
Saved in:
| Main Author: | |
|---|---|
| Other Authors: | |
| Format: | Thesis |
| Language: | English |
| Published: |
Department of Computer Science
2014
|
| Subjects: | |
| Tags: |
No Tags, Be the first to tag this record!
|
| _version_ | 1867613181545807872 |
|---|---|
| access_status_str | Open Access |
| author | Mestern, Mark Andrew |
| author2 | Kritzinger, Pieter S |
| author_browse | Kritzinger, Pieter S Mestern, Mark Andrew |
| author_facet | Kritzinger, Pieter S Mestern, Mark Andrew |
| author_sort | Mestern, Mark Andrew |
| collection | Thesis |
| description | Bibliography: leaves 88-91. |
| format | Thesis |
| id | oai:open.uct.ac.za:11427/9693 |
| institution | University of Cape Town (South Africa) |
| language | eng |
| last_indexed | 2026-06-10T12:32:03.909Z |
| license_str | Not specified — see source repository |
| provenance_str_mv | Harvested via OAI-PMH from UCTD — University of Cape Town Open Access Repository |
| publishDate | 2014 |
| publishDateRange | 2014 |
| publishDateSort | 2014 |
| publisher | Department of Computer Science |
| publisherStr | Department of Computer Science |
| record_format | dspace |
| source_str | UCTD — University of Cape Town Open Access Repository |
| spelling | oai:open.uct.ac.za:11427/9693 Distributed analysis of Markov chains Mestern, Mark Andrew Kritzinger, Pieter S Computer Science Bibliography: leaves 88-91. This thesis examines how parallel and distributed algorithms can increase the power of techniques for correctness and performance analysis of concurrent systems. The systems in question are state transition systems from which Markov chains can be derived. Both phases of the analysis pipeline are considered: state space generation from a state transition model to form the Markov chain and finding performance information by solving the steady state equations of the Markov Chain. The state transition models are specified in a general interface language which can describe any Markovian process. The models are not tied to a specific modelling formalism, but common formal description techniques such as generalised stochastic Petri nets and queuing networks can generate these models. Tools for Markov chain analysis face the problem of state Spaces that are so large that they exceed the memory and processing power of a single workstation. This problem is attacked with methods to reduce memory usage, and by dividing the problem between several workstations. A distributed state space generation algorithm was designed and implemented for a local area network of workstations. The state space generation algorithm also includes a probabilistic dynamic hash compaction technique for storing state hash tables, which dramatically reduces memory consumption.- Numerical solution methods for Markov chains are surveyed and two iterative methods, BiCG and BiCGSTAB, were chosen for a parallel implementation to show that this stage of analysis also benefits from a distributed approach. The results from the distributed generation algorithm show a good speed up of the state space generation phase and that the method makes the generation of larger state spaces possible. The distributed methods for the steady state solution also allow larger models to be analysed, but the heavy communications load on the network prevents improved execution time. 2014-11-16T20:07:57Z 2014-11-16T20:07:57Z 1998 Master Thesis Masters MSc http://hdl.handle.net/11427/9693 eng application/pdf Department of Computer Science Faculty of Science University of Cape Town |
| spellingShingle | Computer Science Mestern, Mark Andrew Distributed analysis of Markov chains |
| thesis_degree_str | Master's |
| title | Distributed analysis of Markov chains |
| title_full | Distributed analysis of Markov chains |
| title_fullStr | Distributed analysis of Markov chains |
| title_full_unstemmed | Distributed analysis of Markov chains |
| title_short | Distributed analysis of Markov chains |
| title_sort | distributed analysis of markov chains |
| topic | Computer Science |
| url | http://hdl.handle.net/11427/9693 |
| work_keys_str_mv | AT mesternmarkandrew distributedanalysisofmarkovchains |