Logo[ ILPnet2 | Library | Newsletter | CSCW | Education | End-User Club | Events | Nodes | Systems | Applications | Members only ]

Linear Dynamic Kahn Networks are Deterministic.

A. de Bruin and S. H. Nienhuys-Cheng. Theoretical Computer Science, 195(1):3--32, March 1998.

Abstract

The first part of Kahn principle states that networks with deterministic nodes are deterministic on the I/O level: for each network, different executions provided with the same input streams deliver the same output streams. the Kahn principle has thus far not been proved for dynamic, non-deterministic networks.

We consider a simple language L containing the fork-statement. For this language we introduce a non-deterministic transition system which defines all interleavings consisting of baisc steps, for all possible executions of a program. We prove that, although on the execution level there is much nondeterminism, this nondeterminism disappears because all executions deliver the same output stream (or a prefix of it), given the same input stream. This proves the Kahn principle for linear, nondeterministic dynamic networks.

BibTeX entry.

Other publications


S-H Nienhuys-Cheng, cheng@few.eur.nl. Last modified on Wednesday 9 April 2003 at 18:31. © 2003 ILPnet2