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 1: The workflow of an LLM agent.
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).
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δ
f+1
4δ
f+1
FastPaxos
Fallback only
Fast
≥3δ
>3n/4
≥3δ
>3n/4
Slow
≥4δ
f+1
≥4δ
f+1
EPaxos
Per command
Fast
≥4δ
f+⌊(f+1)/2⌋
≥4δ
f+⌊(f+1)/2⌋
Slow
≥6δ
f+1
≥6δ
f+1
CURP
Yes
Fast
≥2δ
f+⌈f/2⌉+1
≥2δ
f+⌈f/2⌉+1
Appendix
Table 1: Qualitative comparison of latency and quorum requirements. W and R denote write and read latency, respectively; δ 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.
Figure 11: Pruning with tentative metadata reverses conflicting command order: r0 executes X before Y , while r2 prunes X using its tentative tuple and executes Y before X .
Figure 12: Pruning committed B hides C , allowing r1 to execute A before C while r0 executes C before A .
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.
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 C2 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 use language models and tools to search literature, design and run experiments, analyze results, and support scientific discovery.
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.
Frédéric Berdoz, Leonardo Rugli, Roger Wattenhofer
Vibe coding turns natural-language intent into working software, but code generation alone does not give humans and agents a shared account of what they are building. As collaboration spans participants, components, and releases, design choices must remain understandable and open to revision. We argue that scaling human and AI coding collaboration requires a governable consensus layer. Agentic Consensus organizes collaboration around a versioned project-state model linking selected intent, structural commitments, executable artifacts, and evidence. Participants can clarify intent before implementation and coordinate proposed changes against commitments that humans can inspect and revise. Bidirectional synchronization connects intended changes to implementation and exposes conflicts or stale evidence as artifacts evolve. We implemented its review workflow in Consensus Control. In a small exploratory human study, 10 participants used the system on projects from their everyday work and reported clearer, faster understanding of agent-submitted changes. A three-condition comparison with the same participants collected 60 responses, with near-ceiling decision scores and measured representation and pipeline costs. Our research agenda asks how shared project state can preserve human understanding and control as agent contributions accumulate.
Tianfu Wang, Zhezheng Hao, Yin Wu +7
HKUST (GZ) Guangzhou, China · ZJU Hangzhou, China · USTC Hefei, China +1
Consensus protocols form the backbone of distributed systems and blockchains, where implementation bugs can cause data corruption and financial losses. While LLM-based approaches show promise in code analysis, they struggle with deep protocol-level logic bugs involving complex state-dependent behaviors across multiple execution stages. We present Agora, a domain-aware multi-agent framework that integrates hypothesis-driven testing with LLM capabilities for systematic protocol verification. Agora employs specialized agents that collaboratively explore protocol state spaces, synthesize attack scenarios using domain-specific constraints, and validate findings through iterative refinement. This explicit role separation enables reasoning about global protocol invariants beyond single-function code analysis. We evaluate Agora on four consensus implementations (Raft, EPaxos, HotStuff, BullShark) using four state-of-the-art LLMs. Agora discovers 15 previously unknown protocol-level logic bugs that violate safety properties, while existing LLM-based agents fail to detect any such protocol-level logic bugs. Our results demonstrate that domain-aware multi-agent collaboration is essential for detecting deep logic bugs in complex protocols.
Xiang Liu, Sa Song, Zhaowei Zhang +6
School of Computing, National University of Singapore · School of Information and Telecommunication Engineering, Beijing University of Posts and Telecommunications · Peking University +1