Multi-Agentic Software Development Is a Distributed Systems Problem

Multi-agentic Software Development is a Distributed Systems Problem (AGI can't save you from it)

Recently, I've been thinking a lot about scaffolding and languages for managing systems of LLMs coordinating with each other — new programming languages might be the ideal solution for this area.

We have a rather fun paper in the works developing a fun choreographic language for describing multi-agent workflows — it turns out that choreographies, while being too weak for any practical distributed protocol, are actually quite a concise and elegant formalism for describing the bespoke interactions that arise between agents, especially so if we incorporate game theory. Keep an eye out for that, we'll be sharing it soon!

Now, one annoying piece of feedback that I keep on hearing, even from other verification researchers who should know better, is a sort of apathy about the state of affairs, and towards the goals of developing formalisms and languages to manage agents. The common refrain is best summarised as the quote:

"The best solution to agentic coordination is to just wait a few months."

The argument roughly summarises to something like:

• Current multi-agentic LLM systems are unable to build large-scale software autonomously (agreed ✅).
• This boils down to an issue of coordination (agreed ✅).
• The next generation of models will be smarter (agreed ✅).
• The next generation of models will not have coordination problems (⁇ HUH ⁇).

The main implication is that building languages and tooling to describe and manage these systems is a sisyphean task; newer models will inevitably render them obsolete, and the entire effort will be in vain.

As a verification researcher I find this capitulation a little premature and misguided: there's a rich literature of distributed systems literature, literally about this very problem, that people are ignoring, and a number of impossibility results that are invariant to model capability. Even if the next models are AGI (lol), the problem of coordination is a fundamental one, and smarter agents alone can't escape it.

In this blog post, I want to flesh out this idea, and break down the problem of multi-agent software development into a formal model and establish some connections to some standard distributed systems impossibility results. Distributed consensus is difficult, no matter how AGI your participants are.

A Formal Model of Software Development

Claude. Make me an app to track recipes.

We can model the problem of multi-agent synthesis formally as follows:

Given a prompt $P :=$ "An app to track recipes", we can define the formula $\Phi(P)$ as the set of software consistent with the prompt:

$$\Phi(P) := { \phi \mid \phi \text{ program} \land \phi \text{ is consistent with the prompt } P }$$

The key point here is that a natural language prompt, by its very nature, is underspecified — i.e there may be multiple programs that are consistent with the prompt. When we use LLMs to build and write software systems, we're effectively asking the LLMs to select one element amongst many from this set.

Conversely, when we do multi-agentic software development, i.e we spin up several agents, $A_1, \dots, A_n$, and ask them to build a piece of software, we're essentially asking them each to produce software components $\phi_1, \dots, \phi_n$ such that they all refine one single consistent interpretation of the prompt:

$$C(\phi_1, \dots, \phi_n) := \exists \phi \in \Phi(P), \forall i, \phi_i \text{ refines } \phi$$

This in other words, is nothing other than one big distributed consensus problem.

In other words, the user's prompt $P$ first gets sent split, via a plan, into tasks for several agents $a_1, \dots, a_n$. Then, these agents work in parallel to implement their respective coding tasks $\phi_1, \dots, \phi_n$, and by the end, if the synthesis was successful, we're hoping that the final generated software system $\phi$ composed of each of the individual constructions $\phi := \phi_1 || \dots || \phi_n$, satisfies the user's request.

This is inherently a consensus problem as the agents $a_1, \dots, a_n$ must work concurrently to produce their software artefacts $\phi_1, \dots, \phi_n$, but communicate and agree enough that the final piece of software $\phi_1 || \dots || \phi_n$ is well formed and satisfies the request. Design decisions or choices in one $\phi_i$ will result in constraints that affect and influence the possible choices of $\phi_j$ for other agents. For example, if the agent in charge of implementing network connections $a_{\text{network}}$ chooses a library with a callback-style async API for requests, then whichever agent is responsible for the overall integration $a_{\text{integration}}$ must organise the infrastructure around that choice and so on and so forth. Similar choices in other modules will influence the design spaces of other agents and overall the process proceeds as a joint synthesis problem.

Is this really a Distributed Consensus Problem?

As we complete our formal model of agentic software development, at this point, I'd like to also take a second to shoot down some obvious rebuttals.

• Why is $P$ underspecified? This holds by the very nature of natural language as being ambiguous. As it turns out, we do have a way to give a precise and unambiguous specifications for software. It's called a programming language. Anything else leaves room for the agent to make design decisions.
• Is the problem inherently concurrent? The motivations for throwing multiple agents at a software system are somewhat outside the scope of this post, but as soon as we have made that decision and we have multiple agents working on our tasks, then the problem is inherently concurrent, and we have to solve problems of coordination.
• Can't we have a single supervisor to dictate choices? A git repo is a pretty standard approach to trying to coordinate parallel software development, but you haven't solved the fundamental concurrency problem, at best you've hard-coded yourself into a single choice of concurrency: when one design decision is chosen and merged into the codebase, what happens to work that must be rebased? what if it has conflicts? Some work has to be lost.

The key point that I'm trying to convey here is not that you can't sometimes do multi-agentic software development while ignoring the concurrency problem, but rather that this perspective helps us be prescient about how we are resolving these fundamental concurrency problems with our coordination workflows.

Impossibility Results for Multi-agentic Software Development

Now we have this formal model of agentic software development, it's time for the payoff of this blog post! Let's draw some connections to distributed systems and try and sketch out some impossibility results.

FLP for multi-agentic systems (Safety, Liveness, Fault Tolerance, pick two)

Of course, where else could we start but with FLP, oh my dear FLP. Fischer, Lynch and Paterson's seminal p