Stochastic Process Algebras - Between LOTOS and Markov Chains

This paper introduces stochastic process algebras as an approach for the structured design and analysis of both the functional behavior and performance characteristics of parallel and distributed systems. This is achieved by integrating stochastic modelling and analysis into process algebras like CCS or LOTOS. We demonstrate how notions of equivalent behavior -- substantial for process algebras -- stand in a new light for stochastic process algebras. In particular we discuss the impact of stochastic versions of such equivalences on compositional performance analysis by means of a running example. In addition we discuss analysis techniques, tool support and include a survey of related work as well as recent trends in this area. Keywords: Process Algebra, Performance Analysis, Stochastic Time, Markov Chains, Bisimulation. 1 Introduction -- Distributed Systems and their Formal Description One may safely assume that almost all substantial future computer- and information systems will be ..