Development and application of an efficient method for the solution of stochastic activity networks with deterministic activities

Persistent Link:
http://hdl.handle.net/10150/282098
Title:
Development and application of an efficient method for the solution of stochastic activity networks with deterministic activities
Author:
Malhis, Luai Mohammed, 1964-
Issue Date:
1996
Publisher:
The University of Arizona.
Rights:
Copyright © is held by the author. Digital access to this material is made possible by the University Libraries, University of Arizona. Further transmission, reproduction or presentation (such as public display or performance) of protected items is prohibited except with permission of the author.
Abstract:
Modeling and evaluation of communication and computing systems is an important undertaking. In many cases, large-scale systems are designed in an ad-hoc manner, with validation (or disappointment regarding) system performance coming only after an implementation is made. This does not need to be the case. Modern modeling tools and techniques can yield accurate performance predictions that can be used in the design process. Stochastic activity networks (SANs), stochastic Petri nets (SPNs) and analytic solution methods permit specification and fast solution of many complex system models. To enhance the modeling power of SANs (SPNs), new steady-state analysis methods have been proposed for SAN (SPN) models that include non-exponential activities (transitions). The underlying stochastic process is a Markov regenerative process (MRP) when at most one non-exponential activity (transition) is enabled in each marking. Time-efficient algorithms for constructing the Markov regenerative process have been developed. However, the space required to solve such models is often extremely large. This largeness is due to the large number of transitions in the MRP. Traditional analysis methods require all these transitions be stored in memory for efficient computation. If the size of available memory is smaller than that needed to store these transitions, a time-efficient computation is impossible using these methods. To use this class of SANs to model real systems, the space complexity of MRP analysis algorithms must be reduced. In this thesis, we propose a new steady-state analysis method that is time and space efficient. The new method takes advantage of the structure of the underlying process to reduce both computation time and required memory. The performance of the proposed method is compared to existing methods using several SAN examples. In addition, the ability to model real systems using SANs that include exponential and deterministic activities is demonstrated by modeling and evaluating the performability of a group communication protocol, called Psync. In particular, we study message stabilization time (the time required for messages to arrive at all hosts) under a wide variety of workload and message loss probabilities. We then use this information to suggest a modification to Psync to reduce message stabilizing time. Another important issue we consider is the dependability modeling and evaluation of fault-tolerant parallel and distributed systems. Because of the inherent component redundancy in such systems, the state space size of the underlying stochastic process is often very large. Reduced base model construction techniques that take advantage of symmetries in the structure of such systems have the potential to avoid this state space growth. We investigate this claim, by considering the application of SANs together with reduced base model construction for the dependability modeling and evaluation of three different systems: a fault-tolerant parallel computing system, a distributed database architecture, and a multiprocessor shared-memory system.
Type:
text; Dissertation-Reproduction (electronic)
Keywords:
Engineering, Electronics and Electrical.; Physics, Electricity and Magnetism.
Degree Name:
Ph.D.
Degree Level:
doctoral
Degree Program:
Graduate College; Electrical and Computer Engineering
Degree Grantor:
University of Arizona
Advisor:
Sanders, William H.

Full metadata record

DC FieldValue Language
dc.language.isoen_USen_US
dc.titleDevelopment and application of an efficient method for the solution of stochastic activity networks with deterministic activitiesen_US
dc.creatorMalhis, Luai Mohammed, 1964-en_US
dc.contributor.authorMalhis, Luai Mohammed, 1964-en_US
dc.date.issued1996en_US
dc.publisherThe University of Arizona.en_US
dc.rightsCopyright © is held by the author. Digital access to this material is made possible by the University Libraries, University of Arizona. Further transmission, reproduction or presentation (such as public display or performance) of protected items is prohibited except with permission of the author.en_US
dc.description.abstractModeling and evaluation of communication and computing systems is an important undertaking. In many cases, large-scale systems are designed in an ad-hoc manner, with validation (or disappointment regarding) system performance coming only after an implementation is made. This does not need to be the case. Modern modeling tools and techniques can yield accurate performance predictions that can be used in the design process. Stochastic activity networks (SANs), stochastic Petri nets (SPNs) and analytic solution methods permit specification and fast solution of many complex system models. To enhance the modeling power of SANs (SPNs), new steady-state analysis methods have been proposed for SAN (SPN) models that include non-exponential activities (transitions). The underlying stochastic process is a Markov regenerative process (MRP) when at most one non-exponential activity (transition) is enabled in each marking. Time-efficient algorithms for constructing the Markov regenerative process have been developed. However, the space required to solve such models is often extremely large. This largeness is due to the large number of transitions in the MRP. Traditional analysis methods require all these transitions be stored in memory for efficient computation. If the size of available memory is smaller than that needed to store these transitions, a time-efficient computation is impossible using these methods. To use this class of SANs to model real systems, the space complexity of MRP analysis algorithms must be reduced. In this thesis, we propose a new steady-state analysis method that is time and space efficient. The new method takes advantage of the structure of the underlying process to reduce both computation time and required memory. The performance of the proposed method is compared to existing methods using several SAN examples. In addition, the ability to model real systems using SANs that include exponential and deterministic activities is demonstrated by modeling and evaluating the performability of a group communication protocol, called Psync. In particular, we study message stabilization time (the time required for messages to arrive at all hosts) under a wide variety of workload and message loss probabilities. We then use this information to suggest a modification to Psync to reduce message stabilizing time. Another important issue we consider is the dependability modeling and evaluation of fault-tolerant parallel and distributed systems. Because of the inherent component redundancy in such systems, the state space size of the underlying stochastic process is often very large. Reduced base model construction techniques that take advantage of symmetries in the structure of such systems have the potential to avoid this state space growth. We investigate this claim, by considering the application of SANs together with reduced base model construction for the dependability modeling and evaluation of three different systems: a fault-tolerant parallel computing system, a distributed database architecture, and a multiprocessor shared-memory system.en_US
dc.typetexten_US
dc.typeDissertation-Reproduction (electronic)en_US
dc.subjectEngineering, Electronics and Electrical.en_US
dc.subjectPhysics, Electricity and Magnetism.en_US
thesis.degree.namePh.D.en_US
thesis.degree.leveldoctoralen_US
thesis.degree.disciplineGraduate Collegeen_US
thesis.degree.disciplineElectrical and Computer Engineeringen_US
thesis.degree.grantorUniversity of Arizonaen_US
dc.contributor.advisorSanders, William H.en_US
dc.identifier.proquest9626500en_US
dc.identifier.bibrecord.b33951883en_US
All Items in UA Campus Repository are protected by copyright, with all rights reserved, unless otherwise indicated.