On the Kahn Principle and Fair Networks
Abstract
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.
Document Details
- Document Type
- Technical Report
- Publication Date
- Aug 01, 1998
- Accession Number
- ADA356031
Entities
People
- Stephen Brookes
Organizations
- Carnegie Mellon University