New methodology for calculating distributions of reward accumulated during a finite interval

M. Akber Qureshi, William H Sanders

Research output: Contribution to journalArticlepeer-review


Markov reward models are an important formalism by which to obtain dependability and performability measures of computer systems and networks. In this context, it is particularly important to determine the probability distribution function of the reward accumulated during a finite interval. The interval may correspond to the mission period in a mission-critical system, the time between scheduled maintenances, or a warranty period. In such models, changes in state correspond to changes in system structure (due to faults and repairs), and the reward structure depends on the measure of interest. For example, the reward rates may represent a productivity rate while in that state, if performability is considered, or the binary values zero and one, if interval availability is of interest. This paper presents a new methodology to calculate the distribution of reward accumulated over a finite interval. In particular, we derive recursive expressions for the distribution of reward accumulated given that a particular sequence of state changes occurs during the interval, and we explore paths one at a time. The expressions for conditional accumulated reward are new and are numerically stable. In addition, by exploring paths individually, we avoid the memory growth problems experienced when applying previous approaches to large models. The utility of the methodology is illustrated via application to a realistic fault-tolerant multiprocessor model with over half a million states.

Original languageEnglish (US)
Pages (from-to)116-125
Number of pages10
JournalProceedings - Annual International Conference on Fault-Tolerant Computing
StatePublished - 1996

ASJC Scopus subject areas

  • Hardware and Architecture


Dive into the research topics of 'New methodology for calculating distributions of reward accumulated during a finite interval'. Together they form a unique fingerprint.

Cite this