The End of Consensus Research?

Clément Burgelin; Rachid Guerraoui; Zicong Hong; Yinan Hu; Anne-Marie Kermarrec; Rafael Pires; Rasmus Moorits Veski; Martijn de Vos

cs.DCOct 21, 2026

The End of Consensus Research?

Authors: Clément Burgelin, Rachid Guerraoui, Zicong Hong, Yinan Hu, Anne-Marie Kermarrec, Rafael Pires, Rasmus Moorits Veski, Martijn de Vos

Organizations: École Polytechnique Fédérale de Lausanne (EPFL), Lausanne, Switzerland

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.

Figures & tables

Figure 2: Mean and tail (P99) latency of discovered consensus protocols across 20 search iterations, using the original Codex harness and the GPT-6.1 Sol model (with high reasoning effort).

Panel of Figure 3 — Figure 3: AI-greement harness architecture. Blue components provide reusable knowledge, interfaces, execution semantics, and proof support; orange components contain protocol-specific logic supplied by the agent. In the verification column, protocol specifications and proofs build on a shared execution model and linearizability definition.

Figure 4: Message propagation in A-greement on the hot (left), ordinary (middle) and cold write (right) paths.

Figure 5: Failure-free latency averaged with equal weight over the six deployments with 5 or 9 replicas. Bars report mean latency, while upper whiskers report p99 latency. Lower bound is the idealized communication baseline.

Figure 6: Recovery throughput with five replicas under workloads A, B, and C (left to right). Lines show mean completed requests per second across three topologies; bands show their minimum–maximum range.

Figure 7: Stage-attributed token usage, including input and output tokens. (a) Per-iteration usage in millions of tokens, with a broken axis omitting the range from 10 to 700 million. Formalization and verification adds 710.31 million tokens at iteration 19. (b) Phase shares within the search, excluding formalization and verification.

Appendix figures & tables10 assets

Supplementary material from the paper’s appendix.

Appendix

Protocol	Leader	Path	W	Write quorum	R	Read quorum
Paxos	Yes	Normal	$4\delta$	$f+1$	$4\delta$	$f+1$
FastPaxos	Fallback only	Fast	$\geq 3\delta$	$>3n/4$	$\geq 3\delta$	$>3n/4$
FastPaxos	Fallback only	Slow	$\geq 4\delta$	$f+1$	$\geq 4\delta$	$f+1$
EPaxos	Per command	Fast	$\geq 4\delta$	$f+\lfloor(f+1)/2\rfloor$	$\geq 4\delta$	$f+\lfloor(f+1)/2\rfloor$
EPaxos	Per command	Slow	$\geq 6\delta$	$f+1$	$\geq 6\delta$	$f+1$
CURP	Yes	Fast	$\geq 2\delta$	$f+\lceil f/2\rceil+1$	$\geq 2\delta$	$f+\lceil f/2\rceil+1$

Appendix

Table 1: Qualitative comparison of latency and quorum requirements.

W

and

R

denote write and read latency, respectively;

\delta

is a one-way message delay,

n=2f+1

, and

S

is the set of authorized read responders. “Cert” and “exec” denote certificate-based completion and completion after execution, respectively.

Replicas	Clients	Topology	Workload	SwiftPaxos		Bodega		Multi-Paxos		KCensus		A-greement (ours)		Lower bound
				mean	p99	mean	p99	mean	p99	mean	p99	mean	p99	mean	p99
5	5	clustered	A	80.955	116.199	121.120	223.832	113.834	151.313	94.267	180.063	66.412	139.075	44.250	101.500
5	5	clustered	B	80.960	115.654	54.306	217.560	113.693	151.195	97.384	119.678	24.687	134.241	19.905	98.000
5	5	clustered	C	80.908	115.247	19.602	28.499	113.637	151.255	97.763	119.604	19.598	28.490	17.200	25.000
5	5	uniform	A	168.977	244.626	233.824	352.695	214.035	264.545	230.193	403.652	166.515	263.005	118.700	176.500
5	5	uniform	B	168.956	244.639	144.595	346.727	214.058	264.543	225.345	384.629	122.017	238.409	99.710	170.500

Appendix

Table 2: Normal-case latency results in milliseconds (mean and p99). The Lower bound is analytical and excluded from ranking. Within each row, bold marks the best result among protocols, separately for mean and p99 latency.

Workload	Command	SwiftPaxos		Bodega		Multi-Paxos		KCensus		A-greement (ours)		Lower bound
		mean	p99	mean	p99	mean	p99	mean	p99	mean	p99	mean	p99
A (50% writes)	Read	114.975	164.010	77.220	176.345	158.315	211.431	138.746	210.334	56.544	129.864	27.967	46.417
	Write	115.185	163.568	212.630	265.170	158.526	211.380	145.781	297.498	145.359	188.035	86.452	118.000
	All	115.081	163.745	144.949	262.797	158.421	211.400	142.245	282.171	100.984	186.281	57.209	118.000
B (5% writes)	Read	115.081	163.654	61.927	164.521	157.869	211.112	136.461	200.008	40.669	96.328	27.967	46.417
	Write	115.481	163.833	207.254	262.435	158.382	211.527	129.774	268.959	150.453	187.524	86.452	118.000

Appendix

Table 3: Operation-level normal-case latency in milliseconds, averaged with equal weight over the six deployments with 5 or 9 replicas. The Lower bound is analytical and excluded from ranking. Within each row, bold marks the best result among protocols, separately for mean and p99 latency.

Panel of Figure 11 — Figure 11: Pruning with tentative metadata reverses conflicting command order: $r_{0}$ executes $X$ before $Y$ , while $r_{2}$ prunes $X$ using its tentative tuple and executes $Y$ before $X$ .

Panel of Figure 12 — Figure 12: Pruning committed $B$ hides $C$ , allowing $r_{1}$ to execute $A$ before $C$ while $r_{0}$ executes $C$ before $A$ .

Panel of Figure 13 — Figure 13: Counterexample to Bodega’s early-accept read optimization. All replicas accept $w$ , but delayed acceptance replies prevent $L$ from committing it. Accept notifications let $A$ return $7$ , while a subsequent read at $L$ returns absence.

Panel of Figure 14 — Figure 14: A Bodega client retry can repeat a write that has already taken effect. The first attempt sets $x=1$ , but its reply is delayed. After $C_{2}$ reads $1$ and completes a write of $2$ , a retry with a new identifier overwrites $x$ with $1$ . If both attempts represent one client write, the final read must return $2$ .

Work	Search	Target	Correctness check	Objective	New algorithm or protocol?
Algorithm and policy discovery
AlphaDev [ 47 ]	Deep RL	Sorting, hashing (assembly)	Tests	Latency	Yes: sorting routines merged into LLVM libc++
FunSearch [ 62 ]	LLM + evolution	Math, bin packing	Evaluator	Score	Yes: new cap-set constructions and packing heuristics
AlphaEvolve [ 54 ]	LLM + evolution	Math, kernels, scheduling	Evaluator	Score	Yes: new algorithms (e.g., matrix multiplication) and data-center heuristics
ADRS [ 14 ]	LLM + evolution	Systems policies	Simulator, tests	Cost, latency	Yes: single-node policies (scheduling, load balancing), consensus deemed a poor fit
Glia [ 24 ]	Multi-agent LLM	LLM-serving routing, scaling	Simulator	Completion time	Yes: request-routing algorithm

Appendix

Table 4: AI-driven discovery of algorithms and protocols. Before AI-greement , no automated system had produced a new fault-tolerant consensus protocol that improves measured performance.

Work	Context builder	Solution generator	Evaluator	Solution selector
AlphaDev [ 47 ]	Current assembly program and its CPU state	Policy network adding one instruction at a time	Correctness tests and measured latency	Monte Carlo tree search
FunSearch [ 62 ]	Prompt with the best programs sampled from one island	Pretrained code LLM	Runs the program on problem instances and scores it	Island-based evolutionary database
AlphaEvolve [ 54 ]	Prompt with prior programs, scores, and human-written context, with prompts that can themselves evolve	Ensemble of Gemini models emitting code diffs	User-supplied evaluation function, applied as a cascade of tests	Program database combining MAP-Elites and islands
ADRS [ 14 ] (OpenEvolve)	Fixed prompt template with problem statement and prior solutions	Ensemble of LLMs editing code	Simulator replaying workload traces	MAP-Elites and islands
Glia [ 24 ]	Task description and shell access to the codebase	Researcher LLM agent, guided by a Supervisor agent	Simulator (request completion time)	Researcher’s own analysis, then best of independent runs
SkyDiscover [ 44 , 42 ]	Problem context with feedback and reflections from prior solutions	LLM calls with optional tool use	User-supplied scoring function	Pluggable (Top-K, MAP-Elites, Pareto), adaptive (AdaEvolve), or evolved (EvoX)

Appendix

Table 5: Discovery procedures, described in the nomenclature of SkyDiscover [ 44 ] .

Work	Problem	C1	C2	C3	Why the challenges do not arise, or how they are sidestepped
Classical algorithms
AlphaDev [ 47 ]	Sorting, hashing				Output is checked by tests on small deterministic inputs. Latency is measured in microseconds
FunSearch [ 62 ]	Cap sets, bin packing				Every packing is valid and every construction is checked exactly
AlphaEvolve [ 54 ]	Matrix multiplication, scheduling				Decompositions are checked exactly, and every schedule is valid
Distributed-systems policies
ADRS [ 14 ]	Spot scheduling, load balancing				Optimizations rarely alter system semantics. Candidates are scored in a simulator

Appendix

Table 6: Challenges of consensus discovery (C1: performance conflicts with correctness, C2: tests cannot establish correctness, C3: evaluation is expensive) faced by AI-driven discovery approaches. faced, sidestepped by restricting the problem, does not arise.

Autonomous Research Agents

Autonomous research agents use language models and tools to search literature, design and run experiments, analyze results, and support scientific discovery.

See all 318 papers

Can AI Agents Agree?
Mar 1, 2026Frédéric Berdoz, Leonardo Rugli, Roger WattenhoferMulti-Agent Consensus LLM Agent Reliability
ETH Zurich, Switzerland
Scaling Human-AI Coding Collaboration Requires a Governable Consensus Layer
Apr 20, 2026Tianfu Wang, Zhezheng Hao, Yin Wu +7AI Agent Benchmarks AI Agent Governance
HKUST (GZ) Guangzhou, China · ZJU Hangzhou, China · USTC Hefei, China +1
Agora: Toward Autonomous Bug Detection in Production-Level Consensus Protocols with LLM Agents
May 28, 2026Xiang Liu, Sa Song, Zhaowei Zhang +6Multi-Agent LLM Systems Software Vulnerability Detection
School of Computing, National University of Singapore · School of Information and Telecommunication Engineering, Beijing University of Posts and Telecommunications · Peking University +1

Mar 1, 2026J/K move · Enter open · S save

Can AI Agents Agree?

Frédéric Berdoz, Leonardo Rugli, Roger Wattenhofer

ETH Zurich, Switzerland

Multi-Agent Consensus LLM Agent Reliability LLM Agent Evaluation

Open paper AskPDF arXiv

Large language models are increasingly deployed as cooperating agents, yet their behavior in adversarial consensus settings has not been systematically studied. We evaluate LLM-based agents on a Byzantine consensus game over scalar values using a synchronous all-to-all simulation. We test consensus in a no-stake setting where agents have no preferences over the final value, so evaluation focuses on agreement rather than value optimality. Across hundreds of simulations spanning model sizes, group sizes, and Byzantine fractions, we find that valid agreement is not reliable even in benign settings and degrades as group size grows. Introducing a small number of Byzantine agents further reduces success. Failures are dominated by loss of liveness, such as timeouts and stalled convergence, rather than subtle value corruption. Overall, the results suggest that reliable agreement is not yet a dependable emergent capability of current LLM-agent groups even in no-stake settings, raising caution for deployments that rely on robust coordination.

Abstract

Autonomous Research Agents

Explore similar work

Can AI Agents Agree?

Scaling Human-AI Coding Collaboration Requires a Governable Consensus Layer

Agora: Toward Autonomous Bug Detection in Production-Level Consensus Protocols with LLM Agents