Multi-Agentness as FLP: limits of AI coordination

Multiagent Development as Distributed Consensus: FLP and Lamport in Action

Multiagent systems for code generation face fundamental limitations inherent to distributed systems. Coordinating AI agents is equivalent to solving consensus in asynchronous networks with failures, where the FLP and Lamport theorems set hard boundaries. Even AGI cannot bypass these impossibility results—explicit protocols and failure detectors are essential.

Formalizing the Agent Coordination Problem

The multiagent development process is formalized through the set of valid programs Φ(P) generated by prompt P. Each agent produces a refinement φ_i, and consensus is achieved when all φ_i refine a single φ ∈ Φ(P):

C(φ_1, ..., φ_n) := ∃ φ ∈ Φ(P), ∀i, φ_i refines φ

Without a protocol, agents compete over design decisions: one picks callback APIs, another async/await, leading to Git conflicts. A supervisor merging PRs doesn’t solve the issue—it masks it, causing lost work during rebases.

Key FLP Conditions:

• Asynchronous delivery: agents decide when to process messages after tool calls.
• Crash failures: processes die, loops hang, pkill disrupts communication.

The FLP Impossibility Theorem: No Perfect Consensus

FLP (Fischer-Lynch-Paterson, 1985) proves that in an asynchronous system with a single crash failure, you cannot guarantee safety (correctness), liveness (progress toward a solution), and fault tolerance simultaneously. Pick any two—your third is lost.

In agents, this manifests as endless rollback cycles: Agent A finalizes a design, B reverts it, A reacts. Without a failure detector (Chandra-Toueg, 1996), liveness is unattainable. In practice, teams use ps | grep to check neighbor health, extending the model into partial synchrony.

Byzantine Failures from Misinterpreted Prompts

Lamport (1982): With f Byzantine agents (misinterpreting prompts, generating incompatible φ_i), you need n > 3f + 1 agents for consensus. A Byzantine agent falsifies decisions like a general lying about votes.

LLM voting is inefficient due to the vast space Φ(P). Solution: external validators (tests, linters, verification) convert Byzantine failures into crash failures, reducing the system to FLP mode with known algorithms (Paxos-like).

Validator Trade-offs:

• Increase safety at the cost of liveness (slower pipelines).
• Reduce Byzantine risks but don’t eliminate FLP constraints.
• Scale with n, where f < (n-1)/3.

Practical Pipeline Design Rules

• Failure detectors are mandatory: agents monitor neighbors’ progress to avoid hangs.
• Task partitioning: minimize file overlaps (worktree patterns mirror CAP’s partition tolerance).
• Timeouts and restarts: implement partial synchrony (Dwork-Lynch-Stockmeyer, 1988) with bounded delays.
• External validation first: tests > coordination; convert failures early.
• Avoid ad-hoc solutions: use Paxos or Raft for explicit consensus.

CAP theorem applies: in multiagent systems, partition tolerance is often sacrificed for CA (consistency + availability).

Advanced Concepts for Scalability

Common Knowledge (Halpern-Moses, 1990): "Everyone knows that everyone knows" is unattainable without protocols—explains shared document failures (CLAUDE.md).

Partial Synchrony: timeouts increase message complexity but enable consensus.

These tools from 40 years of theory enable reliable pipelines—without relying on AGI hype.

What Matters

• Multiagent systems are distributed consensus under FLP/CAP constraints, independent of model choice.
• Validators (tests, linters) convert Byzantine failures into crashes, making systems manageable.
• Failure detectors and partitioning are the minimal production-ready toolkit.
• Use n > 3f + 1 to resist misinterpretations of prompts.
• AGI may improve constants—but not the impossibility boundaries.

— Editorial Team