Process algebras are mathematical tools used to model and analyze a system in which more than one process occurs concurrently. In many real-world processes, priorities, probabilities, and the duration of an action need due emphasis. Prioritized, probabilistic, and deterministically timed process algebras were developed to tackle each of these problems in isolation. Extended Markovian process algebra (EMPA) is proposed to consider these aspects together. According to the authors, the underlying theory is not complex and is based on available stochastically timed algebras.
This tutorial paper includes 60 references. It is divided into five major sections, the sixth consisting of concluding remarks and an appendix. Section 1 introduces process algebras in approximately one page. The syntax and semantics of EMPA operators are described in section 2 (five pages). Integrated interleaving of EMPA is the basis of section 3 (about three pages). The kernel, along with four components, is used to model different kinds of actions. This approach is the heart of EMPA, which allows comparison of the process algebras reported in the literature. In section 5, the authors define a notion of equivalence over EMPA terms by considering each of the kernels in isolation. The algorithms and tables enhance the lucidity of the paper.
While EMPA consists of nondeterministic, prioritized, and exponentially timed kernels, the nondeterministic kernel considers passive actions that model activities waiting for synchronization with timed activities. This component corresponds to classical process algebra, which does not take into account the duration of the action. Thus, only functional characteristics such as the absence of deadlock of a concurrent process can be studied. Prioritized and probabilistic kernels deal with immediate actions. The former type deals with actions of the same weight, while the latter deals with those having the same priority level. The exponentially timed kernel takes into account actions with exponential time profiles. It models activities from the performance point of view. The dining philosophers problem is used to demonstrate the capabilities and applications of EMPA. The formal definition of integrated interleaving semantics for EMPA is based on the transaction relation.
The idea of potential move employed in this context is intuitive. The expressiveness of EMPA is the sum of the expressiveness of classical, prioritized, probabilistic, and exponentially timed process algebras. It is contemplated that the gap between deterministically timed and stochastically timed process algebras will be reduced with the increase of the expressive power of EMPA.