| 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:
- Decomposition choice: Request-response pattern → guarded server selection
- Protocol design: Auctioneer inputs bids, outputs announcements (symmetric)
- Termination: Timer provides bounded execution, winner channel signals end
- 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:
- Protocol completeness: Every input must produce some output
- Error propagation: Rejections become explicit error messages, not silence
- Consumer guards: Handle both success and error cases symmetically
Quality Gates
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.
