×

Performance evaluation of distributed systems based on a discrete real- and stochastic-time process algebra. (English) Zbl 1215.68049

Summary: 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 conditionally distributed discrete-time delays and generally-distributed stochastic delays. In the general case, the performance analysis is done with the toolset of the modeling language \(\chi\) 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/\infty\) 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 \(\chi\)-toolset. For illustrative purposes, we analyze the concurrent alternating bit protocol in the extended environment of the \(\chi\)-toolset using discrete-event simulation for generally distributed channels, the developed analytical method for deterministic channels, and Markovian analysis for exponentially-distributed delays.

MSC:

68M20 Performance evaluation, queueing, and scheduling in the context of computer systems
68M14 Distributed systems
68Q85 Models and methods for concurrent and distributed computing (process algebras, bisimulation, transition nets, etc.)

Software:

MoDeST
PDFBibTeX XMLCite
Full Text: DOI