View in EDS

Performance measure sensitive congruences for Markovian process algebras

Saved in:
Bibliographic Details
Title: Performance measure sensitive congruences for Markovian process algebras
Authors: Bernardo, Marco1 bernardo@di.unito.it, Bravetti, Mario2
Source: Theoretical Computer Science. Jan2003, Vol. 290 Issue 1, p117. 44p.
Subjects: Algebra, Markov processes, Algorithms
Abstract: The modeling and analysis experience with process algebras has shown the necessity of extending them with priority, probabilistic internal/external choice, and time while preserving compositionality. The purpose of this paper is to make a further step by introducing a way to express performance measures, in order to allow the modeler to capture the QoS metrics of interest. We show that the standard technique of expressing stationary and transient performance measures as weighted sums of state probabilities and transition frequencies can be imported in the process algebra framework. Technically speaking, if we denote by n ∈ N the number of performance measures of interest, in this paper we define a family of extended Markovian process algebras with generative master–reactive slaves synchronization mechanism called EMPAgrn including probabilities, priorities, exponentially distributed durations, and sequences of rewards of length n. Then we show that the Markovian bisimulation equivalence ∼MBn is a congruence for EMPAgrn which preserves the specified performance measures and we give a sound and complete axiomatization for finite EMPAgrn terms. Finally, we present a case study conducted with the software tool TwoTowers in which we contrast the average performance of a selection of distributed algorithms for mutual exclusion modeled with EMPAgrn. [Copyright &y& Elsevier]
Copyright of Theoretical Computer Science is the property of Elsevier B.V. and its content may not be copied or emailed to multiple sites without the copyright holder's express written permission. Additionally, content may not be used with any artificial intelligence tools or machine learning technologies. However, users may print, download, or email articles for individual use. This abstract may be abridged. No warranty is given about the accuracy of the copy. Users should refer to the original published version of the material for the full abstract. (Copyright applies to all Abstracts.)
Database: Engineering Source
FullText Text:
  Availability: 0
Header DbId: egs
DbLabel: Engineering Source
An: 7911582
AccessLevel: 6
PubType: Academic Journal
PubTypeId: academicJournal
PreciseRelevancyScore: 0
IllustrationInfo
Items – Name: Title
  Label: Title
  Group: Ti
  Data: Performance measure sensitive congruences for Markovian process algebras
– Name: Author
  Label: Authors
  Group: Au
  Data: <searchLink fieldCode="AR" term="%22Bernardo%2C+Marco%22">Bernardo, Marco</searchLink><relatesTo>1</relatesTo><i> bernardo@di.unito.it</i><br /><searchLink fieldCode="AR" term="%22Bravetti%2C+Mario%22">Bravetti, Mario</searchLink><relatesTo>2</relatesTo>
– Name: TitleSource
  Label: Source
  Group: Src
  Data: <searchLink fieldCode="JN" term="%22Theoretical+Computer+Science%22">Theoretical Computer Science</searchLink>. Jan2003, Vol. 290 Issue 1, p117. 44p.
– Name: Subject
  Label: Subjects
  Group: Su
  Data: <searchLink fieldCode="DE" term="%22Algebra%22">Algebra</searchLink><br /><searchLink fieldCode="DE" term="%22Markov+processes%22">Markov processes</searchLink><br /><searchLink fieldCode="DE" term="%22Algorithms%22">Algorithms</searchLink>
– Name: Abstract
  Label: Abstract
  Group: Ab
  Data: The modeling and analysis experience with process algebras has shown the necessity of extending them with priority, probabilistic internal/external choice, and time while preserving compositionality. The purpose of this paper is to make a further step by introducing a way to express performance measures, in order to allow the modeler to capture the QoS metrics of interest. We show that the standard technique of expressing stationary and transient performance measures as weighted sums of state probabilities and transition frequencies can be imported in the process algebra framework. Technically speaking, if we denote by <f>n ∈ N</f> the number of performance measures of interest, in this paper we define a family of extended Markovian process algebras with generative master–reactive slaves synchronization mechanism called <f>EMPAgrn</f> including probabilities, priorities, exponentially distributed durations, and sequences of rewards of length <f>n</f>. Then we show that the Markovian bisimulation equivalence <f>∼MBn</f> is a congruence for <f>EMPAgrn</f> which preserves the specified performance measures and we give a sound and complete axiomatization for finite <f>EMPAgrn</f> terms. Finally, we present a case study conducted with the software tool TwoTowers in which we contrast the average performance of a selection of distributed algorithms for mutual exclusion modeled with <f>EMPAgrn</f>. [Copyright &y& Elsevier]
– Name: AbstractSuppliedCopyright
  Label:
  Group: Ab
  Data: <i>Copyright of Theoretical Computer Science is the property of Elsevier B.V. and its content may not be copied or emailed to multiple sites without the copyright holder's express written permission. Additionally, content may not be used with any artificial intelligence tools or machine learning technologies. However, users may print, download, or email articles for individual use. This abstract may be abridged. No warranty is given about the accuracy of the copy. Users should refer to the original published version of the material for the full abstract.</i> (Copyright applies to all Abstracts.)
PLink https://search.ebscohost.com/login.aspx?direct=true&site=eds-live&db=egs&AN=7911582
RecordInfo BibRecord:
  BibEntity:
    Identifiers:
      – Type: doi
        Value: 10.1016/S0304-3975(01)00090-1
    Languages:
      – Code: eng
        Text: English
    PhysicalDescription:
      Pagination:
        PageCount: 44
        StartPage: 117
    Subjects:
      – SubjectFull: Algebra
        Type: general
      – SubjectFull: Markov processes
        Type: general
      – SubjectFull: Algorithms
        Type: general
    Titles:
      – TitleFull: Performance measure sensitive congruences for Markovian process algebras
        Type: main
  BibRelationships:
    HasContributorRelationships:
      – PersonEntity:
          Name:
            NameFull: Bernardo, Marco
      – PersonEntity:
          Name:
            NameFull: Bravetti, Mario
    IsPartOfRelationships:
      – BibEntity:
          Dates:
            – D: 01
              M: 01
              Text: Jan2003
              Type: published
              Y: 2003
          Identifiers:
            – Type: issn-print
              Value: 03043975
          Numbering:
            – Type: volume
              Value: 290
            – Type: issue
              Value: 1
          Titles:
            – TitleFull: Theoretical Computer Science
              Type: main
ResultId 1