Temporal Process Language

In theoretical computer science, Temporal Process Language (TPL) is a process calculus which extends Robin Milner's CCS with the notion of ''multi-party synchronization'', which allows multiple process to synchronize on a global 'clock'. This clock measures time, though not concretely, but rather as an abstract signal which defines when the entire process can step onward.

Informal definition

TPL is a conservative extension of CCS, with the addition of a special action called σ representing the passage of time by a process - the ticking of an abstract clock. As in CCS, TPL features action prefix and it can be described as being ''patient'', that is to say a process $a.P$ will idly accept the ticking of the clock, written as

$a.P \rightarrow^a a.P$

Key to the use of abstract time is the ''timeout'' operator, which presents two processes, one to behave as if the clock ticks, one to behave as if it can't, i.e.

$\lfloor E \rfloor (F) \rightarrow^\sigma F$

provided process E does not prevent the clock from ticking.

$\lfloor E \rfloor (F) \rightarrow^\sigma E'$

provided E can perform action a to become E'.

In TPL, there are two ways to prevent the clock from ticking. First is via the presence of the ω operator, for example in process $a.P + \Omega$ the clock is prevented from ticking. It can be said that the action a is ''insistent'', i.e. it insists on acting before the clock can tick again.

The second way in which ticking can be prevented is via the concept of ''maximal-progress'', which states that silent actions (i.e. τ actions) always take precedence over and thus suppress σ actions. Thus is two parallel processes are capable of synchronizing at a given instant, it is not possible for the clock to tick.

Thus a simple way of viewing multi-party synchronization is that a group of composed processes will allow time to pass provided none of them prevent it, i.e. the system agrees that it is time to move on.

Formal definition

Syntax

Let a be a non-silent action name, α be any action name (including τ, the silent action) and be a process label used for recursion.

:$\begin Proc ::= & \alpha.Proc \\ , & \lfloor Proc \rfloor (Proc) \\ , & Proc + Proc \\ , & Proc\;, \;Proc \\ , & rec X.Proc \\ , & X \\ , & \Omega \\ , & Proc \setminus a \\ , & 0 \\ \end{matrix}$

References

Matthew Hennessy and Tim Regan : ''A Process Algebra for Timed Systems''. Information and Computation, 1995.

Process calculi