A recurrence-relation-based reward model for performability evaluation of embedded systems

Ann T. Tai, Kam S. Tso, William H Sanders

Research output: Contribution to conferencePaper

Abstract

Embedded systems for closed-loop applications often behave as discrete-time semi-Markov processes (DTSMPs). Performability measures most meaningful to iterative embedded systems, such as accumulated reward, are thus difficult to solve analytically in general. In this paper, we propose a recurrence-relation- based (RRB) reward model to evaluate such measures. A critical element in RRB reward models is the notion of state-entry probability. This notion enables us to utilize the embedded Markov chain in a DTSMP in a novel way. More specifically, we formulate state-entry probabilities, state-occupancy probabilities, and expressions concerning accumulated reward solely in terms of state-entry probability and its companion term, namely the expected accumulated reward at the point of state entry. As a result, recurrence relations abstract away all the intermediate points that lack the memoryless property, enabling a solvable model to be directly built upon the embedded Markov chain. To show the usefulness of RRB reward models, we evaluate an embedded system for which we leverage the proposed notion and methods to solve a variety of probabilistic measures analytically.

Original languageEnglish (US)
Pages532-541
Number of pages10
DOIs
StatePublished - Oct 13 2008
Event2008 International Conference on Dependable Systems and Networks, DSN-2008 - Anchorage, AK, United States
Duration: Jun 24 2008Jun 27 2008

Other

Other2008 International Conference on Dependable Systems and Networks, DSN-2008
CountryUnited States
CityAnchorage, AK
Period6/24/086/27/08

Fingerprint

Embedded systems
Markov processes

ASJC Scopus subject areas

  • Computer Networks and Communications
  • Hardware and Architecture
  • Software

Cite this

Tai, A. T., Tso, K. S., & Sanders, W. H. (2008). A recurrence-relation-based reward model for performability evaluation of embedded systems. 532-541. Paper presented at 2008 International Conference on Dependable Systems and Networks, DSN-2008, Anchorage, AK, United States. https://doi.org/10.1109/DSN.2008.4630124

A recurrence-relation-based reward model for performability evaluation of embedded systems. / Tai, Ann T.; Tso, Kam S.; Sanders, William H.

2008. 532-541 Paper presented at 2008 International Conference on Dependable Systems and Networks, DSN-2008, Anchorage, AK, United States.

Research output: Contribution to conferencePaper

Tai, AT, Tso, KS & Sanders, WH 2008, 'A recurrence-relation-based reward model for performability evaluation of embedded systems', Paper presented at 2008 International Conference on Dependable Systems and Networks, DSN-2008, Anchorage, AK, United States, 6/24/08 - 6/27/08 pp. 532-541. https://doi.org/10.1109/DSN.2008.4630124
Tai AT, Tso KS, Sanders WH. A recurrence-relation-based reward model for performability evaluation of embedded systems. 2008. Paper presented at 2008 International Conference on Dependable Systems and Networks, DSN-2008, Anchorage, AK, United States. https://doi.org/10.1109/DSN.2008.4630124
Tai, Ann T. ; Tso, Kam S. ; Sanders, William H. / A recurrence-relation-based reward model for performability evaluation of embedded systems. Paper presented at 2008 International Conference on Dependable Systems and Networks, DSN-2008, Anchorage, AK, United States.10 p.
@conference{1d092ec6efa44c669266321492d7c56c,
title = "A recurrence-relation-based reward model for performability evaluation of embedded systems",
abstract = "Embedded systems for closed-loop applications often behave as discrete-time semi-Markov processes (DTSMPs). Performability measures most meaningful to iterative embedded systems, such as accumulated reward, are thus difficult to solve analytically in general. In this paper, we propose a recurrence-relation- based (RRB) reward model to evaluate such measures. A critical element in RRB reward models is the notion of state-entry probability. This notion enables us to utilize the embedded Markov chain in a DTSMP in a novel way. More specifically, we formulate state-entry probabilities, state-occupancy probabilities, and expressions concerning accumulated reward solely in terms of state-entry probability and its companion term, namely the expected accumulated reward at the point of state entry. As a result, recurrence relations abstract away all the intermediate points that lack the memoryless property, enabling a solvable model to be directly built upon the embedded Markov chain. To show the usefulness of RRB reward models, we evaluate an embedded system for which we leverage the proposed notion and methods to solve a variety of probabilistic measures analytically.",
author = "Tai, {Ann T.} and Tso, {Kam S.} and Sanders, {William H}",
year = "2008",
month = "10",
day = "13",
doi = "10.1109/DSN.2008.4630124",
language = "English (US)",
pages = "532--541",
note = "2008 International Conference on Dependable Systems and Networks, DSN-2008 ; Conference date: 24-06-2008 Through 27-06-2008",

}

TY - CONF

T1 - A recurrence-relation-based reward model for performability evaluation of embedded systems

AU - Tai, Ann T.

AU - Tso, Kam S.

AU - Sanders, William H

PY - 2008/10/13

Y1 - 2008/10/13

N2 - Embedded systems for closed-loop applications often behave as discrete-time semi-Markov processes (DTSMPs). Performability measures most meaningful to iterative embedded systems, such as accumulated reward, are thus difficult to solve analytically in general. In this paper, we propose a recurrence-relation- based (RRB) reward model to evaluate such measures. A critical element in RRB reward models is the notion of state-entry probability. This notion enables us to utilize the embedded Markov chain in a DTSMP in a novel way. More specifically, we formulate state-entry probabilities, state-occupancy probabilities, and expressions concerning accumulated reward solely in terms of state-entry probability and its companion term, namely the expected accumulated reward at the point of state entry. As a result, recurrence relations abstract away all the intermediate points that lack the memoryless property, enabling a solvable model to be directly built upon the embedded Markov chain. To show the usefulness of RRB reward models, we evaluate an embedded system for which we leverage the proposed notion and methods to solve a variety of probabilistic measures analytically.

AB - Embedded systems for closed-loop applications often behave as discrete-time semi-Markov processes (DTSMPs). Performability measures most meaningful to iterative embedded systems, such as accumulated reward, are thus difficult to solve analytically in general. In this paper, we propose a recurrence-relation- based (RRB) reward model to evaluate such measures. A critical element in RRB reward models is the notion of state-entry probability. This notion enables us to utilize the embedded Markov chain in a DTSMP in a novel way. More specifically, we formulate state-entry probabilities, state-occupancy probabilities, and expressions concerning accumulated reward solely in terms of state-entry probability and its companion term, namely the expected accumulated reward at the point of state entry. As a result, recurrence relations abstract away all the intermediate points that lack the memoryless property, enabling a solvable model to be directly built upon the embedded Markov chain. To show the usefulness of RRB reward models, we evaluate an embedded system for which we leverage the proposed notion and methods to solve a variety of probabilistic measures analytically.

UR - http://www.scopus.com/inward/record.url?scp=53349154061&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=53349154061&partnerID=8YFLogxK

U2 - 10.1109/DSN.2008.4630124

DO - 10.1109/DSN.2008.4630124

M3 - Paper

AN - SCOPUS:53349154061

SP - 532

EP - 541

ER -