Five Performability Algorithms: A Comparison

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

    38 Downloads (Pure)


    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
    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


    ConferenceMAM 2006: Markov Anniversary Meeting
    Country/TerritoryUnited States
    CityCharleston, SC, USA


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

    Cite this