Article Preview
Top1. Introduction
Concurrent systems (e.g. time sharing computers, mainframes, client-server systems, telecommunication systems) consist of multiple, simultaneously active computing agents that interact with one another and with the environment. In these systems, the access conflicts to some shared resources leads to different non-deterministic behavioral scenarios. Moreover, due to competition, faults, physical phenomena and random strategies, these systems are characterized by randomly varying time instants and intervals, summarized as probabilistic and stochastic (temporal) behaviors (Hermanns et al., 1998). For instance, in communication networks, communication delays vary depending on the actual traffic, on the selected route, and on the retransmission because of transmission faults or buffer overflows, etc. Hence, the behavior and the performance of such systems cannot be described or analyzed by deterministic timing models. However, the analysis of performance properties of concurrent systems needs probabilistic and/or stochastic timing models. Actually, behaviors with randomly varying time instants and intervals of stochastic systems are modeled by Queuing Networks or stochastic versions of Petri Nets, Automata, or Process Algebras (PAs), wherein the varying time instants and intervals are captured by random variables, which are characterized by their probability distribution functions.
From other hand, “the insularity problem of performance evaluation in the system design process” (Harvey, 1986) is produced due to the separation between the functional and performance aspects of systems during their design. However, both functional and performance features are becoming of increasing similar interests, and it would be beneficial to be able to check how changes in functionality affect performance issues, and vice versa (Bravetti et al., 1998). Thus, it is highly desirable to have a single framework where both aspects could be defined and analyzed, and avoid the use of different models that may be mutually incompatible (Ferrari, 1986).
In this paper, we present our approach for integrated functional and performance specification and analysis of concurrent systems. We propose the adoption of a new stochastic extension of Process Algebra (that naturally supplies formality, compositionality and abstraction). Our Stochastic Process Algebra (SPA) -like other ones- extends the expressiveness of classical process algebra by representing each action as a pair composed of its name and the probability distribution function governing its duration. However, unlike other SPAs, our contribution consists of two points:
- •
Specifying and modeling functional and performance behaviors with true concurrency and using general distributions. Unlike Markovian Process Algebras and their interleaving semantics, our SPA allows to support immediate, deterministic, Markovian and non Markovian durations, thanks to the true concurrency of the underlying maximality semantics
- •
Pruning the state space graph by avoiding the explicit splitting of actions into start and termination events. In fact, functional and performance analyses can be carried out on a new integrated semantic model, called MLSTS (Maximality-based Labeled Stochastic Transition System), a transition system labeled by both type and probability distribution function of the action duration, wherein transitions only represent the starts of action executions.
The paper is organized as follows: In section 2, we recall the principle of the maximality semantics and we present informally the basic semantic model, i.e. the Maximality-based Labeled Stochastic Transition System. In section 3, we present our Stochastic Process Algebra, called S-LOTOS, which enables us to compositionally describe MLSTS models, and we present the operational semantics of their behavioral expressions, that allows the automatic generation of the underlying MLSTS models. In section 4, we discuss briefly the main performance evaluation approaches. In Section 5 we present –as an explanatory case study– the specification and the analysis of a well-known example, i.e. the Alternating Bit Protocol, and in section 6 we discuss some related works. Finally, section 7 concludes the paper.