Kahn Process Networks

An untimed computation network of deterministic sequential processes connected by conceptually unbounded FIFO streams, where blocking reads and nonblocking writes yield a least-fixed-point output independent of execution schedule.

Version

v2 · 2026-09-06 · History

Domain-specific #

2118

Origin domain

computer science

Subdomain

concurrent models of computation

Aliases

KPN, Kahn network, Process network

Core Idea

A Kahn process network (KPN) is a directed network of deterministic sequential processes communicating through FIFO token streams. Each channel has one writer and one reader, reads block when the requested token is unavailable, and writes are semantically nonblocking because channels are modeled as unbounded. Processes cannot branch on whether a channel is empty without consuming according to their fixed program.

Each process denotes a continuous function from input streams to output streams under prefix order. The connected network denotes the least fixed point of those functions, so its output streams depend on processes, topology, inputs, and initial tokens—not on relative execution speeds or a fair schedule's interleaving.

Scope of Application

KPNs model streaming, signal-processing, embedded, high-performance, and dataflow computations. Dataflow process networks specialize KPNs by decomposing processes into repeated actor firings, enabling efficient visual programming and scheduling.

Clarity

Declare channel topology, token domains, read order, process functions, initial tokens, external inputs, and fairness assumptions. Separate the ideal unbounded semantic model from an implementation's buffer capacities and blocking-write policy. State whether a claimed property is functional determinism, liveness, boundedness, throughput, or schedulability.

Manages Complexity

The model makes concurrency compositional: deterministic stream transducers can be reasoned about as functions even when executed in parallel. Schedule independence removes interleaving order from functional correctness, leaving scheduling to optimize resource use without redefining intended outputs.

Abstract Reasoning

1. Express each process as a deterministic stream transformer.
2. Connect outputs to inputs through single-reader/single-writer FIFOs.
3. Verify blocking reads and absence of output-affecting availability tests.
4. Establish monotonicity and continuity under prefix order.
5. Form the simultaneous stream equations.
6. Interpret the network by their least fixed point.
7. Prove functional equivalence independently of schedule.
8. Analyze liveness and buffer boundedness separately.
9. Design a finite implementation with safe scheduling or overflow policy.

Knowledge Transfer

The portable pattern is constrain communication so concurrent execution denotes one monotone fixed point, separating functional meaning from timing. It transfers to deterministic streaming systems. The proposed immediate parent is Network.

Relationships to Other Abstractions

Current abstraction Kahn Process Networks Domain-specific

Parents (1) — more general patterns this builds on

• Kahn Process Networks is a kind of Network Prime

  Network is the proposed immediate parent.

Hierarchy path (1) — routes to 1 parentless root

• Kahn Process Networks → Network → Reservoir-Flux Network → Conservation Laws → Invariance

Neighborhood in Abstraction Space

Kahn Process Networks sits in a sparse region of the domain-specific corpus (91^st percentile for distinctiveness): few abstractions share its structure, so a faithful description tends to retrieve it precisely.

Family — Unclustered & Miscellaneous (1565 abstractions)

Nearest neighbors

• CAP Theorem — 0.79
• FLP Impossibility — 0.79
• Rice's Theorem — 0.79
• Disjoint-Set Data Structure — 0.77
• Cryptographic Hash Function — 0.77

Computed from structural-signature embeddings · 2026-09-08