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 non-deterministic networks, since the obvious generalization to continuous relations on histories is not compositional. Previous attempts to model non-deterministic 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 non-deterministic networks the assumption of continuity is not operationally justifiable, whereas fairness is still vital. We provide a compositional model for fair non-deterministic 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 Kahn-style history function from the network's trace set, showing that our model is a natural generalization of Kahn's.

49 pages

Return to: SCS Technical Report Collection
School of Computer Science homepage

This page maintained by reports@cs.cmu.edu