
CMUCS98156
Computer Science Department
School of Computer Science, Carnegie Mellon University
CMUCS98156
On the Kahn Principle and Fair Networks
Stephen Brookes
August 1998
This is an extended version of a paper presented at
MFPS'98. Also submitted to Theoretical Computer
Science.
CMUCS98156.ps
CMUCS98156.pdf
Keywords: Communicating processes, dataflow, networks,
denotational semantics, fairness, safety, liveness, nondeterminism,
parallel programming
The Kahn Principle states that each node in an asynchronous deterministic
network computes a continuous function from input histories to output
histories, and the behavior of the network can be characterized as a
least fixed point. Fairness plays a vital but implicit role: the Kahn
Principle is only sound when network execution is assumed to be (weakly)
fair. Kahn's model does not extend easily to nondeterministic networks,
since the obvious generalization to continuous relations on histories is
not compositional. Previous attempts to model nondeterministic networks
have sought to remain faithful to Kahn's spirit by retaining some form of
continuity assumption; these approaches typically apply only to a limited
class of network and do not deal adequately with fairness. We argue that
for nondeterministic networks the assumption of continuity is not
operationally justifiable, whereas fairness is still vital. We provide a
compositional model for fair nondeterministic networks, based
on trace sets which can be regarded as history relations "extended in time"
to allow for the possibility of interference during execution. For a
deterministic network one can extract the Kahnstyle history function from
the network's trace set, showing that our model is a natural generalization
of Kahn's.
49 pages
