Kahn Process Networks and a Reactive Extension - Signal Processing Systems - page 1045

The use of a totally ordered trace indicates the loss of independence of scheduling of
concurrent processes associated with the introduction of a merge construct, which
is one of the strongest points of KPN. A theoretical analysis of relational models for
indeterminate dataflow models is [ 54 ] .

7.2 Time

A timed process network model is a model which not only describes the data
transformations of the network, but also the timing of such a process [ 11 , 56 ] . Such
a model is typically made by labeling symbols on streams with time-stamps or tags
from a particular time domain of choice (for instance non-negative integers or reals)
or, more general, according to the tagged-signal model of [ 35 ] , allowing for instance
also partially ordered or super-dense time domains common in hardware description
languages [ 37 ] . Alternatively, a stream can then be described as a mapping from the
time-domain to the channel alphabet. If this function is total, it may also specify
the absence of data at certain points in time, which can then be deterministically
exploited by processes. Time-stamps may be interpreted as the exact timing of the
production of tokens or as a specification of a deadline for the production.
From a semantics perspective, time-stamps can be exploited to “rescue” the
merge process from indeterminacy and in general to make reactive behavior
deterministic. Using time information, decisions can be taken in a deterministic way,
based on the time-stamps of data, for instance to describe a merge process which
merges symbols in the order in which they arrive (with some deterministic provision,
for instance fixed priority, when tokens arrive at the same time) [ 11 , 37 , 56 ] .
Alternative network equations can be formulated and different fixed-point theorems
(such as Banach's) can be used to show them to have a unique solution. The
(big) price one has to pay for salvaging determinacy of the model is that it
requires a global notion of synchronized (logical) time, which puts constraints on
implementation and requires additional synchronization.
By adopting such a notion of synchronized global logical time, we end up close
to another end of the spectrum of data-flow languages, the domain of synchronous
languages such as Esterel [ 6 ] , Signal [ 5 ] orLustre[ 26 ] , where the execution of
a network needs to be globally synchronized. This can be a strong disadvantage
to a distributed implementation. Recent work [ 4 , 13 ] in the synchronous language
domain searches for conditions to relax the global synchrony constraints towards so-
called GALS (globally asynchronous, locally synchronous) implementations, where
particularly the most costly global synchronization may be eliminated.