Semantics of Probabilistic Processes: An Operational Approach
Yuxin Deng · 2015
Subject matter With the rapid development of computer network and communication technology, the study of concurrent and distributed systems has become increasingly impor-tant. Among various models of concurrent computation, process calculi have been widely investigated and successfully used in the specification, design, analysis and verification of practical concurrent systems. In recent years, probabilistic process calculi have been proposed to describe and analyse quantitative behaviour of con-current systems, which calls for the study of semantic foundations of probabilistic processes. In “Semantics of Probabilistic Processes ” [4] we adopt an operational ap-proach to describing the behaviour of nondeterministic and probabilistic processes. The semantic comparison of different systems is based on appropriate behavioural relations such as bisimulation equivalences and testing preorders. This book mainly consists of two parts. The first part provides an elementary account of bisimulation semantics for probabilistic processes from metric, logical and algorithmic perspectives. The second part sets up a general testing framework and specialises it to probabilistic processes with nondeterministic behaviour. The resulting testing semantics is treated in depth. A few variants of it are shown to coincide, and they can be characterised in terms of modal logics and coinductively defined simulation relations. Although in the traditional (nonprobabilistic) setting, simulation semantics is in general finer (i.e. it distinguishes more processes) than testing semantics, for a large class of probabilistic processes, the gap between simulation and testing semantics disappears. Therefore, in this case, we have a semantics where both negative and positive results can be easily proved: to show that two processes are not related in the semantics, we just give a witness test, and to prove that two processes are related, we only need to establish a simulation relation. Why yet another book? Three decades have passed since the well-known books on process algebras by Hoare [8], Milner [10], Baeten and Weijland [3], and Hennessy [7] were pub-lished. In the meanwhile some excellent textbooks have appeared, including those