Temporal Process Language

From Wikipedia, the free encyclopedia

In theoretical computer science, TPL (Temporal Process Language) 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.

1 Informal Definition
2 Formal Definition
- 2.1 Syntax
3 References

[edit] 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 + Ω$ 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.

[edit] Formal Definition

[edit] Syntax

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

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