AI Discovers A-greement, a Faster Consensus Protocol
The End of Consensus Research?
The non-obvious point is that the agent harness itself, AI-greement, found bugs in established protocols while verifying new ones — a reusable recipe for applying coding agents to distributed-systems research. Distributed-systems engineers and researchers can study the harness design to run their own autonomous protocol search. It complements classics like Paxos and Raft with measurable latency gains in geo-replicated settings.
Researchers report using AI to discover A-greement, a new consensus protocol for geo-replicated state machines. Across six deployments with 5 or 9 replicas, A-greement reduces mean latency of a geo-distributed key-value store by 12.2% on write-heavy and 33.3% on read-heavy workloads versus the fastest baseline, matching it on read-only workloads. The discovery relied on AI-greement, an agent harness combining a protocol knowledge base, a modular implementation skeleton, and a Lean-based verification framework. The Lean formalization also uncovered previously unreported vulnerabilities in existing consensus protocols. The authors stress that human experts remained essential before, during, and after the search.
The End of Consensus Research?
Consensus is a fundamental problem in distributed computing and at the core of state machine replication (SMR). Despite decades of active human research, discovering practical low-latency solutions to the problem is still open, as it requires combining protocol knowledge, correctness reasoning, implementation, and experimental evaluation. We report on how AI helped us discover A-greement, a new consensus protocol for geo-replicated state machines that significantly outperforms state-of-the-art solutions. Averaged across six deployments with 5 or 9 replicas, A-greement reduces the mean latency of a geo-distributed key-value store over the fastest baseline by 12.2% and 33.3% on write-heavy and read-heavy workloads, respectively, and matches the fastest baseline on read-only workloads. A-greement combines lease-authorized local reads, direct client learning for leader-ordered writes, and a fast fixed-quorum per-key write path, selected according to network topology and workload. At the heart of our discovery lies AI-greement, an agent harness for the "autonomous" discovery, implementation, experimentation, and verification of candidate protocols. AI-greement integrates (1) a concept-oriented protocol knowledge base, (2) a modular implementation skeleton, and (3) a Lean-based verification framework with reusable safety definitions, reference specifications, and proofs. AI-greement is of independent interest: its Lean formalization uncovers several previously unreported vulnerabilities in existing consensus protocols, and it provides guidelines on how domain-specific harnesses can turn general-purpose coding agents into effective tools for (distributed) computing research. Yet we argue that human consensus experts remain essential before, during, and after the search: agents reshape the researcher's role rather than end consensus research.
