The End of Consensus Research?
Abstract
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.
The following analysis is generated by AI and may contain errors. It is separate from the authors’ abstract and is not peer review.
Research summary
The paper presents AI-greement, a specialized agent harness that leverages formal verification and domain knowledge to autonomously discover and verify a new consensus protocol, A-greement, which outperforms state-of-the-art solutions in geo-distributed settings. This work is significant as it demonstrates a novel application of AI agents in the design of complex distributed systems, moving beyond code generation to algorithmic discovery and formal verification, thereby offering a new paradigm for tackling hard problems in distributed computing.
Methodology
The paper proposes "AI-greement," a specialized agent harness designed to autonomously discover, implement, experiment with, and verify distributed consensus protocols. The methodology integrates three key components: a concept-oriented protocol knowledge base, a modular implementation skeleton, and a Lean-based formal verification framework. This approach moves beyond simple code generation by embedding domain-specific constraints and formal safety definitions directly into the agent's workflow. The resulting protocol, A-greement, is a hybrid design combining lease-authorized local reads, direct client learning for leader-ordered writes, and fast fixed-quorum per-key write paths. The use of Lean for verification is a significant methodological strength, as it allows the agent to reason about correctness rather than just performance, leading to the discovery of previously unreported vulnerabilities in existing protocols.
Results & evaluation
The evaluation is rigorous, comparing A-greement against state-of-the-art baselines across six different geo-distributed deployments with 5 and 9 replicas. The results show a 12.2% reduction in mean latency for write-heavy workloads and a 33.3% reduction for read-heavy workloads compared to the fastest baseline. The paper also validates the safety of the discovered protocol using the Lean framework. The inclusion of real-world network topologies and varied workload characteristics strengthens the empirical claims.
Reproducibility
The paper provides details on the agent harness architecture and the Lean verification framework, which are critical for reproducibility. However, as the full text provided is a skeleton with section headers, specific implementation details, prompt engineering strategies, and code repositories are not visible in the excerpt. The mention of a "modular implementation skeleton" suggests that code artifacts are likely available or planned, but without the actual code or detailed prompt logs, full reproducibility of the *discovery process* is difficult to assess from the abstract and headers alone.
Limitations
The primary limitation is the reliance on a highly specialized, domain-specific harness (AI-greement) which may not generalize easily to other areas of distributed computing or software engineering without significant adaptation. Additionally, the "autonomous" nature of the discovery is tempered by the authors' admission that human experts remain essential, suggesting the current level of autonomy is limited to search space reduction and verification assistance rather than fully independent invention. The performance gains, while significant, are specific to geo-replicated state machines and may not apply to other consensus contexts.
Broader impact
This paper has high potential impact on the field of AI for Systems. It demonstrates that LLMs can be effectively used not just for coding, but for the *design* of complex distributed algorithms when coupled with formal verification tools. The discovery of vulnerabilities in existing protocols via the Lean framework highlights the utility of AI-assisted formal methods. This work could inspire similar "agent harnesses" for other hard problems in computer science where correctness and performance are tightly coupled. The paper presents AI-greement, a specialized agent harness that leverages formal verification and domain knowledge to autonomously discover and verify a new consensus protocol, A-greement, which outperforms state-of-the-art solutions in geo-distributed settings. This work is significant as it demonstrates a novel application of AI agents in the design of complex distributed systems, moving beyond code generation to algorithmic discovery and formal verification, thereby offering a new paradigm for tackling hard problems in distributed computing.
Author of this paper? Send a correction.