Learning Provably Correct Distributed Protocols Without Human Knowledge

• URL: http://arxiv.org/abs/2601.22369v1
• Date: Thu, 29 Jan 2026 22:24:07 GMT
• Title: Learning Provably Correct Distributed Protocols Without Human Knowledge
• Abstract summary: We formulate protocol design as a search problem over strategies in a game with imperfect information.<n>Standard methods for solving multi-agent games fail to learn correct protocols in this setting.<n>We propose a learning framework, GGMS, which integrates a specialized variant of Monte Carlo Tree Search with a transformer-based action encoder.
• Score: 12.414511696558291
• License: http://creativecommons.org/licenses/by/4.0/
• 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.

Related papers

• A Technical Taxonomy of LLM Agent Communication Protocols [60.76747983053368]
  This study develops a technical taxonomy to classify and analyze large language models (LLMs) agent communication protocols.<n>The framework guides protocol selection and highlights open research gaps such as privacy and policy enforcement.
  arXiv  Detail & Related papers  (2026-06-17T14:45:20Z)
• Agora: Toward Autonomous Bug Detection in Production-Level Consensus Protocols with LLM Agents [11.555840794263753]
  Agora is a domain-aware multi-agent framework that integrates hypothesis-driven testing with LLM capabilities for systematic protocol verification.<n>Our results demonstrate that domain-aware multi-agent collaboration is essential for detecting deep logic bugs in complex protocols.
  arXiv  Detail & Related papers  (2026-05-28T13:27:47Z)
• From I/O to Code with Discovery Agent [103.88427301265669]
  We propose DIO-Agent, a discovery agent for IO2Code.<n>Our method frames IO2Code as an evolutionary search over discrete program space.<n>Extensive experiments show that DIO-Agent consistently outperforms both traditional program-by-example method and SOTA evolution-agent baselines.
  arXiv  Detail & Related papers  (2026-05-14T18:57:32Z)
• Correction and Corruption: A Two-Rate View of Error Flow in LLM Protocols [51.56484100374058]
  We propose a paired-outcome measurement interface for auditing a single protocol step on exact-match tasks.<n>For each instance, the interface records a baseline correctness bit and a post-step correctness bit.<n>These rates predict accuracy changes and define a reusable empirical interface testable across seeds, mixtures, and pipelines.
  arXiv  Detail & Related papers  (2026-04-20T13:25:40Z)
• Autogenesis: A Self-Evolving Agent Protocol [60.15939127351914]
  We introduce Autogenesis Protocol (AGP), a self evolution protocol that decouples what evolves from how evolution occurs.<n>We present Autogenesis System (AGS), a self-evolving multi-agent system that dynamically instantiates, retrieves, and refines protocol-registered resources during execution.
  arXiv  Detail & Related papers  (2026-04-16T14:04:06Z)
• Which LLM Multi-Agent Protocol to Choose? [30.16052895726503]
  We introduce ProtocolBench, a benchmark that compares agent protocols along four measurable axes: task success, end-to-end latency, message or byte overhead, and under failures.<n>On ProtocolBench, protocol choice significantly influences system behavior.<n> Protocol completion is a learnable protocol router that selects per-scenario protocols from requirement and runtime signals.
  arXiv  Detail & Related papers  (2025-10-20T04:53:19Z)
• LLM-Assisted Model-Based Fuzzing of Protocol Implementations [9.512044399020514]
  Faults in protocol behavior can lead to vulnerabilities and system failures.<n>A common approach to protocol testing involves constructing Markovian models that capture the state transitions and expected behaviors of the protocol.<n>We propose a novel method that leverages large language models (LLMs) to automatically generate sequences for testing network protocol implementations.
  arXiv  Detail & Related papers  (2025-08-03T13:16:18Z)
• Validating Network Protocol Parsers with Traceable RFC Document Interpretation [11.081773172066766]
  oracle and traceability problems determine when a protocol implementation can be considered buggy.<n>This work considers both and provides an effective solution using recent advances in large language models (LLMs)<n>We have extensively evaluated our approach using nine network protocols and their implementations written in C, Python, and Go.
  arXiv  Detail & Related papers  (2025-04-25T03:39:19Z)
• Subversion Strategy Eval: Can language models statelessly strategize to subvert control protocols? [50.62012690460685]
  This paper investigates how well AI systems can generate and act on their own strategies for subverting control protocols.<n>An AI system may need to reliably generate optimal plans in each context, take actions with well-calibrated probabilities, and coordinate plans with other instances of itself without communicating.
  arXiv  Detail & Related papers  (2024-12-17T02:33:45Z)
• Games for AI Control: Models of Safety Evaluations of AI Deployment Protocols [52.40622903199512]
  This paper introduces AI-Control Games, a formal decision-making model of the red-teaming exercise as a multi-objective, partially observable game. We apply our formalism to model, evaluate and synthesise protocols for deploying untrusted language models as programming assistants.
  arXiv  Detail & Related papers  (2024-09-12T12:30:07Z)
• Pessimism of the Will, Optimism of the Intellect: Fair Protocols with Malicious but Rational Agents [0.6990493129893112]
  We present a game-based framework for the study of fairness protocols. It is based on the notion of strong secure equilibria, and leverages the conceptual and algorithmic toolbox of game theory.
  arXiv  Detail & Related papers  (2024-05-29T10:15:36Z)
• DT-SIM: Property-Based Testing for MPC Security [2.0308771704846245]
  Property-based testing is effective for detecting security bugs in secure protocols. We specifically target Secure Multi-Party Computation (MPC) We devise a test that can detect various flaws in a bit-level implementation of an MPC protocol.
  arXiv  Detail & Related papers  (2024-03-08T02:02:24Z)
• Semi-DETR: Semi-Supervised Object Detection with Detection Transformers [105.45018934087076]
  We analyze the DETR-based framework on semi-supervised object detection (SSOD) We present Semi-DETR, the first transformer-based end-to-end semi-supervised object detector. Our method outperforms all state-of-the-art methods by clear margins.
  arXiv  Detail & Related papers  (2023-07-16T16:32:14Z)
• Reinforcement learning-enhanced protocols for coherent population-transfer in three-level quantum systems [50.591267188664666]
  We deploy a combination of reinforcement learning-based approaches and more traditional optimization techniques to identify optimal protocols for population transfer. Our approach is able to explore the space of possible control protocols to reveal the existence of efficient protocols. The new protocols that we identify are robust against both energy losses and dephasing.
  arXiv  Detail & Related papers  (2021-09-02T14:17:30Z)
• Round-robin differential phase-time-shifting protocol for quantum key distribution: theory and experiment [58.03659958248968]
  Quantum key distribution (QKD) allows the establishment of common cryptographic keys among distant parties. Recently, a QKD protocol that circumvents the need for monitoring signal disturbance, has been proposed and demonstrated in initial experiments. We derive the security proofs of the round-robin differential phase-time-shifting protocol in the collective attack scenario. Our results show that the RRDPTS protocol can achieve higher secret key rate in comparison with the RRDPS, in the condition of high quantum bit error rate.
  arXiv  Detail & Related papers  (2021-03-15T15:20:09Z)
• Entanglement purification by counting and locating errors with entangling measurements [62.997667081978825]
  We consider entanglement purification protocols for multiple copies of qubit states. We use high-dimensional auxiliary entangled systems to learn about number and positions of errors in the noisy ensemble.
  arXiv  Detail & Related papers  (2020-11-13T19:02:33Z)
• End-to-End Object Detection with Transformers [88.06357745922716]
  We present a new method that views object detection as a direct set prediction problem. Our approach streamlines the detection pipeline, effectively removing the need for many hand-designed components. The main ingredients of the new framework, called DEtection TRansformer or DETR, are a set-based global loss.
  arXiv  Detail & Related papers  (2020-05-26T17:06:38Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.