Learning Provably Correct Distributed Protocols Without Human Knowledge

Yujie Hui, Xiaoyi Lu, Andrew Perrault, Yang Wang · 2026

Read Learning Provably Correct Distributed Protocols Without Human Knowledge by Yujie Hui, Xiaoyi Lu, Andrew Perrault, Yang Wang (2026) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2601-22369.txt.

Introduction

Yujie Hui, Xiaoyi Lu, Andrew Perrault, and Yang Wang teach machines to design network rules that are provably right. Such rules let many computers agree despite faults and doubt. Their 2026 preprint notes that hand-made rules have taken decades of expert work.

Their learner searches for rules that come with a proof of correctness. That proof bar is what sets the work apart from plain trial-and-error design. Provably right rules could speed the build of cloud and bank systems. They could also cut the risk of rare, costly faults. The work aims at trust, not just speed.

Catalog record

CREATORYujie Hui, Xiaoyi Lu, Andrew Perrault, Yang Wang
YEAR2026
COLLECTIONPAPERS
FORMATTXT
FILE SIZE75 KB
VERSION1.0
LICENSEhttp://creativecommons.org/licenses/by/4.0/
RIGHTSCC BY
SOURCEarXiv

Source: https://arxiv.org/abs/2601-22369

Browse the full library · About the Tower of Babel

Full text

The opening of the work, from the library's hosted text:

Learning Provably Correct Distributed Protocols Without Human Knowledge Yujie Hui, Xiaoyi Lu, Andrew Perrault, Yang Wang Abstract Provably correct distributed protocols, which are a critical component of modern distributed systems, are highly challenging to design and have often required decades of human effort. These protocols allow multiple agents to coordinate to come to a common agreement in an environment with uncertainty and failures. We formulate protocol design as a search problem over strategies in a game with imperfect information, and the desired correctness conditions are specified in Satisfiability Modulo Theories (SMT). However, standard methods for solving multi-agent games fail to learn correct protocols in this setting, even when the number of agents is small. We propose a learning framework, GGMS, which integrates a specialized variant of Monte Carlo Tree Search with a transformer-based action encoder, a global depth-first search to break out of local minima, and repeated feedback from a model checker. Protocols output by GGMS are verified correct via exhaustive model checking for all executions within the bounded setting. We further prove that, under mild assumptions, the search process is complete: if a correct protocol exists, GGMS will eventually find it. In experiments, we show that GGMS can learn correct protocols for larger settings than existing methods. 1 Introduction Consider a coordination game where multiple agents must reach agreement on a shared decision, but each agent observes only its own local state and the messages it receives—some of which may be lost. An adversary controls which messages fail to arrive. The agents win if they all reach the same valid decision; they lose if any agent decides differently or violates a safety constraint. Crucially, this is not a game where high expected reward suffices—we need guaranteed correctness under worst-case adversarial play. A protocol that works 99.9% of the time is useless; a single counterexample renders it unusable. This formulation captures the essence of distributed protocol design , a fundamental problem in building reliable systems. When you use a database, make a payment, or store a file in the cloud, distributed protocols ensure that multiple machines either all agree on what happened, or the operation safely aborts—even when machines crash or messages vanish. Designing these protocols has historically required decades of human ingenuity: The above formulation represents the consensus problem, a classic topic in distributed protocols, and consensus alone has motivated over 40 years of research spanning Paxos ( 21 ; 22 ; 29 ; 31 ) and Byzantine fault tolerance ( 20 ; 7 ; 18 ; 11 ) . A concrete example. In the consensus problem, three processes P1, P2, P3 must agree on a single value. Suppose P1 and P2 start proposing “0” while P3 proposes “1”. In round one, each process broadcasts its proposal—but P3 crashes mid-broadcast, so P1 receives P3’s message while P2 does not. Now P1 sees {0, 0, 1} while P2 sees {0, 0, ?}. Despite this asymmetry, a correct protocol must lead both to the same final decision. The FloodSet algorithm ( 25 ) achieves this in f+1 rounds (where f is the maximum failures): each process repeatedly broadcasts everything it has received, and in the final round decides on the minimum value. The key insight is that at least one round must be failure-free, allowing all processes to synchronize (see § 2.1 ). Can we automate the discovery of such protocols? The game-theoretic structure—partial observability, adversarial uncertainty, hard safety constraints—suggests this problem might be amenable to the search-based learning that succeeded in games like Go and poker. We formulate protocol design as search over strategies in an imperfect-information game, where correctness properties are formally specified and exhaustively verified. We pursue this through zero-knowledge synthesis : given only a specification of what constitutes a correct outcome, can a learning system discover protocols without human-designed examples? This methodology serves two purposes. First, it reveals what structure is necessary for correctness versus merely conventional —when our system independently discovers FloodSet-like protocols, this confirms the structure is dictated by the problem constraints rather than historical accident. Second, it provides a rigorous baseline: success validates that the search space is tractable, while the framework can naturally incorporate human knowledge (warm-starting, architectural constraints) when desired. However, standard game-playing approaches fail here. In AlphaGo-style MCTS ( 32 ) , self-play learns policies that win in expectation . Distributed protocols require something stronger: a policy that never loses against any failure pattern. Additionally, multiple correct protocols often exist, and naive learning can mix transitions from different protocols—a superposition problem —causing failures even when each protocol would individually be correct. These challenges defeat prior methods even for 3–4 agents. We develop Guided Global Monte Carlo Tree Search (GGMS) , integrating three key ideas. (1) Model checking as a hard oracle : any candidate protocol is exhaustively verified against all possible executions (for the given process count). Violations produce counterexamples that feed back into training. This exhaustive verification—not the learning process—is what makes output protocols provably correct . (2) Global depth-first search : when learning produces ambiguous transitions (multiple outputs with similar probability), often due to the superposition problem mentioned above, GGMS freezes one choice and continues. If no correct protocol exists under current freezes, it backtracks systematically. This guarantees eventual convergence if a correct protocol exists. (3) Guided sampling : a phased curriculum starts with less ambiguous scenarios (failures only in later rounds, unambiguous initial states), allowing the effects of frozen transitions to propagate before relaxing to harder cases. We make the following contributions. (1) We formulate distributed protocol design as search over state machines in an imperfect-information game with formal correctness specifications and exhaustive verification. (2) We propose GGMS, combining MCTS with a transformer encoder, global DFS, and iterative model-checking feedback. We prove that under mild assumptions, the search is complete: GGMS will not miss correct solutions (§ 4.2 ). (3) We demonstrate that GGMS learns correct protocols where standard MCTS fails, scaling to 4 processes with 3 failures. For consensus, it independently recovers FloodSet-like protocols. For synchronous atomic commit—a variant without known solutions—it discovers a novel correct protocol (§ 5 ). Relationship to LLMs. We tested GPT and Gemini (Appendix H ): both retrieved FloodSet for consensus but often failed on synchronous atomic commit on the first attempt, since it lacks existing solutions. LLMs struggle with systematic exploration for novel synthesis, making GGMS complementary. Our evaluation shows GGMS achieves substantially higher success rates than MCTS baselines across all tested configurations. We discuss limitations including synchronous network assumptions and bounded process counts, and outline directions for relaxing these assumptions and integrating with LLM-based approaches. 2 Background 2.1 Distributed Protocols as State Machines The distributed systems community models protocols using the state machine approach : each process is a state machine that takes its current state and incoming messages as input, and outputs a new state and messages to send. This enables both precise specification and formal verification. Protocols vary along several dimensions. Failure models specify what can go wrong: in crash failures , a failed process simply stops responding; in Byzantine failures , a failed process may behave arbitrarily. Timing models specify synchrony assumptions: in synchronous networks, message delays and clock drift are bounded; in asynchronous networks, no such

Read the complete text