hoare-1978-csp

license: Apache-2.0 name: hoare-1978-csp description: Foundational theory for process-oriented concurrency through synchronous message-passing, applicable to multi-agent coordination and parallel decomposition category: Research & Academic tags: - csp - concurrency - process-algebra - formal-methods - synchronization

Communicating Sequential Processes (Hoare)

Description: Foundational theory for process-oriented concurrency through synchronous message-passing Activation triggers: Multi-agent coordination protocols, parallel task decomposition, deadlock debugging, coordination failures

Decision Points

1. System Decomposition Strategy

IF task has clear data transformations (input → process → output)
  THEN decompose by data flow (each transformation = process)
  └── Linear dependencies → pipeline topology
  └── Independent branches → parallel processes
  └── Convergence points → guarded input selection

IF components need frequent fine-grained data sharing
  THEN consider shared-memory model instead
  └── Use CSP for coarse-grained coordination only

IF coordination requirements unclear
  THEN map all component interactions first
  └── Draw communication graph before coding

See references/process-topology-as-system-architecture.md for Hoare's topology-first design thesis — why the communication graph is the architecture.

2. Communication Protocol Design

IF request-response pattern needed
  THEN client outputs request, inputs reply
       server inputs request, outputs reply
  └── Symmetric protocol prevents deadlock

IF streaming data flow
  THEN producer: *[output!data]
       consumer: *[input?data → process(data)]
  └── Termination via channel closure

IF multiple clients, one server
  THEN server uses guarded selection:
       *[client1?req → handle1(req)
        []client2?req → handle2(req)]
  └── Built-in fairness via arbitrary choice

3. Deadlock Prevention Strategy

IF communication graph has cycles
  THEN prove resource ordering OR redesign topology
  └── Cycles require careful justification

IF topology is DAG (no cycles)
  THEN deadlock impossible, proceed with design

IF bidirectional communication needed
  THEN alternate input/output carefully
  └── Never have both processes waiting for same direction

See references/failure-modes-in-concurrent-systems.md for the full taxonomy of deadlock types and detection strategies.

4. Termination Design

IF pipeline topology
  THEN source terminates first → propagates downstream
  └── Each stage: *[input?x → process(x)]

IF tree/graph topology
  THEN design explicit join points for synchronization
  └── Avoid premature termination breaking chains

IF long-running services
  THEN use external termination signals
  └── CSP suitable for bounded-lifetime tasks

See references/termination-propagation-through-process-networks.md for how termination propagates automatically through the communication topology.

Failure Modes

1. Circular Dependency Deadlock

• Symptom: System hangs with all processes waiting
• Detection: ps shows processes blocked; communication graph has cycles
• Diagnosis: Multiple processes waiting for each other (A waits for B, B waits for A)
• Fix: Reorder channel operations or break cycles with resource hierarchy

2. Protocol Asymmetry

• Symptom: One-sided blocking (client hangs, server proceeds)
• Detection: Client expects response but server sends different message type
• Diagnosis: Mismatched input/output pairs in protocol design
• Fix: Write complementary protocols (every send has matching receive)

3. Premature Termination Cascade

• Symptom: Pipeline stops early, downstream processes starved
• Detection: Some processes terminated while others still have work
• Diagnosis: Process terminated before consuming all input
• Fix: Ensure termination guards: *[input?x → process(x)] only stops when input closes

4. Guard Condition Race

• Symptom: Inconsistent behavior, sometimes works/sometimes doesn't
• Detection: Nondeterministic results with same input
• Diagnosis: Multiple guards enabled simultaneously, choice is arbitrary
• Fix: Make guards mutually exclusive or accept nondeterministic behavior

5. Buffering Assumption Violation

• Symptom: Performance degradation or unexpected blocking
• Detection: Sends block when receiver not immediately ready
• Diagnosis: Assumed asynchronous sends but CSP uses synchronous communication
• Fix: Add explicit bounded buffers where needed, keep synchronous by default

Worked Examples

Example 1: Multi-Agent Negotiation with Guards

Scenario: Auction system where auctioneer coordinates bidder agents

AUCTIONEER = 
  *[bidder1?bid(amount) → record(1, amount); announce!newbid(1, amount)
   []bidder2?bid(amount) → record(2, amount); announce!newbid(2, amount)  
   []bidder3?bid(amount) → record(3, amount); announce!newbid(3, amount)
   []timer?timeout → announce!closed; winner!result
   ]

BIDDER(id) =
  *[announce?newbid(bidder, amount) → 
      [amount < maxprice → auctioneer!bid(amount + increment)
      []amount >= maxprice → skip
      ]
   []winner?result → celebrate
   ]

Decision walkthrough:

1. Decomposition choice: Request-response pattern → guarded server selection
2. Protocol design: Auctioneer inputs bids, outputs announcements (symmetric)
3. Termination: Timer provides bounded execution, winner channel signals end
4. Nondeterminism: If multiple bidders ready simultaneously, arbitrary selection (fair)

Novice mistake: Making bidders poll for auction state instead of using announcements Expert insight: Guards encode bidding strategy (amount < maxprice), selection handles concurrency

Example 2: Pipeline Deadlock Recovery

Scenario: Data processing pipeline with validation stage that can reject items

// BROKEN VERSION (deadlock prone)
PRODUCER = *[pipeline!item(data)]
VALIDATOR = *[pipeline?item(data) → 
              [valid(data) → consumer!clean(data)
              []¬valid(data) → skip  // PROBLEM: consumer waits forever
              ]]
CONSUMER = *[validator?clean(data) → process(data)]

Failure analysis:

• Symptom: Consumer hangs waiting for data after invalid items
• Diagnosis: Validator doesn't send anything for invalid data, breaking pipeline
• Decision point: How to handle rejection without breaking flow?

// FIXED VERSION
VALIDATOR = *[pipeline?item(data) → 
              [valid(data) → consumer!clean(data)
              []¬valid(data) → consumer!error(data)  // Always send something
              ]]
CONSUMER = *[validator?clean(data) → process(data)
            []validator?error(data) → log_error(data)  // Handle both cases
            ]

Key decisions made:

1. Protocol completeness: Every input must produce some output
2. Error propagation: Rejections become explicit error messages, not silence
3. Consumer guards: Handle both success and error cases symmetically

Quality Gates

• Communication topology drawn and analyzed for cycles
• All process termination conditions explicitly defined
• Every output operation has corresponding input operation (protocol symmetry)
• Guard conditions are mutually exclusive OR nondeterminism is acceptable
• No processes terminate prematurely, breaking downstream dependencies
• Buffering requirements explicitly identified and bounded
• Deadlock potential analyzed: cycles justified or eliminated
• Resource ordering established for any shared channel access
• Error propagation paths defined (rejections don't break pipeline)
• System shutdown/cleanup procedure specified

NOT-FOR Boundaries

Don't use CSP for:

• Fine-grained parallelism: Shared-memory with locks is more efficient for tight loops
• High-frequency communication: Synchronous handshakes add overhead, use async messaging
• Complex state machines: Use dedicated state machine frameworks instead
• Database-style transactions: ACID properties need different coordination primitives
• Real-time systems: CSP's arbitrary choice semantics conflict with timing guarantees

Delegate instead:

• Shared data structures: Use concurrent-data-structures skill
• Event-driven architectures: Use event-sourcing or reactive-streams skills
• Performance-critical paths: Use lock-free-algorithms skill
• Complex scheduling: Use task-scheduling skill
• Distributed systems: Use distributed-consensus skill for cross-network coordination

CSP sweet spot: Medium-grained coordination between independent processes with clear communication boundaries and well-defined protocols.

Bundled Assets

• Diagrams → — Mermaid visualizations of process communication topology, synchronous rendezvous protocols, and guarded command state machines.
• References → — Deep dives into deadlock failure modes, guarded commands, nondeterminism/fairness, pattern matching for message discrimination, process topology as architecture, synchronous communication primitives, and termination propagation.