Five Performability Algorithms: A Comparison

    Research output: Chapter in Book/Report/Conference proceedingConference contributionAcademicpeer-review

    22 Downloads (Pure)

    Abstract

    Since the introduction by John F. Meyer in 1980, various algorithms have been proposed to evaluate the performability distribution. In this paper we describe and compare five algorithms that have been proposed recently to evaluate this distribution: Picard's method, a uniformisation-based method, a path-exploration method, a discretisation approach and a fully Markovian approximation. As a result of our study, we recommend Picard's method not to be used (due to numerical stability problems). Furthermore, the path exploration method turns out to be heavily dependent on the branching structure of the Markov-reward model under study. For small models, the uniformisation method is preferable; however, its complexity is such that it is impractical for larger models. The discretisation method performs well, also for larger models; however, it does not easily apply in all cases. The recently proposed Markovian approximation works best, even for large models; however, error bounds cannot be given for it.
    Original languageEnglish
    Title of host publicationMAM 2006: Markov Anniversary Meeting
    EditorsAmy N. Langville, William J. Stewart
    Place of PublicationRaleigh, NC, USA
    PublisherBoson Books
    Pages39-54
    Number of pages16
    ISBN (Electronic)1-932482-35-0
    ISBN (Print)1-932482-34-2
    Publication statusPublished - Jun 2006
    EventMAM 2006: Markov Anniversary Meeting: An international conference to celebrate the 150th Anniversary of the birth of A.A. Markov - Charleston, SC, USA, United States
    Duration: 12 Jun 200614 Jun 2006

    Conference

    ConferenceMAM 2006: Markov Anniversary Meeting
    CountryUnited States
    CityCharleston, SC, USA
    Period12/06/0614/06/06

    Fingerprint Dive into the research topics of 'Five Performability Algorithms: A Comparison'. Together they form a unique fingerprint.

  • Cite this

    Cloth, L., & Haverkort, B. R. (2006). Five Performability Algorithms: A Comparison. In A. N. Langville, & W. J. Stewart (Eds.), MAM 2006: Markov Anniversary Meeting (pp. 39-54). Raleigh, NC, USA: Boson Books.