Communicating Sequential Processes

Knowledge Graph: Communicating Sequential Processes (C.A.R. Hoare, 1978)

Editorial spotlight: ↑ synchronous rendezvous — the atomic primitive

Concepts

• CSP process (importance 5): Sequential program that communicates with other processes only through input/output operations on named channels. No shared variables.. Source: (from training memory of book).
• synchronous communication (rendezvous) (importance 5): Both sender and receiver must be ready simultaneously for a message transfer to occur. No buffering, no asynchrony — the foundational design choice.. Source: (from training memory of book).
• CSP channel (importance 5): Named communication link between processes. Typed, point-to-point. The only way processes interact.. Source: (from training memory of book).
• determinacy property (importance 4): A process is determinate if output depends only on input sequence, not timing. Most CSP examples are determinate by construction.. Source: (from training memory of book).
• non-determinism via alternative (importance 4): When multiple guards are ready, choice is arbitrary. Explicit, controlled non-determinism for servers.. Source: (from training memory of book).
• process algebra (importance 4): Mathematical framework for reasoning about concurrent systems. CSP is the first widely-adopted process algebra.. Source: (from training memory of book).
• process network topology (importance 4): Arrangement of processes and channels forms a graph. Topology determines communication patterns and deadlock risk.. Source: (from training memory of book).
• blocking I/O semantics (importance 4): Input and output commands block the executing process until communication completes. No polling, no busy-wait.. Source: (from training memory of book).
• compositional reasoning (importance 4): Behavior of P || Q derived from behaviors of P and Q independently. Enables modular verification.. Source: (from training memory of book).
• fairness assumption (importance 3): CSP does not guarantee fairness. A starved process is a valid execution. Fairness must be enforced by design.. Source: (from training memory of book).
• safety property (importance 3): Nothing bad ever happens. Verified by showing no trace leads to error state.. Source: (from training memory of book).
• liveness property (importance 3): Something good eventually happens. Requires failures-divergences semantics to verify.. Source: (from training memory of book).
• stream processing model (importance 3): Infinite sequences of values flowing through process networks. CSP's natural abstraction for data flow.. Source: (from training memory of book).
• value-passing (not name-passing) (importance 3): CSP 1978 passes data values, not channel names. Later pi-calculus adds name-passing (mobile channels).. Source: (from training memory of book).
• channel as abstraction barrier (importance 3): Internal state of a process is invisible to others. Only communication behavior matters. Strong encapsulation.. Source: (from training memory of book).
• reactive system model (importance 3): CSP naturally models systems that respond to environment indefinitely. Infinite loops are the norm, not bugs.. Source: (from training memory of book).
• channel protocol specification (importance 3): Specifying valid message sequences on a channel. CSP enables modular protocol design.. Source: (from training memory of book).
• CSP as notation vs. implementation (importance 3): Hoare presents CSP as design notation, not necessarily efficient implementation. Clarity over performance.. Source: (from training memory of book).
• livelock (importance 2): System makes progress but never reaches goal state. Harder to detect than deadlock in CSP.. Source: (from training memory of book).
• channel typing (importance 2): Each channel has a declared type. Messages must match the type. Static checking prevents type errors.. Source: (from training memory of book).
• timeout (later extension) (importance 2): Not in 1978 CSP. Later variants add timeout guards for real-time systems.. Source: (inferred — post-1978 extension).
• buffered channels (Go extension) (importance 2): Not in Hoare's CSP. Go allows buffered channels to decouple sender/receiver timing.. Source: (inferred — Go divergence from CSP).
• critical section via channels (importance 2): Mutual exclusion enforced by process controlling access channel. No locks, no monitors — just message-passing.. Source: (from training memory of book).
• Church-Rosser property (importance 2): For deterministic CSP processes, order of internal transitions doesn't matter — final state is unique.. Source: (from training memory of book).
• starvation risk (importance 2): Process never gets scheduled despite being ready. CSP semantics allow this unless fairness is explicitly designed in.. Source: (from training memory of book).
• event ordering (happened-before) (importance 2): Partial order on communications. P sends before Q receives. Basis for trace semantics.. Source: (from training memory of book).
• behavioral equivalence (importance 2): Two processes are equivalent if they have the same traces. Abstracts away internal implementation.. Source: (from training memory of book).
• divergence (infinite internal loop) (importance 2): Process performs infinite sequence of internal actions without communicating. Liveness failure.. Source: (from training memory of book).
• refusal set (importance 2): Set of events a process can refuse after a given trace. Needed to distinguish deadlock from choice.. Source: (from training memory of book).
• data abstraction via channels (importance 2): Server process encapsulates data structure. Clients interact via request/reply protocol. Message-passing ADT.. Source: (from training memory of book).
• real-time CSP (Timed CSP) (importance 2): Extension adding explicit time delays and deadlines. Not in Hoare's original formulation.. Source: (inferred — post-1978 extension).
• communication patterns catalog (importance 2): Recurring process network topologies: pipeline, tree, ring, mesh. CSP's architectural palette.. Source: (from training memory of book).
• channel directionality (importance 2): Each process has input/output view of channel. Mismatch is type error.. Source: (from training memory of book).
• interference freedom (Owicki-Gries) (importance 2): Shared-memory proof technique. CSP avoids the problem by eliminating shared memory.. Source: (from training memory of book).
• priority (later extension) (importance 1): Not in 1978 CSP. Some later variants add priority to alternative command for scheduling control.. Source: (inferred — post-1978 extension).
• structured messages (importance 1): Messages can be tuples, records, or simple values. Channel typing enforces structure.. Source: (from training memory of book).
• fan-out (broadcast) (importance 1): One process sends to multiple receivers. Requires N output commands (no implicit multicast).. Source: (from training memory of book).
• fan-in (merge) (importance 1): One process receives from multiple senders. Server pattern uses alternative to handle any sender.. Source: (from training memory of book).
• virtual channels (importance 1): Logical channels multiplexed over physical links. Implementation detail not in core CSP model.. Source: (from training memory of book).
• process naming (importance 1): Processes have symbolic names in parallel composition. Used to specify channel connections.. Source: (from training memory of book).

Claims

• no shared memory thesis (importance 5): Hoare's radical constraint: processes share NOTHING except communication channels. All interaction is explicit message-passing.. Source: (from training memory of book).
• deadlock as correctness signal (importance 4): A CSP system that deadlocks when done is correct — termination IS deadlock. Unintended deadlock is a specification error.. Source: (from training memory of book).
• minimalism thesis (importance 4): A few primitives (channels, guards, parallel composition) suffice for all concurrent patterns. Occam's razor applied to concurrency.. Source: (from training memory of book).
• synchrony simplifies reasoning (importance 4): Synchronous communication eliminates message buffers, ordering ambiguity, and race conditions. Compositional reasoning becomes tractable.. Source: (from training memory of book).
• subroutine ≠ process distinction (importance 3): Subroutine: caller waits for return. Process: independent life, communicates as peer. Fundamental shift in abstraction.. Source: (from training memory of book).
• no implementation commitment (importance 3): CSP is specification language, not programming language. Doesn't mandate threads, interrupts, or scheduling policy.. Source: (from training memory of book).
• shared-memory as legacy model (importance 3): Hoare argues shared memory is holdover from sequential thinking. Message-passing is the natural concurrent abstraction.. Source: (from training memory of book).
• zero-capacity channels (importance 3): Pure CSP channels have no buffer. Message transfer is atomic handshake. Buffering is a separate process if needed.. Source: (from training memory of book).
• modularity via independent processes (importance 3): Each process is self-contained unit with interface = channels. Strong modularity boundary.. Source: (from training memory of book).
• termination convention (importance 2): A process terminates by ceasing all communication. No explicit 'done' signal required.. Source: (from training memory of book).
• concurrency ≠ parallelism (importance 2): CSP describes concurrent interaction structure, not physical parallel execution. Implementation may be sequential or parallel.. Source: (from training memory of book).
• no interrupt primitive (importance 2): CSP 1978 has no interrupt/preemption. All control transfer is via communication. Later CSP variants add interrupts.. Source: (from training memory of book).
• synchronization overhead acceptable (importance 2): Hoare argues cost of rendezvous is small compared to gained simplicity. Hardware support (Transputer) makes it negligible.. Source: (from training memory of book).

Methods

• parallel composition (||) (importance 5): Combines processes to run concurrently. Processes listed explicitly, channels connect them. No implicit sharing.. Source: (from training memory of book).
• input command (c?x) (importance 4): Waits to receive a value from channel c, assigns it to variable x. Blocks until sender is ready.. Source: (from training memory of book).
• output command (c!e) (importance 4): Sends the value of expression e on channel c. Blocks until receiver is ready.. Source: (from training memory of book).
• guarded command (Dijkstra's guards in CSP) (importance 4): Boolean guard followed by action. Input guards extend Dijkstra's original guards to include communication readiness.. Source: (from training memory of book).
• alternative command ([ ... ]) (importance 4): Non-deterministic choice among multiple guarded commands. Waits for one guard to become ready, executes that branch.. Source: (from training memory of book).
• repetitive command (*[ ... ]) (importance 4): Repeatedly executes alternative command until all guards are false. The server pattern primitive.. Source: (from training memory of book).
• trace semantics (importance 4): Formal meaning of a process is the set of all possible traces (sequences of communications). Foundation for CSP verification.. Source: (from training memory of book).
• trace refinement (importance 3): Process P refines Q if traces(P) ⊆ traces(Q). Allows stepwise development from specification to implementation.. Source: (from training memory of book).
• failures-divergences semantics (importance 3): Extension of traces to include refusal sets and divergence. Needed for liveness properties.. Source: (from training memory of book).
• recursive process definition (importance 3): Process defined in terms of itself. Enables infinite behavior (servers) and inductive reasoning.. Source: (from training memory of book).
• formal verification via traces (importance 3): Prove correctness by showing desired property holds for all traces. CSP's algebraic laws enable equational reasoning.. Source: (from training memory of book).
• CSP algebraic laws (importance 3): Equations like (P || Q) = (Q || P), (P ; SKIP) = P. Enable syntactic transformation and optimization.. Source: (from training memory of book).
• sequential composition (;) (importance 2): Run P, then Q. Standard imperative sequencing within a single process.. Source: (from training memory of book).
• STOP command (importance 2): Deadlocks immediately. Useful for modeling error states.. Source: (from training memory of book).
• hiding operator (\) (importance 2): Makes internal channels invisible to external observers. Implements information hiding.. Source: (from training memory of book).
• renaming operator (importance 2): Changes channel names. Useful for composing processes with mismatched interfaces.. Source: (from training memory of book).
• simulation relation (importance 2): Process P simulates Q if every Q-trace has a corresponding P-trace. Refinement preorder.. Source: (from training memory of book).
• abstraction function (implementation → spec) (importance 2): Maps concrete implementation states to abstract specification states. Key to stepwise refinement.. Source: (from training memory of book).
• proof obligations per operator (importance 2): Each CSP operator has associated proof rules. Parallel composition requires showing channel protocol compatibility.. Source: (from training memory of book).
• invariant-based proof (importance 2): Find predicate preserved by all process actions. Standard technique adapted from Floyd-Hoare logic.. Source: (from training memory of book).
• recursion unfolding proof (importance 2): Prove property P(X) by assuming P holds for recursive calls. Structural induction on process definitions.. Source: (from training memory of book).
• global invariant reasoning (importance 2): Property of entire system state. Harder to establish in CSP than local invariants due to distributed state.. Source: (from training memory of book).
• SKIP command (importance 1): Does nothing, terminates immediately. Identity for sequential composition.. Source: (from training memory of book).
• assignment (x := e) (importance 1): Standard imperative assignment within a process. No communication, just local state update.. Source: (from training memory of book).
• conditional (if-then-else) (importance 1): Standard imperative conditional. Guard evaluated locally, no communication.. Source: (from training memory of book).

Entities

• Occam language (importance 4): First hardware implementation of CSP, designed for Transputer chips. Direct realization of Hoare's primitives.. Source: (from training memory of book).
• Go channels (goroutines) (importance 4): Modern descendant of CSP. Go's concurrency model is Hoare's primitives with buffered channels and garbage collection.. Source: (inferred — post-1978 influence).
• COPY process example (importance 3): Canonical first example: reads from west channel, writes to east channel, loops forever. Demonstrates basic CSP structure.. Source: (from training memory of book).
• DIV process (Sieve of Eratosthenes) (importance 3): Filters out multiples of a prime. Part of the prime sieve pipeline — demonstrates process networks.. Source: (from training memory of book).
• bounded buffer pattern (importance 3): Fixed-size queue implemented as a process. Demonstrates state management via repetitive command.. Source: (from training memory of book).
• semaphore in CSP (importance 3): Resource counter implemented as a process with P/V channels. Shows how classical concurrency primitives emerge from CSP.. Source: (from training memory of book).
• dining philosophers problem (importance 3): Classic deadlock scenario. Hoare's solution uses a butler process to prevent circular wait.. Source: (from training memory of book).
• Erlang actors (importance 3): Asynchronous variant: mailbox buffering instead of synchronous rendezvous. CSP influence via shared 'no-shared-state' principle.. Source: (inferred — post-1978 influence).
• Dijkstra's guarded commands (1975) (importance 3): Hoare's starting point. CSP extends guards to include communication readiness, not just boolean conditions.. Source: (from training memory of book).
• monitor paradigm (Hoare 1974) (importance 3): Hoare's earlier shared-memory concurrency model. CSP rejects monitors in favor of message-passing.. Source: (from training memory of book).
• pipeline pattern (importance 3): Linear chain of processes. Each stage transforms input to output. Prime sieve is canonical example.. Source: (from training memory of book).
• client-server pattern (importance 3): One server process, many clients. Server uses repetitive alternative to handle requests non-deterministically.. Source: (from training memory of book).
• FDR model checker (importance 3): Tool for automatically checking CSP properties via exhaustive state exploration. Developed after Hoare's original paper.. Source: (inferred — post-1978 tool).
• pi-calculus (Milner 1992) (importance 3): Successor to CSP adding mobile channel names. Channels become first-class values.. Source: (inferred — post-CSP development).
• Actor model (Hewitt 1973) (importance 3): Concurrent formalism predating CSP. Asynchronous message-passing, no synchronous rendezvous.. Source: (from training memory of book).
• Inmos Transputer (importance 3): VLSI chip implementing CSP in hardware. 4 serial links for process communication. Occam's target platform.. Source: (inferred — post-1978 hardware).
• SQUASH process (importance 2): Removes consecutive duplicates from a stream. Example of stateful stream processing.. Source: (from training memory of book).
• matrix multiplication example (importance 2): Array of processes computing matrix product in parallel. Demonstrates systolic array pattern.. Source: (from training memory of book).
• Petri nets (importance 2): Alternative formalism for concurrency. CSP is higher-level, algebraic; Petri nets are graphical, token-based.. Source: (from training memory of book).
• systolic array pattern (importance 2): Regular 2D grid of processes. Data flows through like blood through tissue. Matrix algorithms.. Source: (from training memory of book).
• ring topology (importance 2): Processes arranged in a circle. Token-passing protocols. Risk of deadlock if not carefully designed.. Source: (from training memory of book).
• select statement (Go) (importance 2): Go's syntax for CSP alternative command. Chooses among ready channels.. Source: (inferred — Go realization).
• Conway's problem (importance 2): Card deck splitting and interleaving. Classic coroutine example adapted to CSP.. Source: (from training memory of book).
• producer-consumer pattern (importance 2): One process generates data, another consumes it. Bounded buffer mediates. Textbook concurrency example.. Source: (from training memory of book).
• readers-writers problem (importance 2): Multiple readers OR one writer accessing shared resource. CSP solution uses server process to arbitrate.. Source: (from training memory of book).
• CCS (Milner 1980) (importance 2): Milner's alternative process calculus. Asynchronous, different operator set. Both CSP and CCS foundational.. Source: (inferred — post-1978 comparison).
• temporal logic for CSP (importance 2): Later work applies LTL/CTL to CSP processes. Expresses safety/liveness as logical formulas.. Source: (inferred — post-1978 verification).
• distributed termination detection (importance 2): Algorithm for detecting when all processes have finished. Non-trivial in CSP due to lack of global state.. Source: (from training memory of book).
• CSP → Occam compilation (importance 2): Occam is executable CSP with concrete syntax and scheduling. Compiles to Transputer bytecode.. Source: (inferred — post-1978 implementation).
• Linda tuple spaces (importance 2): Alternative coordination model using shared tuple space. CSP uses point-to-point channels instead.. Source: (inferred — parallel development).
• resource allocator pattern (importance 2): Server process manages pool of resources. Clients request/release via channels. Dining philosophers solution uses this.. Source: (from training memory of book).

Relations

• synchronous communication (rendezvous) requires CSP channel
• CSP channel enables CSP process
• input command (c?x) exemplifies synchronous communication (rendezvous)
• output command (c!e) exemplifies synchronous communication (rendezvous)
• guarded command (Dijkstra's guards in CSP) enables alternative command ([ ... ])
• guarded command (Dijkstra's guards in CSP) enables repetitive command (*[ ... ])
• alternative command ([ ... ]) exemplifies non-determinism via alternative
• repetitive command (*[ ... ]) enables reactive system model
• parallel composition (||) requires CSP process
• parallel composition (||) requires CSP channel
• no shared memory thesis motivates synchronous communication (rendezvous)
• no shared memory thesis contradicts monitor paradigm (Hoare 1974)
• deadlock as correctness signal supports termination convention
• COPY process example exemplifies input command (c?x)
• COPY process example exemplifies output command (c!e)
• SQUASH process exemplifies stream processing model
• DIV process (Sieve of Eratosthenes) exemplifies pipeline pattern
• bounded buffer pattern exemplifies repetitive command (*[ ... ])
• bounded buffer pattern exemplifies producer-consumer pattern
• semaphore in CSP exemplifies client-server pattern
• dining philosophers problem exemplifies deadlock as correctness signal
• matrix multiplication example exemplifies systolic array pattern
• trace semantics enables process algebra
• trace semantics enables formal verification via traces
• trace refinement requires trace semantics
• failures-divergences semantics builds-on trace semantics
• failures-divergences semantics enables liveness property
• Occam language exemplifies CSP process
• Occam language requires Inmos Transputer
• Go channels (goroutines) builds-on synchronous communication (rendezvous)
• Go channels (goroutines) exemplifies buffered channels (Go extension)
• Erlang actors supports no shared memory thesis
• Erlang actors contradicts synchronous communication (rendezvous)
• Dijkstra's guarded commands (1975) motivates guarded command (Dijkstra's guards in CSP)
• monitor paradigm (Hoare 1974) contradicts no shared memory thesis
• process network topology exemplifies parallel composition (||)
• pipeline pattern exemplifies process network topology
• client-server pattern exemplifies process network topology
• client-server pattern requires repetitive command (*[ ... ])
• systolic array pattern exemplifies process network topology
• ring topology exemplifies process network topology
• blocking I/O semantics supports synchronous communication (rendezvous)
• compositional reasoning supports parallel composition (||)
• channel as abstraction barrier supports CSP channel
• formal verification via traces requires trace semantics
• FDR model checker requires trace semantics
• CSP algebraic laws exemplifies process algebra
• select statement (Go) exemplifies alternative command ([ ... ])
• pi-calculus (Milner 1992) builds-on process algebra
• pi-calculus (Milner 1992) exemplifies value-passing (not name-passing)
• Actor model (Hewitt 1973) contradicts synchronous communication (rendezvous)
• Inmos Transputer enables Occam language
• producer-consumer pattern requires bounded buffer pattern
• readers-writers problem exemplifies client-server pattern
• critical section via channels exemplifies CSP channel
• simulation relation exemplifies trace refinement
• divergence (infinite internal loop) contradicts liveness property
• refusal set enables failures-divergences semantics
• minimalism thesis motivates CSP process
• shared-memory as legacy model supports no shared memory thesis
• reactive system model requires repetitive command (*[ ... ])
• synchrony simplifies reasoning supports synchronous communication (rendezvous)
• synchrony simplifies reasoning enables compositional reasoning
• channel protocol specification requires CSP channel
• data abstraction via channels exemplifies client-server pattern
• zero-capacity channels supports synchronous communication (rendezvous)
• modularity via independent processes supports channel as abstraction barrier
• determinacy property contradicts non-determinism via alternative
• fairness assumption contradicts starvation risk
• safety property requires trace semantics
• liveness property requires failures-divergences semantics
• subroutine ≠ process distinction supports CSP process
• stream processing model exemplifies reactive system model
• event ordering (happened-before) enables trace semantics
• concurrency ≠ parallelism supports CSP process
• behavioral equivalence requires trace semantics
• abstraction function (implementation → spec) enables trace refinement
• no implementation commitment supports CSP as notation vs. implementation
• CCS (Milner 1980) exemplifies process algebra
• temporal logic for CSP enables formal verification via traces
• distributed termination detection requires deadlock as correctness signal
• proof obligations per operator requires formal verification via traces
• invariant-based proof exemplifies formal verification via traces
• recursion unfolding proof requires recursive process definition
• recursive process definition exemplifies repetitive command (*[ ... ])
• CSP → Occam compilation enables Occam language
• resource allocator pattern exemplifies dining philosophers problem
• communication patterns catalog exemplifies process network topology
• channel directionality requires channel typing
• global invariant reasoning requires no shared memory thesis
• interference freedom (Owicki-Gries) contradicts no shared memory thesis
• STOP command exemplifies deadlock as correctness signal
• hiding operator (\) enables channel as abstraction barrier
• Conway's problem exemplifies pipeline pattern
• Linda tuple spaces contradicts CSP channel
• buffered channels (Go extension) contradicts synchronous communication (rendezvous)
• timeout (later extension) contradicts blocking I/O semantics
• real-time CSP (Timed CSP) builds-on trace semantics
• priority (later extension) builds-on alternative command ([ ... ])
• fan-out (broadcast) requires output command (c!e)
• fan-in (merge) requires alternative command ([ ... ])
• synchronization overhead acceptable supports synchronous communication (rendezvous)
• Petri nets contradicts process algebra

© 2026 LOOMUS. Curation, importance scoring, edge typing, and visualization. Source paper © respective authors, quoted under fair use.