Kahn process networks

• A process need not read any input or have any input channels as it may act as a pure data source
• A process need not write any output or have any output channels
• Testing input channels for emptiness (or non-blocking reads) could be allowed for optimization purposes, but it should not affect outputs. It can be beneficial and/or possible to do something in advance rather than wait for a channel. For example, assume there were two reads from different channels. If the first read would stall (wait for a token) but the second read could succeed directly, it could be beneficial to read the second one first to save time, because the reading itself often consumes some time (e.g. time for memory allocation or copying).

Firing semantics of process P modeled with a Petri net displayed in the image above

Assuming process P in the KPN above is constructed so that it first reads data from channel A, then channel B, computes something and then writes data to channel C, the execution model of the process can be modeled with the Petri net shown on the right.[2] The single token in the PE resource place forbids the process from executing simultaneously for different input data. When data arrives at channel A or B, tokens are placed into places FIFO A and FIFO B respectively. The transitions of the Petri net are associated with the respective I/O operations and computation. When the data has been written to channel C, PE resource is filled with its initial marking again allowing new data to be read.

A finite state machine of a process

A process can be modeled as a finite state machine that is in one of two states:

• Active; the process computes or writes data
• Wait; the process is blocked (waiting) for data

Assuming the finite state machine reads program elements associated with the process, it may read three kinds of tokens, which are "Compute", "Read" and "Write token". Additionally, in the Wait state it can only come back to Active state by reading a special "Get token" which means the communication channel associated with the wait contains readable data.

A channel is strictly bounded by ${\displaystyle b}$ if it has at most ${\displaystyle b}$ unconsumed tokens for any possible execution. A KPN is strictly bounded by ${\displaystyle b}$ if all channels are strictly bounded by ${\displaystyle b}$.

The number of unconsumed tokens depends on the execution order (scheduling) of processes. A spontaneous data source could produce arbitrarily many tokens into a channel if the scheduler would not execute processes consuming those tokens.

A real application can not have unbounded FIFOs and therefore scheduling and maximum capacity of FIFOs must be designed into a practical implementation. The maximum capacity of FIFOs can be handled in several ways:

• FIFO bounds can be mathematically derived in design to avoid FIFO overflows. This is however not possible for all KPNs. It is an undecidable problem to test whether a KPN is strictly bounded by ${\displaystyle b}$. Moreover, in practical situations, the bound may be data dependent.
• FIFO bounds can be grown on demand.[3]
• Blocking writes can be used so that a process blocks if a FIFO is full. This approach may unfortunately lead to an artificial deadlock unless the designer properly derives safe bounds for FIFOs (Parks, 1995). Local artificial detection at run-time may be necessary to guarantee the production of the correct output.[4]

A closed KPN has no external input or output channels. Processes that have no input channels act as data sources and processes that have no output channels act as data sinks. In an open KPN each process has at least one input and output channel.

Processes of a KPN are deterministic. For the same input history they must always produce exactly the same output. Processes can be modeled as sequential programs that do reads and writes to ports in any order or quantity as long as determinism property is preserved. As a consequence, KPN model is deterministic so that following factors entirely determine outputs of the system:

• processes
• the network
• initial tokens

Hence, timing of the processes does not affect outputs of the system.

KPN processes are monotonic. Reading more tokens can only lead to writing more tokens. Tokens read in the future can only affect tokens written in the future. In a KPN there is a total order of events inside a signal. However, there is no order relation between events in different signals. Thus, KPNs are only partly ordered, which classifies them as an untimed model.