Performance Evaluation of Distributed Systems Based on a Discrete Real- and Stochastic-Time Process Algebra

Issue title: Application of Concurrency to System Design

Article type: Research Article

Authors: Markovski, Jasen | de Vink, Erik P.

Affiliations: Formal Methods Group, Department of Mathematics and Computer Science, Eindhoven University of Technology, Den Dolech 2, 5612 AZ Eindhoven, The Netherlands. E-mail: [email protected],[email protected]

Abstract: We present a process-algebraic framework for performance evaluation of discrete-time discrete-event systems. The modeling of the system builds on a process algebra with conditionallydistributed discrete-time delays and generally-distributed stochastic delays. In the general case, the performance analysis is done with the toolset of the modeling language χ by means of discrete-event simulation. The process-algebraic setting allows for expansion laws for the parallel composition and the maximal progress operator, so one can directly manipulate the process terms and transform the specification in a required form. This approach is illustrated by specifying and solving the recursive specification of the G/G/1/∞ queue, as well as by specifying a variant of the concurrent alternating bit protocol with generally-distributed unreliable channels. In a specific situation when all delays are assumed deterministic, we turn to performance analysis of probabilistic timed systems. This work employs discrete-time probabilistic reward graphs, which comprise deterministic delays and immediate probabilistic choices. Here, we extend previous investigations on the topic, which only touched long-run analysis, to tackle transient analysis as well. The theoretical results obtained allow us to extend the χ-toolset. For illustrative purposes, we analyze the concurrent alternating bit protocol in the extended environment of the χ-toolset using discrete-event simulation for generallydistributed channels, the developed analytical method for deterministic channels, and Markovian analysis for exponentially-distributed delays.

DOI: 10.3233/FI-2009-146

Journal: Fundamenta Informaticae, vol. 95, no. 1, pp. 157-186, 2009