An Asynchronous Process Algebra with Multiple Clocks

From bibtex.

Abstract

In this paper we introduce a novel approach to the specification of real-time behaviour with process algebras. In contrast to the usual pattern, involving a fixed, measurable, and global notion of time, we suggest to represent real-time constraints indirectly through uninterpreted clocks enforcing broadcast synchronization between processes. Our approach advocates the use of asynchronous process algebras, which admit the faithful representation of nondeterministic and distributed computations. Technically, we present a non-trivial extension of the Calculus of Communicating Systems CCS [Mil89a) by multiple clocks with associated timeout and clock ignore operators. We illustrate the flexibility of the proposed process algebra, called PMC, by presenting examples of rather different nature. The timeout operators generalize the timeout of ATP [NS90] to multiple clocks. The main technical contribution is a complete axiomatization of strong bisimulation equivalence for a class of finite-state processes and a complete axiomatization of observation congruence for finite processes.